延迟时间Petri网的验证分析
|
摘要
延迟时间Petri网(Delay Time Petri Nets,DTPN)是一类重要的时间扩展Petri网系统,解决了其他时间扩展Petri网(如时间Petri网)在保存时间约束时所面临的困难。可调度验证的目的是验证工作流模型时间约束的合理性,对流程实例的时间可达性进行仿真。提出一种基于DTPN的时间约束工作流验证分析方法。给出了DTPN的相关定义,并结合工作流控制结构描述了变迁可触发的时间条件;提出了DTPN触发点的概念以及基于此的验证分析算法;简要分析了DTPN的特性。DTPN的研究丰富完善了现有时间Petri网体系,具有积极的意义。
Delay Time Petri Nets(DTPN)are an important kind of time-extended Petri nets. They overcome the difficulties of other time-extended Petri nets(such as Time Petri Nets)in the preservation of timing constraints. Schedulability verification is to testify the rationality of timing constraints of workflow model and to do simulation to verify the time accessibility for process instances. A novel verification analysis approach is presented for timing constraint workflows based on DTPN. Firstly, the definition of DTPN is given, and the time conditions of transition firable are described in combination with workflow structure. Then, the concept of DTPN firing point and the verification analysis algorithm based on this are proposed. Finally, the characteristics of DTPN are briefly analyzed. The research of DTPN enriches and improves the existing time-related Petri nets, which is of positive significance.
Delay Time Petri Nets(DTPN)are an important kind of time-extended Petri nets. They overcome the difficulties of other time-extended Petri nets(such as Time Petri Nets)in the preservation of timing constraints. Schedulability verification is to testify the rationality of timing constraints of workflow model and to do simulation to verify the time accessibility for process instances. A novel verification analysis approach is presented for timing constraint workflows based on DTPN. Firstly, the definition of DTPN is given, and the time conditions of transition firable are described in combination with workflow structure. Then, the concept of DTPN firing point and the verification analysis algorithm based on this are proposed. Finally, the characteristics of DTPN are briefly analyzed. The research of DTPN enriches and improves the existing time-related Petri nets, which is of positive significance.
引文
[1]Murata T.Petri nets:properties,analysis and applications[J].Proc IEEE,1977,77(4):541-580.
[2]Ramchandani C.Analysis of asynchronous concurrent system by Petri nets[J].Project Mac,1974,15(4):13-15.
[3]Zuberek W M.Timed Petri nets definitions,properties,and applications[J].Microelectronics Reliability,1991,31(4):627-644.
[4]Molloy M K.Performance analysis using stochastic Petri nets[J].IEEE Transactions on Computers,2006,C-31(9):913-917.
[5]Merlin P M,Farber D J.Recoverability of communication protocols-implications of a theoretical study[J].IEEETrans Commun,1976,24(9):1036-1043.
[6]Tsai J J P,Yang S J,Chang Y H.Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J].IEEE Transactions on Software Engineering,1995,21(1):32-49.
[7]冯复剑.时间约束工作流的可调度性分析[J].计算机工程与应用,2016,52(12):26-30.
[8]Carlier J,Chretienne P.Timed Petri net schedules[C]//Advances in Petri Nets 1988,Covers the European Workshop on Applications and Theory of Petri Nets,Zaragoza,Jun 1987:62-84.
[9]Sloan R H,Buy U.Reduction rules for time Petri nets[J].Acta Informatica,1996,33(5):687-706.
[10]Boucheneb H,Alger U,Berthelot G.Towards a simplified building of time Petri nets reachability graph[C]//International Workshop on Petri Nets and Performance Models,1993:46-47.
[11]Bonhomme P,Berthelot G,Aygalinc P,et al.Verification technique for time Petri nets[C]//IEEE International Conference on Systems,Man and Cybernetics,2004:4278-4283.
[12]宋巍,窦万春,刘茜萍.时间约束Petri网及其可调度性分析与验证[J].软件学报,2007,18(1):11-21.
[13]Juan E Y T,Tsai J J P,Murata T,et al.Reduction methods for real-time systems using delay time Petri nets[J].IEEE Transactions on Software Engineering,2001,27(5):422-448.
[14]Juan E Y T,Tsai J J P.Delay time Petri nets and net reduction[M]//Compositional verification of concurrent and real-time systems.[S.l.]:Springer US,2002:143-186.
[15]张姝,江金龙.基于DTPN的时间Petri网的组件级化简规则[J].计算机仿真,2008,25(1):105-108.
[16]Jiang J,Zhou X,Sun Y.Component-level reduction rules for time petri nets based on DTPN[J].Computer Simulation,2008,25(1):105-108.
[17]Aalst W M P V D.Three good reasons for using a Petrinet-based workflow management system[M]//Information and process integration in enterprises.Boston:Springer,1996:161-182.
[18]Berthelot G,Lri-Iie.Checking properties of nets using transformations[C]//European Workshop on Applications and Theory in Petri Nets.Berlin,Heidelberg:Springer,1985:19-40.
[19]Lee K H,Favrel J.Hierarchical reduction method for analysis and decomposition of Petri nets[J].IEEE Transactions on Systems,Man and Cybernetics,1985,15(2):272-280.
[20]Lee-Kwang H,Favrel J,Baptiste P.Generalized Petri net reduction method[J].IEEE Transactions on Systems,Man and Cybernetics,1987,17(2):297-303.
[21]Lambert J L.A structure to decide reachability in Petri nets[M].[S.l.]:Elsevier Science Publishers Ltd,1992.
[22]干梦迪,王寿光,周孟初,等.无界Petri网的可达树的综述[J].自动化学报,2015,41(4):686-693.
[23]Berthomieu B,Diaz M.Modeling and verification of time dependent systems using time Petri nets[J].IEEE Transactions on Software Engineering,1991,17(3):259-273.
[24]Hadjidj R,Boucheneb H.Efficient reachability analysis for time Petri nets[J].IEEE Transactions on Computers,2011,60(8):1085-1099.
[25]杨根科,曾建潮,孙国基.TCPN的状态可达及可调度决策空间算法[J].计算机学报,1998,21(1):34-39.
[26]杨根科,曾建潮,孙国基.TCPN的变迁弱规则特有的调度可达决策区域及算法[J].自动化学报,1999,25(4):543-547.
[27]李慧芳,李人厚.时间约束Petri网的可达性分析研究[J].计算机工程与科学,2000,22(3):60-63.
[28]吴亚丽,曾建潮,卫军胡,等.TCPN的可调度性及调度区间的约束分析[J].控制与决策,2002,17(5):522-526.
[29]庞辉,方宗德,赵勇.时间约束工作流模型的简化分析与可调度性验证[J].计算机集成制造系统,2008,14(11):2217-2230.
[30]李鹏,李勋,顾庆,等.TCPN的组合可调度分析[J].计算机科学,2008,35(1):290-293.
[2]Ramchandani C.Analysis of asynchronous concurrent system by Petri nets[J].Project Mac,1974,15(4):13-15.
[3]Zuberek W M.Timed Petri nets definitions,properties,and applications[J].Microelectronics Reliability,1991,31(4):627-644.
[4]Molloy M K.Performance analysis using stochastic Petri nets[J].IEEE Transactions on Computers,2006,C-31(9):913-917.
[5]Merlin P M,Farber D J.Recoverability of communication protocols-implications of a theoretical study[J].IEEETrans Commun,1976,24(9):1036-1043.
[6]Tsai J J P,Yang S J,Chang Y H.Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J].IEEE Transactions on Software Engineering,1995,21(1):32-49.
[7]冯复剑.时间约束工作流的可调度性分析[J].计算机工程与应用,2016,52(12):26-30.
[8]Carlier J,Chretienne P.Timed Petri net schedules[C]//Advances in Petri Nets 1988,Covers the European Workshop on Applications and Theory of Petri Nets,Zaragoza,Jun 1987:62-84.
[9]Sloan R H,Buy U.Reduction rules for time Petri nets[J].Acta Informatica,1996,33(5):687-706.
[10]Boucheneb H,Alger U,Berthelot G.Towards a simplified building of time Petri nets reachability graph[C]//International Workshop on Petri Nets and Performance Models,1993:46-47.
[11]Bonhomme P,Berthelot G,Aygalinc P,et al.Verification technique for time Petri nets[C]//IEEE International Conference on Systems,Man and Cybernetics,2004:4278-4283.
[12]宋巍,窦万春,刘茜萍.时间约束Petri网及其可调度性分析与验证[J].软件学报,2007,18(1):11-21.
[13]Juan E Y T,Tsai J J P,Murata T,et al.Reduction methods for real-time systems using delay time Petri nets[J].IEEE Transactions on Software Engineering,2001,27(5):422-448.
[14]Juan E Y T,Tsai J J P.Delay time Petri nets and net reduction[M]//Compositional verification of concurrent and real-time systems.[S.l.]:Springer US,2002:143-186.
[15]张姝,江金龙.基于DTPN的时间Petri网的组件级化简规则[J].计算机仿真,2008,25(1):105-108.
[16]Jiang J,Zhou X,Sun Y.Component-level reduction rules for time petri nets based on DTPN[J].Computer Simulation,2008,25(1):105-108.
[17]Aalst W M P V D.Three good reasons for using a Petrinet-based workflow management system[M]//Information and process integration in enterprises.Boston:Springer,1996:161-182.
[18]Berthelot G,Lri-Iie.Checking properties of nets using transformations[C]//European Workshop on Applications and Theory in Petri Nets.Berlin,Heidelberg:Springer,1985:19-40.
[19]Lee K H,Favrel J.Hierarchical reduction method for analysis and decomposition of Petri nets[J].IEEE Transactions on Systems,Man and Cybernetics,1985,15(2):272-280.
[20]Lee-Kwang H,Favrel J,Baptiste P.Generalized Petri net reduction method[J].IEEE Transactions on Systems,Man and Cybernetics,1987,17(2):297-303.
[21]Lambert J L.A structure to decide reachability in Petri nets[M].[S.l.]:Elsevier Science Publishers Ltd,1992.
[22]干梦迪,王寿光,周孟初,等.无界Petri网的可达树的综述[J].自动化学报,2015,41(4):686-693.
[23]Berthomieu B,Diaz M.Modeling and verification of time dependent systems using time Petri nets[J].IEEE Transactions on Software Engineering,1991,17(3):259-273.
[24]Hadjidj R,Boucheneb H.Efficient reachability analysis for time Petri nets[J].IEEE Transactions on Computers,2011,60(8):1085-1099.
[25]杨根科,曾建潮,孙国基.TCPN的状态可达及可调度决策空间算法[J].计算机学报,1998,21(1):34-39.
[26]杨根科,曾建潮,孙国基.TCPN的变迁弱规则特有的调度可达决策区域及算法[J].自动化学报,1999,25(4):543-547.
[27]李慧芳,李人厚.时间约束Petri网的可达性分析研究[J].计算机工程与科学,2000,22(3):60-63.
[28]吴亚丽,曾建潮,卫军胡,等.TCPN的可调度性及调度区间的约束分析[J].控制与决策,2002,17(5):522-526.
[29]庞辉,方宗德,赵勇.时间约束工作流模型的简化分析与可调度性验证[J].计算机集成制造系统,2008,14(11):2217-2230.
[30]李鹏,李勋,顾庆,等.TCPN的组合可调度分析[J].计算机科学,2008,35(1):290-293.