有色时间Petri网与随机Petri网应用研究
|
摘要
Petri网是一种适合于描述异步并发现象的系统模型,是离散事件系统建模的一种强有力工具,但是在使用基本Petri网来为复杂系统建模时会出现“节点爆炸”问题,有色时间Petri网(CTPN)是克服该问题的有效途径之一。多范式建模通过耦合和转换以整合不同方法建立的模型来综合利用多种形式化方法,可以全面准确地描述建模对象,可以大大的减轻仿真建模的工作量、提高整个仿真过程的效率。依据多范式建模理论,本文提出了基于规则化描述方法的CTPN建模方法,同时发挥两种建模方法的优势,有利于全面准确地反映系统的设计内容,并以汽车车身控制系统为例为其建立模型,为复杂系统建模和模拟验证提供一定的借鉴。
工作流管理技术是90年代初兴起的软件技术,工作流是一个业务过程的全部或部分自动执行,为了实现工作流管理功能,我们必须将业务过程从现实世界中抽象出来,并用一种形式化方法对其进行描述,其结果称为是工作流模型。Petri网作为一种图形化的数学建模工具,适合于工作流领域的建模需求,提出了基于广义随机Petri网(GSPN)的工作流建模方法,将工作流模型映射为广义随机工作流网模型,并运用可达图法对工作流正确性和可靠性进行检查;利用GSPN与马尔可夫链的同构关系,采用GSPN和马尔可夫链相结合的工作流性能分析方法,为工作流性能的有效评估提供理论依据;并通过实例验证该方法的有效性。
Petri Net is a formal, graphical, executable technique for the specification and analysis of concurrent, discrete-event dynamic systems. However, when modeling complicated control systems, basic Petri net may lead to the problem of node number explosion. Colored Timed Petri Net(CTPN) is a way to solve this problem. Multi-paradigm modeling, concerned with the coupling of and transformation between models described in different formalisms, can give a representation of models in diverse formalisms, at different levels of abstraction, and the behavior-conserving transformation between the formalisms is demonstrated. So modeling of CTPN derived from rule description method, which takes advantages of two modeling methods, is presented. And also the method is illustrated through modeling process of auto-body control system, which will help to model, analyze and simulate for complicated systems.
Workflow management techniques were developed in early 1990s. Workflow is the automation of a business process in whole or part. To achieve the function of workflow management, the business process must be abstracted from the real world and described by a kind of formal method. The result is workflow model. As a kind of graphical and mathematical modeling tools, Petri Net is applicable to the modeling requirement of workflow. A method of modeling for workflow based on Generalized Stochastic Petri Net (GSPN) is proposed, the workflow definition of Workflow Management Coalition is mapped to generalized stochastic workflow net. The validity and reliability is checked using reachable graph method. By utilizing the equivalence relation between GSPN and Markov chain, a method of combining GSPN and Markov chain is used to analyze the performance of workflow. The effectiveness of this method is verified by an application case.
工作流管理技术是90年代初兴起的软件技术,工作流是一个业务过程的全部或部分自动执行,为了实现工作流管理功能,我们必须将业务过程从现实世界中抽象出来,并用一种形式化方法对其进行描述,其结果称为是工作流模型。Petri网作为一种图形化的数学建模工具,适合于工作流领域的建模需求,提出了基于广义随机Petri网(GSPN)的工作流建模方法,将工作流模型映射为广义随机工作流网模型,并运用可达图法对工作流正确性和可靠性进行检查;利用GSPN与马尔可夫链的同构关系,采用GSPN和马尔可夫链相结合的工作流性能分析方法,为工作流性能的有效评估提供理论依据;并通过实例验证该方法的有效性。
Petri Net is a formal, graphical, executable technique for the specification and analysis of concurrent, discrete-event dynamic systems. However, when modeling complicated control systems, basic Petri net may lead to the problem of node number explosion. Colored Timed Petri Net(CTPN) is a way to solve this problem. Multi-paradigm modeling, concerned with the coupling of and transformation between models described in different formalisms, can give a representation of models in diverse formalisms, at different levels of abstraction, and the behavior-conserving transformation between the formalisms is demonstrated. So modeling of CTPN derived from rule description method, which takes advantages of two modeling methods, is presented. And also the method is illustrated through modeling process of auto-body control system, which will help to model, analyze and simulate for complicated systems.
Workflow management techniques were developed in early 1990s. Workflow is the automation of a business process in whole or part. To achieve the function of workflow management, the business process must be abstracted from the real world and described by a kind of formal method. The result is workflow model. As a kind of graphical and mathematical modeling tools, Petri Net is applicable to the modeling requirement of workflow. A method of modeling for workflow based on Generalized Stochastic Petri Net (GSPN) is proposed, the workflow definition of Workflow Management Coalition is mapped to generalized stochastic workflow net. The validity and reliability is checked using reachable graph method. By utilizing the equivalence relation between GSPN and Markov chain, a method of combining GSPN and Markov chain is used to analyze the performance of workflow. The effectiveness of this method is verified by an application case.
引文
[1]郑大中,赵千川.离散事件动态系统[M].北京:清华大学出版社2005:72-80
[2]Vangheluwe HLM,de Lara J,Mosterman PJ(2002).An Introduction to Multi-Paradigm Modeling and Simulation.Proc.of the AI,Simulation and Planning in High Autonomy Systems Conf.(AIS2002),Lisboa,Portugal,April 2002,pp 9-20.
[3]韩江洪,郑淑丽,陆阳等.离散事件控制系统规则化描述方法的研究[J].合肥工业大学学报(自然科学版),2005,28(9):1081-1084.
[4]韩江洪,魏振春,张本宏等.总线式车身控制系统的规则化建模方法[J].汽车工程,2006,28(12):1121-1124.
[5]范玉顺.工作流管理技术基础-实现企业业务过程重组、过程管理与过程自动化的核心技术[M].北京:清华大学出版社、施普林格出版社,2001:29-49.
[6]罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.
[7]林闯,李雅娟,单志广.基于随机Petri网的系统性能评价[J].清华大学学报(自然科学版),2003,43(4):475-479.
[8]林闯.随机Petri网和系统性能评价[M].北京:清华大学出版社,2005:19-35.
[9]High-level Petri Nets Concepts,Definitions and Graphical Notation[S].Final Draft International Standard ISO/IEC 15909,Version 4.7.3,2002,10.
[10]吴哲辉.Petri网导论[M].机械工业出版社,2006.
[11]Mosterman,P.and Vangheluwe,H..Computer automated multi paradigm modeling in control system design.In Andras Varga,editor,IEEE International Symposium on Computer-Aided Control System Design,IEEE Computer Society Press,September 2000.pages 65-70.
[12]Chen Liu.Simulation Implemention Based On Multi-DEVS for Petri Net.Society of Computer Modeling and Simulation,2004.
[13]唐俊,张明清,刘建峰.离散事件系统规范DEVS研究[J],计算机仿真,2004,21(6):62-64.
[14]王维平,朱一凡.状态机嵌入DEVS的组合建模方法研究[J].国防科技大学学报2005,27(5):56-61.
[15]Georgakopolous D,Hornick M,Sheth A.An overview of workflow management:from process modeling to workflow automation infrastructure.Distributed and Parallel Databases,1995,3(2):119-152.
[16]Leymann F,Altenhuber W.Managing business processes as an information resource.IBM System s Journal,1994,33(2):326-348.
[17]Vander Aalst WMP.Using interval timed colored Petri nets to calculate performance bounds[J].Lecture Notes in Computer Science,1994, 794:425-444.
[18]李建强,范玉顺.基于Petri网的工作流模型性能分析方法[J].计算机应用,2001,21(6):4-6.
[19]Chiola G,Marsan A,Balbo G,et al.Generalized stochastic Petri nets:a definition at the net level and its implications[J].IEEE Transactions on Software Engineering,1993,19(2):89-107.
[20]Molly M K.Performance analysis using stochastic Petri nets[J].IEEE Transactions on Computer,1982,31(9):913-917.
[21]Wang Jiacun.Timed Petri nets-theory and application[M].Boston:Kluwer Academic Publishers,1999.
[22]Kommunikation mit Automaten.Petri,C.A.,Bonn:Institut f(u|¨)r Instrumentelle Mathematik,Schriften des IIM Nr.2,1962.
[23]张维明.信息系统建模技术与应用[M].北京:电子工业出版社,1997:162-164.
[24]Zurawski,R,MengChu Zhou.Petri Nets and Industrial Applications:A Tutorial.Industrial Electronics,IEEE Transactions on,Volume:41,Issue:6,1994,(10):567-583.
[25]吴文渊,曾振柄.Petri网系统的可达性分析Reachability of Petri Net[J],系统仿真学报,2005,17(z1):17-26
[26]吴维敏,董利达,王肖等.离散事件系统的混合型Petri网控制器Combined Petri Net Controller for Discrete Event Systems[J].自动化学报,Sept 2003,29(5):681-688.
[27]C.A.Petri,Nets,time and space,Theoretical Computer Science,v.153n.1-2,p.3-48,Jan.8,1996[doi〉10.1016/0304-3975(95)00116-6].
[28]吴哲辉.有界Petri网的活性和公平性的分析与实现[J],计算机学报,1989,12(04):267-278.
[29]Jensen K.Colored Petri Nets:Basic Concepts,Analysis Methods and Practical Use[C].Springer Verlag,1997.
[30]B.E.Bauskar and B.Mikolajczak,2006,”Abstract Node Method for Integration of Object Oriented Design with Colored Petri Nets”,Proceedings of the Third International Conference on Information Technology.pp.680-687.
[31]S.J.H.Yang,K.F.R.Liu,S.Lin,J.Lee,and W.T.Huang,Dec,1997“Object-Oriented Development of a Petri Nets Modeling and Analysis System,” NSC'97,pp.D73-D78,Taichung,Taiwan.
[32]REYES A,YU H,KELLEHER G,et al.Integrating Petri nets and hybrid heuristic search for the scheduling of FMS[J].Computers in Industry,2002,47(1):123-138.
[33]翟正利,吴哲辉,杨扬.时间Petri网模拟能力的研究[J].计算机科学,2006,33(4):234-239.
[34]W.M.P.vander Aalst.Interval Timed Petri Nets and their analysis.Computing Science Notes 91/09,Eindhoven University of Technology,EinDhoven,1991.
[35]Merlin P,Faber D J,Recoverability of communication protocols,IEEE Transactions on Communication,1976,24:1036-1043.
[36]Berthomieu B,Diaz M.Modeling and Verification of Time Dependent Systems Using Time Petri Nets.IEEE Transaction on Software Engineering,1993,17(3):259-273.
[37]Barreto R,Cavalcante S,Maciel P.A Time Petri Net Approach for Finding Pre-runtime Schedules in Embedded Hard Real-time Systems.Proc.of ICDCSW,2004:846-851.
[38]Portinale L.Exploiting t-invariant analysis in diagnostic reasoning on a Petri net model.In:Application and Theory of Petri Nets Berlin:Spinger-Verlag,1993.339-356.
[39]Koh I,DiCesare F.Synthesis rules for colored Petri nets and their application to automated manufacturing systems[C/OL]//Proceedings of the 1991 IEEE International Symposium on Intelligence control,Arlington,Virginia,U.S.A,Augustl3-15,1991:152-157.
[40]罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.
[41]Workflow Management Coalition.Workflow management coalition terminology and glossary.Technical Report,WfMC-TC-1011,Brussels:Workflow Management Coalition,1996.
[42]Rusinkiewicz M,Sheth A.Specification and execution of transactional workflows.In:Won Kimed.Modern Database Systems:The Object Model,Interoperability,and Beyond.Reading,MA:Addison Wesley Publishing Company,1995.
[43]Alonso G,Agrawal D,Abbadi E Aet al.Functionality and limitations of current workflow management system s.1997.
[44]Ellis C A,Nutt G J.Modeling and enactment ofworkflow system s.In:Marsan A ed.Application and Theory of Petri Nets.Lecture Notes in Computer Science 691,Berlin:Springer-Verlag,1993.1-16
[45]Zuberekw M.Performance evaluation using unbound timed Petri nets[C].Proc.of the Third International Workshop on Petri Nets and Performance Models.Washington IEEE Computer Society,1989:180-186.
[46]罗建强,韩玉启,姜涛,刘利群.基于GSPN的供应链产品成套性建模与分析[J].系统仿真学报,2007,19(22):5264-5268.
[2]Vangheluwe HLM,de Lara J,Mosterman PJ(2002).An Introduction to Multi-Paradigm Modeling and Simulation.Proc.of the AI,Simulation and Planning in High Autonomy Systems Conf.(AIS2002),Lisboa,Portugal,April 2002,pp 9-20.
[3]韩江洪,郑淑丽,陆阳等.离散事件控制系统规则化描述方法的研究[J].合肥工业大学学报(自然科学版),2005,28(9):1081-1084.
[4]韩江洪,魏振春,张本宏等.总线式车身控制系统的规则化建模方法[J].汽车工程,2006,28(12):1121-1124.
[5]范玉顺.工作流管理技术基础-实现企业业务过程重组、过程管理与过程自动化的核心技术[M].北京:清华大学出版社、施普林格出版社,2001:29-49.
[6]罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.
[7]林闯,李雅娟,单志广.基于随机Petri网的系统性能评价[J].清华大学学报(自然科学版),2003,43(4):475-479.
[8]林闯.随机Petri网和系统性能评价[M].北京:清华大学出版社,2005:19-35.
[9]High-level Petri Nets Concepts,Definitions and Graphical Notation[S].Final Draft International Standard ISO/IEC 15909,Version 4.7.3,2002,10.
[10]吴哲辉.Petri网导论[M].机械工业出版社,2006.
[11]Mosterman,P.and Vangheluwe,H..Computer automated multi paradigm modeling in control system design.In Andras Varga,editor,IEEE International Symposium on Computer-Aided Control System Design,IEEE Computer Society Press,September 2000.pages 65-70.
[12]Chen Liu.Simulation Implemention Based On Multi-DEVS for Petri Net.Society of Computer Modeling and Simulation,2004.
[13]唐俊,张明清,刘建峰.离散事件系统规范DEVS研究[J],计算机仿真,2004,21(6):62-64.
[14]王维平,朱一凡.状态机嵌入DEVS的组合建模方法研究[J].国防科技大学学报2005,27(5):56-61.
[15]Georgakopolous D,Hornick M,Sheth A.An overview of workflow management:from process modeling to workflow automation infrastructure.Distributed and Parallel Databases,1995,3(2):119-152.
[16]Leymann F,Altenhuber W.Managing business processes as an information resource.IBM System s Journal,1994,33(2):326-348.
[17]Vander Aalst WMP.Using interval timed colored Petri nets to calculate performance bounds[J].Lecture Notes in Computer Science,1994, 794:425-444.
[18]李建强,范玉顺.基于Petri网的工作流模型性能分析方法[J].计算机应用,2001,21(6):4-6.
[19]Chiola G,Marsan A,Balbo G,et al.Generalized stochastic Petri nets:a definition at the net level and its implications[J].IEEE Transactions on Software Engineering,1993,19(2):89-107.
[20]Molly M K.Performance analysis using stochastic Petri nets[J].IEEE Transactions on Computer,1982,31(9):913-917.
[21]Wang Jiacun.Timed Petri nets-theory and application[M].Boston:Kluwer Academic Publishers,1999.
[22]Kommunikation mit Automaten.Petri,C.A.,Bonn:Institut f(u|¨)r Instrumentelle Mathematik,Schriften des IIM Nr.2,1962.
[23]张维明.信息系统建模技术与应用[M].北京:电子工业出版社,1997:162-164.
[24]Zurawski,R,MengChu Zhou.Petri Nets and Industrial Applications:A Tutorial.Industrial Electronics,IEEE Transactions on,Volume:41,Issue:6,1994,(10):567-583.
[25]吴文渊,曾振柄.Petri网系统的可达性分析Reachability of Petri Net[J],系统仿真学报,2005,17(z1):17-26
[26]吴维敏,董利达,王肖等.离散事件系统的混合型Petri网控制器Combined Petri Net Controller for Discrete Event Systems[J].自动化学报,Sept 2003,29(5):681-688.
[27]C.A.Petri,Nets,time and space,Theoretical Computer Science,v.153n.1-2,p.3-48,Jan.8,1996[doi〉10.1016/0304-3975(95)00116-6].
[28]吴哲辉.有界Petri网的活性和公平性的分析与实现[J],计算机学报,1989,12(04):267-278.
[29]Jensen K.Colored Petri Nets:Basic Concepts,Analysis Methods and Practical Use[C].Springer Verlag,1997.
[30]B.E.Bauskar and B.Mikolajczak,2006,”Abstract Node Method for Integration of Object Oriented Design with Colored Petri Nets”,Proceedings of the Third International Conference on Information Technology.pp.680-687.
[31]S.J.H.Yang,K.F.R.Liu,S.Lin,J.Lee,and W.T.Huang,Dec,1997“Object-Oriented Development of a Petri Nets Modeling and Analysis System,” NSC'97,pp.D73-D78,Taichung,Taiwan.
[32]REYES A,YU H,KELLEHER G,et al.Integrating Petri nets and hybrid heuristic search for the scheduling of FMS[J].Computers in Industry,2002,47(1):123-138.
[33]翟正利,吴哲辉,杨扬.时间Petri网模拟能力的研究[J].计算机科学,2006,33(4):234-239.
[34]W.M.P.vander Aalst.Interval Timed Petri Nets and their analysis.Computing Science Notes 91/09,Eindhoven University of Technology,EinDhoven,1991.
[35]Merlin P,Faber D J,Recoverability of communication protocols,IEEE Transactions on Communication,1976,24:1036-1043.
[36]Berthomieu B,Diaz M.Modeling and Verification of Time Dependent Systems Using Time Petri Nets.IEEE Transaction on Software Engineering,1993,17(3):259-273.
[37]Barreto R,Cavalcante S,Maciel P.A Time Petri Net Approach for Finding Pre-runtime Schedules in Embedded Hard Real-time Systems.Proc.of ICDCSW,2004:846-851.
[38]Portinale L.Exploiting t-invariant analysis in diagnostic reasoning on a Petri net model.In:Application and Theory of Petri Nets Berlin:Spinger-Verlag,1993.339-356.
[39]Koh I,DiCesare F.Synthesis rules for colored Petri nets and their application to automated manufacturing systems[C/OL]//Proceedings of the 1991 IEEE International Symposium on Intelligence control,Arlington,Virginia,U.S.A,Augustl3-15,1991:152-157.
[40]罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.
[41]Workflow Management Coalition.Workflow management coalition terminology and glossary.Technical Report,WfMC-TC-1011,Brussels:Workflow Management Coalition,1996.
[42]Rusinkiewicz M,Sheth A.Specification and execution of transactional workflows.In:Won Kimed.Modern Database Systems:The Object Model,Interoperability,and Beyond.Reading,MA:Addison Wesley Publishing Company,1995.
[43]Alonso G,Agrawal D,Abbadi E Aet al.Functionality and limitations of current workflow management system s.1997.
[44]Ellis C A,Nutt G J.Modeling and enactment ofworkflow system s.In:Marsan A ed.Application and Theory of Petri Nets.Lecture Notes in Computer Science 691,Berlin:Springer-Verlag,1993.1-16
[45]Zuberekw M.Performance evaluation using unbound timed Petri nets[C].Proc.of the Third International Workshop on Petri Nets and Performance Models.Washington IEEE Computer Society,1989:180-186.
[46]罗建强,韩玉启,姜涛,刘利群.基于GSPN的供应链产品成套性建模与分析[J].系统仿真学报,2007,19(22):5264-5268.