一种工作流网的自动生成算法
|
摘要
针对工作流网人工建模容易出错、工作流分析方法缺乏大规模测试案例等问题,提出了一种自动构建工作流网的生成算法.该算法通过随机节点分组、全连接和最少连接、AND和OR类型转换等方式,自动生成具有自由选择性、安全性和无环性质的工作流网.算法最坏情况下的时间复杂度为O(mn/k),其中m为库所数,n为变迁数,k为库所分组数.同时,基于Matlab平台研制工作流网生成工具,可快速生成无环、自由选择和安全的工作流实例,为工作流分析方法提供了不同规模的测试数据.
Aiming at the problems on constructing workflow nets by hand and lacking large-scale test cases for workflow analysis methods, this paper proposed an automatic algorithm for generating workflow nets. The algorithm produces free choice,safe and acyclic workflow nets by grouping of nodes, full connection and least connection, and type conversion between AND and OR node groups. The time complexity of the algorithm is O(mn/k) in the worst case, where m is the number of places, n is the number of transitions, and k is the number of place groups. Finally, a generation tool of workflow nets based on Matlab is developed. It can quickly generate different scales of workflow instances with the above properties, and provide abundant test data for the verification of workflow analysis methods.
Aiming at the problems on constructing workflow nets by hand and lacking large-scale test cases for workflow analysis methods, this paper proposed an automatic algorithm for generating workflow nets. The algorithm produces free choice,safe and acyclic workflow nets by grouping of nodes, full connection and least connection, and type conversion between AND and OR node groups. The time complexity of the algorithm is O(mn/k) in the worst case, where m is the number of places, n is the number of transitions, and k is the number of place groups. Finally, a generation tool of workflow nets based on Matlab is developed. It can quickly generate different scales of workflow instances with the above properties, and provide abundant test data for the verification of workflow analysis methods.
引文
[1]Wil van der Aalst,Kees van Hee,Aalst,Hee.工作流管理-模型、方法和系统[M].王建民,闻立杰,译.北京:清华大学出版社,2004:22~48
[2]Claude Girault,Rudiger Valk,Girault,et al.系统工程Petri网:建模、验证与应用指南[M].王生原,余鹏,霍金健,译.北京:电子工业出版社,2005:4~55
[3]Pan L,Ding Z J,Zhou M C.A Configurable State Class Method for Temporal Analysis of Time Petri Nets[J].IEEE Transactions on Systems Man&Cybernetics Systems,2014,44(4):482~493
[4]Rodriguez M A,Buyya R.A taxonomy and survey on scheduling algorithms for scientific workflows in Iaa S cloud computing environments[J].Concurrency&Computation Practice&Experience,2017,29
[5]Sba?Z,Guerfel R.CTL Model Checking of Web Services Composition based on Open Workflow Nets Modeling[J].International Journal of Service Science Management Engineering&Technology,2016,7(1):27~42
[6]Zhang W W,Beaubouef T,Ye H.Statechart:A Visual Language for Workflow Specification[J].International Journal of Computer Theory&Engineering,2012:921~925
[7]Shukla N,Keast J E,Ceglarek D.Improved workflow modelling using role activity diagram-based modelling with application to a radiology service case study[J].Comput Methods Programs Biomed,2014,116(3):274~98
[8]Romani Farid Ibrahim.Transactional Workflow Technique for Distributed Transaction Processing[J].International Journal of Soft Computing,2017,12:343~350
[9]范玉顺,吴澄.基于协调理论的工作流建模方法[J].计算机集成制造系统,2001,7(4):1~6
[10]Rodríguez-Fernández V,Gonzalez-Pardo A,Camacho D.Automatic Procedure Following Evaluation Using Petri Net-Based Workflows[J].IEEETransactions on Industrial Informatics,2018,14(6):2748~2759
[11]Femmam M,Kazar O,Kahloul L,et al.Labelled evolutionary Petri nets/genetic algorithm based approach for workflow scheduling in cloud computing[J].International Journal of Grid and Utility Computing,2018,9(2):157~169
[12]Tiplea F L,Leahu I.The Reversible Released Form of Petri Nets and Its Applications to Soundness of Workflow Nets[J].IEEE Transactions on Systems Man&Cybernetics Systems,2016,46(2):303~312
[13]M.La Rosa,W.M.P.van der Aalst,M.Dumas,and F.P.Milani.Business process variability modeling:A survey[J].ACM Computing Surveys,2017,50(1):1~45.
[14]Ouyang Y X,Zhang X,Hou Y R.Method of translation from workflow process model to workflow-net[J].Computer Integrated Manufacturing Systems,2004,10(8):908~913
[15]Hee K M V,Sidorova N,Werf J M V D.Business Process Modeling Using Petri Nets[M].Transactions on Petri Nets and Other Models of Concurrency.Springer Berlin Heidelberg,2013:116~161
[16]Salimifard K,Wright M.Petri Net based modelling of workflow systems:an overview[J].European Journal of Operational Research,2001,134(3):664~676
[17]庞善臣.一种基于资源约束的工作流建模及分析方法[J].电子学报,2012,40(8):1497~1502
[18]曾庆田,鲁法明,刘聪,等.基于Petri网的跨组织应急联动处置系统建模与分析[J].计算机学报,2013,36(11):2290~2302
[19]Aalst W V D,Weijters T,Maruster L.Workflow Mining:Discovering Process Models from Event Logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128~1142
[20]Suriadi S,Andrews R,Hofstede A H M T,et al.Event log imperfection patterns for process mining[J].Information Systems,2017,64(C):132~150
[21]W.M.P.van der Aalst.Process Mining:Data Science in Action[M].Springer-Verlag,Berlin,2016
[22]Kalnins A,Vitolins V.Use of UML and Model Transformations for Workflow Process Definitions[J].Computer Science,2006
[23]Agarwal B.Some Rules to Transform Activity Diagrams into Colored Petri Nets[J].International Journal of Recent Technology&Engineering,2012,1(5):51~56
[24]Stremersch G,Boel R K.Structuring Acyclic Petri Nets for Reachability Analysis and Control[J].Discrete Event Dynamic Systems,2002,12(1):7~41
[2]Claude Girault,Rudiger Valk,Girault,et al.系统工程Petri网:建模、验证与应用指南[M].王生原,余鹏,霍金健,译.北京:电子工业出版社,2005:4~55
[3]Pan L,Ding Z J,Zhou M C.A Configurable State Class Method for Temporal Analysis of Time Petri Nets[J].IEEE Transactions on Systems Man&Cybernetics Systems,2014,44(4):482~493
[4]Rodriguez M A,Buyya R.A taxonomy and survey on scheduling algorithms for scientific workflows in Iaa S cloud computing environments[J].Concurrency&Computation Practice&Experience,2017,29
[5]Sba?Z,Guerfel R.CTL Model Checking of Web Services Composition based on Open Workflow Nets Modeling[J].International Journal of Service Science Management Engineering&Technology,2016,7(1):27~42
[6]Zhang W W,Beaubouef T,Ye H.Statechart:A Visual Language for Workflow Specification[J].International Journal of Computer Theory&Engineering,2012:921~925
[7]Shukla N,Keast J E,Ceglarek D.Improved workflow modelling using role activity diagram-based modelling with application to a radiology service case study[J].Comput Methods Programs Biomed,2014,116(3):274~98
[8]Romani Farid Ibrahim.Transactional Workflow Technique for Distributed Transaction Processing[J].International Journal of Soft Computing,2017,12:343~350
[9]范玉顺,吴澄.基于协调理论的工作流建模方法[J].计算机集成制造系统,2001,7(4):1~6
[10]Rodríguez-Fernández V,Gonzalez-Pardo A,Camacho D.Automatic Procedure Following Evaluation Using Petri Net-Based Workflows[J].IEEETransactions on Industrial Informatics,2018,14(6):2748~2759
[11]Femmam M,Kazar O,Kahloul L,et al.Labelled evolutionary Petri nets/genetic algorithm based approach for workflow scheduling in cloud computing[J].International Journal of Grid and Utility Computing,2018,9(2):157~169
[12]Tiplea F L,Leahu I.The Reversible Released Form of Petri Nets and Its Applications to Soundness of Workflow Nets[J].IEEE Transactions on Systems Man&Cybernetics Systems,2016,46(2):303~312
[13]M.La Rosa,W.M.P.van der Aalst,M.Dumas,and F.P.Milani.Business process variability modeling:A survey[J].ACM Computing Surveys,2017,50(1):1~45.
[14]Ouyang Y X,Zhang X,Hou Y R.Method of translation from workflow process model to workflow-net[J].Computer Integrated Manufacturing Systems,2004,10(8):908~913
[15]Hee K M V,Sidorova N,Werf J M V D.Business Process Modeling Using Petri Nets[M].Transactions on Petri Nets and Other Models of Concurrency.Springer Berlin Heidelberg,2013:116~161
[16]Salimifard K,Wright M.Petri Net based modelling of workflow systems:an overview[J].European Journal of Operational Research,2001,134(3):664~676
[17]庞善臣.一种基于资源约束的工作流建模及分析方法[J].电子学报,2012,40(8):1497~1502
[18]曾庆田,鲁法明,刘聪,等.基于Petri网的跨组织应急联动处置系统建模与分析[J].计算机学报,2013,36(11):2290~2302
[19]Aalst W V D,Weijters T,Maruster L.Workflow Mining:Discovering Process Models from Event Logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128~1142
[20]Suriadi S,Andrews R,Hofstede A H M T,et al.Event log imperfection patterns for process mining[J].Information Systems,2017,64(C):132~150
[21]W.M.P.van der Aalst.Process Mining:Data Science in Action[M].Springer-Verlag,Berlin,2016
[22]Kalnins A,Vitolins V.Use of UML and Model Transformations for Workflow Process Definitions[J].Computer Science,2006
[23]Agarwal B.Some Rules to Transform Activity Diagrams into Colored Petri Nets[J].International Journal of Recent Technology&Engineering,2012,1(5):51~56
[24]Stremersch G,Boel R K.Structuring Acyclic Petri Nets for Reachability Analysis and Control[J].Discrete Event Dynamic Systems,2002,12(1):7~41