计算机科学技术学报 ›› 2021,Vol. 36 ›› Issue (1): 158-190.doi: 10.1007/s11390-020-9516-3

所属专题： Software Systems

• • 上一篇    下一篇

从业务流程中展开迭代控制结构

Yain-Whar Si and Weng-Hong Yung   

  1. Department of Computer and Information Science, University of Macau, Macau, China
  • 收稿日期:2019-02-26 修回日期:2020-12-04 出版日期:2021-01-05 发布日期:2021-01-23
  • 作者简介:Yain-Whar Si is an associate professor at the Department of Computer and Information Science, University of Macau, Macau. His research interest includes business process management, information visualization, and decision support systems.
  • 基金资助:
    The work was supported by University of Macau under Grant No. MYRG2019-00136-FST.

Unraveling Iterative Control Structures from Business Processes

Yain-Whar Si and Weng-Hong Yung        

  1. Department of Computer and Information Science, University of Macau, Macau, China
  • Received:2019-02-26 Revised:2020-12-04 Online:2021-01-05 Published:2021-01-23
  • About author:Yain-Whar Si is an associate professor at the Department of Computer and Information Science, University of Macau, Macau. His research interest includes business process management, information visualization, and decision support systems.
  • Supported by:
    The work was supported by University of Macau under Grant No. MYRG2019-00136-FST.

PDF (PC)

46

补充材料

1

迭代控制结构允许重复执行任务、活动或子流程,具体取决于在流程模型中的给定条件。因为在结构范围内的活动能够重复执行,直至满足给定的条件,迭代控制结构可能会大大增加触发时间异常的风险。在本文中,我们提出两种从流程模型中展开迭代控制结构的方法。第一种方法是基于零一理论(zero-one principle)展开循环结构。第二个方法是基于在网关上分配分支概率展开循环结构。提出的方法够展开结构化循环、嵌套循环和交叉循环。因为展开后的模型将不包含任何迭代控制结构,该模型能够为模型设计者在建模阶段进行进一步的分析工作。提出的方法是基于工作流图(workflow graph)实现,因此这些方法能够兼容于建模语言,例如业务流程模型和表示法(Business Process Modelling Notation)。在文中的实验部分,已展开流程模型的执行行为与原模型之间比较是基于运行(runs)概念。实验结果展示,从原模型生成的运行能够在不包含任何循环结构的已展开BPMN模型上正确执行。

关键词: 业务流程模型, 迭代控制结构, 展开, 零一理论, 分支概率。

Abstract: Iterative control structures allow the repeated execution of tasks, activities or sub-processes according to the given conditions in a process model. Iterative control structures can significantly increase the risk of triggering temporal exceptions since activities within the scope of these control structures could be repeatedly executed until a predefined condition is met. In this paper, we propose two approaches to unravel iterative control structures from process models. The first approach unravels loops based on zero-one principle. The second approach unravels loops based on branching probabilities assigned at split gateways. The proposed methods can be used to unfold structured loops, nested loops and crossing loops. Since the unfolded model does not contain any iterative control structures, it can be used for further analysis by process designers during the modeling phase. The proposed methods are implemented based on workflow graphs, and therefore they are compatible with modeling languages such as Business Process Modelling Notation (BPMN). In the experiments, the execution behavior of unfolded process models is compared against the original models based on the concept of runs. Experimental results reveal that runs generated from the original models can be correctly executed in the unfolded BPMN models that do not contain any loops.

Key words: business process management, iterative control structure, unravelling, zero-one principle, branching probability

[1] Weske M. Adaptive workflows based on flexible assignment of workflow schemes and workflow instances. In Proc. the Enterprise-wide and Cross-enterprise Workflow Management:Concepts, Systems, Applications, October 1999, pp.42-48.
[2] Aalst W M P V D, Hofstede A H M T, Kiepuszewski B, Barros A P. Workflow patterns. Distrib. Parallel Databases, 2003, 14(1):5-51. DOI:10.1023/A:1022883727209.
[3] van derAalst W, van Hee K. Workflow Management:Models, Methods, and Systems. The MIT Press, 2004.
[4] van der Aalst W M P, Barros A P, ter Hofstede A H M, Kiepuszewski B. Advanced workflow patterns. In Proc. the 7th International Conference on Cooperative Information Systems, September 2000, pp.18-29. DOI:10.1007/107226202.
[5] Sarkar V. Optimized unrolling of nested loops. International Journal of Parallel Programming, 2001, 29(5):545- 581. DOI:10.1023/A:1012246031671.
[6] Aho A V, Ullman J D. Principles of Compiler Design. Addison-Wesley, 1977.
[7] Yu Y, Xie T, Wang X. A handling algorithm for workflow time exception based on history logs. The Journal of Supercomputing, 2013, 63(1):89-106. DOI:10.1007/s11227-010- 0543-7.
[8] Eder J, Pichler H. Duration histograms for workflow systems. In Proc. the IFIP TC8/WG8.1 Working Conference on Engineering Information Systems in the Internet Context, September 2002, pp.239-253. DOI:10.1007/978-0-387- 35614-314.
[9] Dumas M, García-Ba~nuelos L, Ho K S, Si Y W. Extended choice relation framework for workflow testing. In Proc. the 12th Symposium on Programming Languages and Software Tools, October 2011, pp.236-247.
[10] Hennessy J L, Patterson D A. Computer Architecture:A Quantitative Approach (5th edition). Morgan Kaufmann, 2011.
[11] Kukunas J. Toolchain primer. In Power and Performance:Software Analysis and Optimization, Kukunas J (ed.), Morgan Kaufmann, 2015, pp.207-239. DOI:10.1016/B978-0-12- 800726-6.00012-4.
[12] Velkoski G, Gusev M, Ristov S. The performance impact analysis of loop unrolling. In Proc. the 37th International Convention on Information and Communication Technology, Electronics and Microelectronics, May 2014, pp.307- 312. DOI:10.1109/MIPRO.2014.6859582.
[13] Cardoso J, Coutinho J, Diniz P. Source code transformations and optimizations. In Embedded Computing for High Performance:Efficient Mapping of Computations Using Customization, Code Transformations and Compilation, Cardoso J, Coutinho J, Diniz P (eds.), Morgan Kaufmann, 2017, pp.137-183. DOI:10.1016/C2015-0-00283-0.
[14] Cooper K D, Torczon L. Introduction to optimization. In Engineering a Compiler (2nd edition), Cooper K D, Torczon L (eds.), Morgan Kaufmann, 2012, pp.405-474. DOI:10.1016/C2009-0-27982-7.
[15] Huang J C, Leng T. Generalized loop-unrolling:A method for program speedup. In Proc. the 1999 IEEE Symposium on Application|Specific Systems and Software Engineering and Technology, March 1999, pp.244-248. DOI:10.1109/ASSET.1999.756775.
[16] Weinhardt M. High-level synthesis oriented restructuring of functions with while loops. In Proc. the 2019 IEEE International Parallel and Distributed Processing Symposium Workshops, May 2019, pp.115-122. DOI:10.1109/IPDPSW.2019.00029.
[17] Carminati A, Starke R A, de Oliveira R S. Combining loop unrolling strategies and code predication to reduce the worst-case execution time of real-time software. Applied Computing and Informatics, 2017, 13(2):184-193. DOI:10.1016/j.aci.2017.03.002.
[18] Dias J, Guerra G, Rochinha F, Coutinho A L G A, Valduriez P, Mattoso M. Data-centric iteration in dynamic workflows. Future Gener. Comput. Syst., 2015, 46(C):114- 126. DOI:10.1016/j.future.2014.10.021.
[19] Cao Y, Subramaniam V, Chen R. Performance evaluation and enhancement of multistage manufacturing systems with rework loops. Comput. Ind. Eng., 2012, 62(1):161-176. DOI:10.1016/j.cie.2011.09.004.
[20] Heng Z, Aiping L, Xuemei L, Liyun X, Moroni G. Modeling and performance evaluation of multistage serial manufacturing systems with rework loops and product polymorphism. Procedia CIRP, 2017, 63:471-476. DOI:10.1016/j.procir.2017.03.347.
[21] Choi I, Jung J, Mannino M, Park C. Terminability and compensatibility of cycles in business processes with a processoriented trigger. Data Knowl. Eng., 2008, 66(2):243-263. DOI:10.1016/j.datak.2008.03.002.
[22] Park C, Choi I. Management of business process constraints using BPTrigger. Comput. Ind., 2004, 55(1):29-51. DOI:10.1016/j.compind.2003.11.003.
[23] Polyvyanyy A, García-Ba~nuelos L, Weske M. Unveiling hidden unstructured regions in process models. In Proc. the Confederated International Conferences on the Move to Meaningful Internet Systems, November 2009, pp.340-356. DOI:10.1007/978-3-642-05148-7.
[24] Koehler J, Hauser R. Untangling unstructured cyclic flows|A solution based on continuations. In Proc. the 2004 OTM Confederated International Conferences on the Move to Meaningful Internet Systems, October 2004, pp.121-138. DOI:10.1007/978-3-540-30468-510.
[25] Dumas M, García-Ba~nuelos L, Polyvyanyy A. Unraveling unstructured process models. In Proc. the 2nd International Workshop on Business Process Modeling Notation, October 2010, pp.1-7. DOI:10.1007/978-3-642-16298-51.
[26] Eshuis R, Kumar A. Converting unstructured into semistructured process models. Data Knowl. Eng., 2016, 101(C):43-61. DOI:10.1016/j.datak.2015.10.003.
[27] Siavvas M, Gelenbe E. Optimum checkpoints for programs with loops. Simulation Modelling Practice and Theory, 2019, 97:Article No. 101951. DOI:10.1016/j.simpat.2019.101951.
[28] Williams M, Ossher H L. Conversion of unstructured flow diagrams to structured form. Comput. J., 1978, 21(2):161- 167. DOI:10.1093/comjnl/21.2.161.
[29] Kiepuszewski B, ter Hofstede A H M, Bussler C. On structured workflow modelling. In Proc. the 12th International Conference on Advanced Information Systems Engineering, June 2000, pp.431-445. DOI:10.1007/3-540-45140-429.
[30] Heinze T, Amme W, Moser S. Control flow unfolding of workflow graphs using predicate analysis and SMT solving. In Proc. the 5th Central-European Workshop on Services and their Composition, February 2013, pp.1-8.
[31] Heinze T, Amme W, Moser S, Gebhardt K. Guided control flow unfolding for workflow graphs using value range information. In Proc. the 4th Central-European Workshop on Services and their Composition, February 2012, pp.128- 135.
[32] Choi Y, Kongsuwan P, Joo C M, Zhao J L. Stepwise structural verification of cyclic workflow models with acyclic decomposition and reduction of loops. Data & Knowledge Engineering, 2015, 95:39-65. DOI:10.1016/j.datak.2014.11.003.
[33] van der Aalst W M P, Hirnschall A, Verbeek H M W. An alternative way to analyze workflow graphs. In Proc. the 14th International Conference on Advanced Information Systems Engineering, May 2002, pp.535-552. DOI:10.1007/3- 540-47961-937.
[34] Si Y W, Hoi K K, Biuk-Aghai R P, Fong S, Zhang D. Runbased exception prediction for workflows. J. Syst. Softw., 2016, 113(C):59-75. DOI:10.1016/j.jss.2015.11.024.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 金兰; 杨元元;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[2] 潘启敬;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[3] 王建潮; 魏道政;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[4] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[5] 黄学东; 蔡莲红; 方棣棠; 迟边进; 周立; 蒋力;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[6] 孙永强; 陆汝占; 黄小戎;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[7] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[8] 李明慧;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
[9] 段平; 蔡希尧;. A Real-Time Interprocessor Synchronization Algorithm for Communication in Distributed Computer Systems[J]. , 1987, 2(4): 292 -302 .
[10] 史维更; StephenY.H.Su;. An Online Diagnosable Fault-Tolerant Redundancy System[J]. , 1987, 2(4): 310 -321 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：