基于Petri网工作流模型的分析(1)

西北大学学报(自然科学网络版)2004年5月，第2卷，第5期ScienceJournalofNorthwestUniversityOnlineMay2004，Vol.2，No.5________________________收稿日期：2004-02-03审稿人：葛玮，男，西北大学计算机科学系副教授基于Petri网工作流模型的分析晋蓓，冯卫兵（1.西北大学计算机科学系，陕西西安710069；2.西安科技大学基础部，陕西西安710054）摘要：通过模型分析发现所描述的过程定义中的设计错误，以便对业务过程重构提供正确的指导和科学的依据。首先将信牌驱动模型转化为Petri网，接着将Petri网进行必要化简，最后对化简后的Petri网进行死锁等分析。关键词：工作流模型；Petri网；死锁中图分类号：TP911.7文献标识码：A文章编号：1000-274X(2004)0068-07工作流模型的分析是指采用各种方法（包括理论模型、模拟、测量方法），对工作流模型的内部行为进行分析计算，使得工作流模型在理论上是正确和有效的。虽然现在绝大部分的工作流产品都提供模型性能分析的仿真功能，但由于复杂性等原因，很难找到一种有效的算法对模型进行分析与验证。本文在总结模型分析研究成果现状的基础上，针对目前模型验证方法存在的不足，总结了Petri网模型分析中的一些图形化简规则，针对企业经营过程模型的特点并利用文中提出的模型正确性标准，提出了一种具有完备性和高效率的工作流模型的模型验证方法分析。1相关概念定义1信牌驱动模型的静态结构:多元式),,,,,,;,)(,,(JOINSPLIT0DAAWAAFTAFTATPf称为信牌驱动模型的静态结构（以下简称信牌驱动模型），其中：1)D表示扩展的信牌驱动模型所涉及的所有数据，其值域用Dˆ表示；2)A表示活动集合，121),,(,GGGaAa和2G分别称为功能函数和后继函数。1G被定义为,22DD2G根据出函数定义，参见下边的定义；23）T表示信牌箱集合；4）TAATF，称为TP的流关系，其中AT和TA分别称为入关系和出关系。对出关系定义一个出函数FO：AFOAATFDTA，。表示与A相关的出函数，被称为A的后继函数。5）AA0是惟一的活动，称为开始活动，0*A；6）AAf是一个活动的集合，称为结束活动，*fA；7）NFW:称为转移的权重；8）SPLITA是A（注意：A中不包含fAA,0）的一种划分},,,{XORORANDAAA即,XORORANDAAAAAAAAJOINXORORAND,是A的另一种划分},,,,{and-tasyncXORORANDAAAAA，即,and-tasyncXORANDORAAAAA规定AAAAAAand-tasyncXORANDOR。若1*A，则AAAND；若1*A，则ANDAA；如果1**AA，则A被称为简单元素。一个信牌驱动的工作流模型，开始活动只能是一个，但是结束活动可以是多个。为了描述问题方便，有时我们也将信牌驱动的模型简写成);,(FTATP。定义2真假信牌，设},{FTTF。1）TF上的一个多重集是一个映射NTFf:(自然数集合)，令)(TF表示TF上所有多重集的集合；2）T1表示多重集1)(1TT且FTF1;0)(1表示多重集0)(1TF且0;1)(1FF表示多重集0)(0T且0)(0F。定义3活动的SPLIT，设),,,,,,;,(JOINSPLIT0DAAWAAFTATPf为信牌驱动模型，令Aa，称集合}),(,),{(FbaTbbaas为a出弧的集合。sa表示a出弧的个数。与sa所联系的信牌箱称为a的后信牌箱。ANDAa或者ORAa或者ANDOR,XOR、Aa和XOR称为a的SPLIT类型，记3为SPLITa。定义4活动的JOIN：设),,,,,,;,(JOINSPLIT0DAAWAAFTATPf为信牌驱动模型，令Ab，称集合}),(,),{(FbaTababJ为b入弧的集合。bJ表示b入弧的个数。与bJ联系的信牌箱称为b的前信牌箱。AbAND或者AbOR或者AbXOR或者Abasync或者Abandt，ANDOR、和AND-TASYNCXOR、、称为b的JOIN类型，记为bJOIN。定义5确定的Petri网[1]。本文的讨论均在有限网的基础上进行，以下不再说明。定义6非确定Petri网系统。参见文献[1]。定义7非确定变迁的发生结果。参见文献[1]。2将信牌驱动模型转化为Petri网Petri网有很强的表达能力，其描述能力与Turing机等价，因此所有典型的流程都可用Petri网予以描述。本节探讨将工作流模型中的各种基本控制结构自动地转化为Petri网的规则。由于工作流模型是由这些基本的控制结构组合而成的复杂网络，所以工作流模型就可转化为一个Petri网模型[2]。下面研究典型流程到Petri网结构转换的对应规则（为讨论方便，在没有特别说明的情况下，在转换过程中对应的信牌箱与位子的容量相同，对应连线的权值相同）转化原则：转化最重要的是要遵守原系统的原有逻辑顺序，把对象的操作映射为Petri网模型中的位子；工作流中的活动即Petri中的转移；工作流中的开始活动即Petri网中的无输入转移和该转移的输出位子，它受外界因素的控制，自动产生激活整个Petri网；工作流中的结束标记即Petri中的无输出库所得变迁和单变迁的输入库所；工作流中的同步节点即Petri中的多输人、单输出变迁及该变迁的库所[3]。1）开始流程：结束流程的转化如图1（a）所示。2）结束流程：结束流程的转化如图1（b）所示。（a）4(b)图1信牌驱动模型向Petri网的转化Fig.1ThetransformfromtheXinpai-drivenmodeltoPetrinet3）顺序流程：在信牌驱动模型中，将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构。4）竞争流程：在扩展的信牌驱动模型中，竞争流程可表示为)},{,(tA。其中：aA{}*ta；}),{(Aaat。将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构)},{,(FsT，其中，ttT{是与Aa对应的元素}，}),{(TttsF。5）无条件分支：它是一种并发执行的结构。在信牌驱动模型中，并行流程可表示为),,(FTA，其中：})},,{(}*{}{ANDANDANDANDANDTtAΑtAFAAAttTaA；，；|。将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构),,(FST。其中：ttT{是与Aa对应的变迁}，ssS{是与Tt对应的位子}),{(},SsTtstF}（见图2）。图2信牌驱动模型向Petri网的转化Fig.2ThetransformfromtheXinpai-drivenmodeltoPetrinet6）分支流程：在扩展的信牌驱动模型中，分支流程可表示为),,(TA，其中：；}{XORaA}),{(}*,{XORXORXORXORTtAaxaAaattT；。根据它的语义，可构造一个Petri网结构),,(FST与之等价。其中：ttTTTT{1,21是与AaXOR对应的变迁''{2},ttT}是与Tt对应的变迁}；ssSSSS{1,21是与AaXOR对应的位子ssS{2},}是与Tt对应的位子5),{(}11),{(};tsSsTtstF),{(}21stTtSs}22SsTt}。例1图3（a）所表示的分支结构可转化为图3（b）的Petri网控制结构。（a）（b）图3信牌驱动模型向Petri网的转化Fig.3ThetransformfromtheXinpai-drivenmodeltoPetrinet7）多分支流程（OR-SPLIT）：在扩展的信牌驱动模型中，多分支流程可表示为),,(TA。其中：}),{(}*,{}{}{ORORORORORORTtAataAaattTattTaA；；；。根据它的语义，将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的非确定Petri网结构),,(FST，其中：NNttT{是与AaOR对应的非确定变迁ssS{}；}是与Tt对应的位子SsTtstFNN),{(}；}。8）XOR-合并流程：在扩展的信牌驱动模型中，XOR-合并流程可表示为),,(TA，其中：}),{(,*}{XORXORXORXORXORTtAaatAaattTaA；；。根据它的语义，可以构造一个Petri网结构),,(FST与其等价。其中：ttTTTT{1,21是与aXOR对应的变迁}；ttT{2是与aXOR的每个前信牌箱对应的变迁}；ssSSSS{1,21是与Tt对应的位子ssS{2}；是与aXOR对应的位子),{(}22),{(}21),{(};tsTtSsstTtSstsF6}12TtSs。例2(a)表示的信牌网结构可转化为(b)的Petri网结构。（a）(b)图4信牌驱动模型向Petri网的转化Fig.4ThetransformfromtheXinpai-drivenmodeltoPetrinet注意：它如果在同步区中出现，该活动的出弧要加权。9）AND-同步流程：在扩展的信牌驱动模型中，AND-同步流程可表示为),,(TA。其中：TtAAAtAAAttTAAANDANDANDANDAND},{(},*{}{；；。根据它的语义，将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的非确定Petri网结构),,(FST。其中：ttT{是与AAAND对应的变迁ssS{}；}是与Tt对应的位子；}}),{(SsTttsF。（在同步区中，设SS为同步区的“门”，则F还应加入}),{(TttSS，它的权值为1*t，详见同步区的描述）。10）OR-同步流程：在扩展的信牌驱动模型中，它一定要有一个OR-SPLIT与之对应（可以是配对，也可以是局焦点。这里选用聚焦点）。为了保证在同步区避免多流交叉问题，这里规定：只有当OR-JOIN节点执行之后，它的聚焦点才能再次执行。11）T-AND合并：它和AND合并的含义类似，不过它只能出现在非同步区内，而AND合并只能出现在同步区内。所以，它的转化与AND合并相识。12）循环流程：循环流程就是有一条向前的转移线所构成的控制结构。向Petri网转化时，无论是在同步区还是在非同步区中的循环，只要按照上面讨论的各种分支和合并的规则进行即可[4]。3Petri网的化简3.1伪位置化简法7定义8在一个带标识M的Petri网};,{FTSPN中，定义)xITSx（：表示x的输入元素的集合；)(xO表示x的输出元素的集合。)(#x表示代x中的元素个数。如果TtSs,，且满足}{)()(tsIsO，),(#tp),(#pt；)(sM),(#pt；))((#tI2))((#tO，那么称位子s伪位子。化简规则1如果一个确定的Petri网存在一个伪位子，则可以删除这个位子及相连的所有的弧（证明见文献[5]），如图5所示。tp(a)含有一伪位子p(b)消除伪位子p图5伪位置化简法的例子Fig5Theexampleofreducation定义9在一个带标识M的Petri网};,{FTSPN中，如果TtSs,，且满足}{)()(stItO，),(#tp1),(#pt；))((#sI2))((#sO，那么称位子t伪转移。3.2伪转移化简法化简规则2如果一个确定的Petri网存在一个伪转移，则可以删除这个转移及相连的所有的弧。3.3等