Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (1): 158-190.doi: 10.1007/s11390-020-9516-3

Special Issue: Software Systems

• Regular Paper • Previous Articles     Next Articles

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.

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] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[2] Pan Qijing;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[3] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[4] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[5] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[6] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[7] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[8] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
[9] Duan Ping; Cai Xiyao;. A Real-Time Interprocessor Synchronization Algorithm for Communication in Distributed Computer Systems[J]. , 1987, 2(4): 292 -302 .
[10] Shi Weigeng; StephenY.H.Su;. An Online Diagnosable Fault-Tolerant Redundancy System[J]. , 1987, 2(4): 310 -321 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved