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

《基于Petri网工作流模型的分析(1).doc》由会员分享，可在线阅读，更多相关《基于Petri网工作流模型的分析(1).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于Petri网工作流模型的分析晋蓓，冯卫兵（1. 西北大学计算机科学系，陕西 西安710069；2. 西安科技大学基础部，陕西 西安710054）摘要：通过模型分析发现所描述的过程定义中的设计错误，以便对业务过程重构提供正确的指导和科学的依据。首先将信牌驱动模型转化为Petri网，接着将Petri网进行必要化简，最后对化简后的Petri网进行死锁等分析。关键词： 工作流模型；Petri网；死锁 中图分类号：TP911.7 文献标识码：A 文章编号：1000-274X(2004)0068-07工作流模型的分析是指采用各种方法（包括理论模型、模拟、测量方法），对工作流模型的内部行为进行分析计算，

2、使得工作流模型在理论上是正确和有效的。虽然现在绝大部分的工作流产品都提供模型性能分析的仿真功能，但由于复杂性等原因，很难找到一种有效的算法对模型进行分析与验证。本文在总结模型分析研究成果现状的基础上，针对目前模型验证方法存在的不足，总结了Petri网模型分析中的一些图形化简规则，针对企业经营过程模型的特点并利用文中提出的模型正确性标准，提出了一种具有完备性和高效率的工作流模型的模型验证方法分析。1相关概念定义1信牌驱动模型的静态结构: 多元式称为信牌驱动模型的静态结构（以下简称信牌驱动模型），其中：1) 表示扩展的信牌驱动模型所涉及的所有数据，其值域用表示；2) 表示活动集合，和分别称为功能函

3、数和后继函数。被定义为根据出函数定义，参见下边的定义；3）表示信牌箱集合；4），称为的流关系，其中和分别称为入关系和出关系。对出关系定义一个出函数：表示与相关的出函数，被称为的后继函数。5） 是惟一的活动，称为开始活动，；6） 是一个活动的集合，称为结束活动，；7） 称为转移的权重；8）是（注意：中不包含）的一种划分即是的另一种划分，即规定。若，则；若，则；如果，则被称为简单元素。一个信牌驱动的工作流模型，开始活动只能是一个，但是结束活动可以是多个。为了描述问题方便，有时我们也将信牌驱动的模型简写成。定义2真假信牌，设。1）上的一个多重集是一个映射 (自然数集合)，令表示上所有多重集的集合；2

4、）表示多重集且表示多重集且表示多重集 且。定义3活动的SPLIT，设为信牌驱动模型，令，称集合为出弧的集合。表示出弧的个数。与所联系的信牌箱称为的后信牌箱。或者或者和称为的SPLIT类型，记为。定义4活动的JOIN：设为信牌驱动模型，令，称集合为入弧的集合。表示入弧的个数。与联系的信牌箱称为的前信牌箱。或者或者或者或者，和称为的类型，记为。定义 5 确定的Petri网1。本文的讨论均在有限网的基础上进行，以下不再说明。定义6非确定Petri网系统。参见文献1。定义7非确定变迁的发生结果。参见文献1。2将信牌驱动模型转化为Petri网Petri网有很强的表达能力，其描述能力与Turing机等价，

5、因此所有典型的流程都可用Petri网予以描述。本节探讨将工作流模型中的各种基本控制结构自动地转化为Petri网的规则。由于工作流模型是由这些基本的控制结构组合而成的复杂网络，所以工作流模型就可转化为一个Petri网模型2。下面研究典型流程到Petri网结构转换的对应规则（为讨论方便，在没有特别说明的情况下，在转换过程中对应的信牌箱与位子的容量相同，对应连线的权值相同）转化原则：转化最重要的是要遵守原系统的原有逻辑顺序，把对象的操作映射为Petri网模型中的位子；工作流中的活动即Petri中的转移；工作流中的开始活动即Petri网中的无输入转移和该转移的输出位子，它受外界因素的控制，自动产生激活

6、整个Petri网；工作流中的结束标记即Petri中的无输出库所得变迁和单变迁的输入库所；工作流中的同步节点即Petri中的多输人、单输出变迁及该变迁的库所3。1）开始流程：结束流程的转化如图1（a）所示。2）结束流程：结束流程的转化如图1（b）所示。 （a） (b)图1 信牌驱动模型向Petri网的转化Fig. 1 The transform from the Xinpai-driven model to Petri net 3）顺序流程：在信牌驱动模型中，将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构。4）竞争流程：在扩展的信牌驱动模型中，竞争流程可表示为。

7、其中： ；。将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构，其中，是与对应的元素，。5）无条件分支：它是一种并发执行的结构。在信牌驱动模型中，并行流程可表示为，其中： |。将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的Petri网结构。其中：是与对应的变迁，是与对应的位子（见图2 ）。 图2 信牌驱动模型向Petri网的转化Fig. 2 The transform from the Xinpai-driven model to Petri net6）分支流程：在扩展的信牌驱动模型中，分支流程可表示为，其中：。根据它的语义，可构造一个Petri

8、网结构与之等价。其中：是与对应的变迁是与 对应的变迁；是与对应的位子是与对应的位子。例1图3（a）所表示的分支结构可转化为图3（b）的Petri网控制结构。 （a） （b）图3 信牌驱动模型向Petri网的转化Fig. 3 The transform from the Xinpai-driven model to Petri net7）多分支流程（OR-SPLIT）：在扩展的信牌驱动模型中，多分支流程可表示为。其中：。根据它的语义，将其中的活动和信牌箱分别对应为变迁和位子，就可构造一个与之等价的非确定Petri网结构，其中：是与对应的非确定变迁是与对应的位子。8）XOR-合并流程：在扩展的信牌

9、驱动模型中，XOR-合并流程可表示为，其中：。根据它的语义，可以构造一个Petri网结构与其等价。其中：是与对应的变迁；是与的每个前信牌箱对应的变迁；是与对应的位子是与对应的位子。例2(a)表示的信牌网结构可转化为 (b)的Petri网结构。 （a） (b)图4 信牌驱动模型向Petri网的转化Fig. 4 The transform from the Xinpai-driven model to Petri net注意：它如果在同步区中出现，该活动的出弧要加权。9）AND-同步流程：在扩展的信牌驱动模型中，AND-同步流程可表示为。其中：。根据它的语义，将其中的活动和信牌箱分别对应为变迁和位

10、子，就可构造一个与之等价的非确定Petri网结构。其中：是与对应的变迁是与对应的位子 。（在同步区中，设SS为同步区的“门”，则F还应加入，它的权值为，详见同步区的描述）。10）OR-同步流程：在扩展的信牌驱动模型中，它一定要有一个OR-SPLIT与之对应（可以是配对，也可以是局焦点。这里选用聚焦点）。为了保证在同步区避免多流交叉问题，这里规定：只有当OR-JOIN节点执行之后，它的聚焦点才能再次执行。11）T-AND合并：它和AND合并的含义类似，不过它只能出现在非同步区内，而AND合并只能出现在同步区内。所以，它的转化与AND合并相识。12）循环流程：循环流程就是有一条向前的转移线所构成的

11、控制结构。向Petri网转化时，无论是在同步区还是在非同步区中的循环，只要按照上面讨论的各种分支和合并的规则进行即可4。3Petri网的化简3.1伪位置化简法定义8在一个带标识M的Petri网中，定义表示的输入元素的集合；表示的输出元素的集合。表示代中的元素个数。如果，且满足， ；，那么称位子伪位子。 化简规则1如果一个确定的Petri网存在一个伪位子，则可以删除这个位子及相连的所有的弧（证明见文献5），如图5所示。 t p (a) 含有一伪位子p (b) 消除伪位子p图5 伪位置化简法的例子Fig 5 The example of reducation 定义9 在一个带标识M的Petri网中

12、，如果，且满足，； ，那么称位子伪转移。3.2伪转移化简法化简规则2如果一个确定的Petri网存在一个伪转移，则可以删除这个转移及相连的所有的弧。3.3等价位子化简法定义10在一个带标识M的Petri网中，如果存在 ，且满足=；=；=， 那么称位子，是等价位子。 化简规则3如果一个确定的Petri网存在等价的转移，则可以删除这些等价转移中任意一个及相连的所有的弧。3.4转移合并化简法 该方法指的是当两相邻的转移及中间的位子满足一定的条件时，可以删除中间位子，并将两个位子合并成一个转移5。此外，还有等价转移化简法，因与等价位子化简法相似，不再赘述。若原网是有界的，那么转化后也是有界的；若原网是无

13、界的，那么转化后也是无界的；若原网是活的，则转化后也是活的；若原网存在死锁，则转化后也存在死锁。即按照上边的5条规则转化，性质保持不变。4死锁检测算法定义11在Petri网中，对于，设=，= ，则死锁定义可以描述为位子的非空子集，且满足 定义12 若非空子集是死锁的，而，不是死锁的，则称为最小死锁。其他的定义参见文献6。图6是死锁的检测算法。图6 死锁的检测Fig.6 The check of deadlock5结语工作流模型是工作流管理系统的基础和核心，模型分析有助于发现所描述的过程定义中的设计错误，以便对业务过程重构提供正确的指导和科学的依据。本文首先将信牌驱动模型转化为Petri网，接着

14、将Petri网进行必要的化简，大大简化了模型分析的难度，在此基础上对化简后的Petri网进行死锁等分析，方法简单实用。参考文献：1 王斌君. 工作流过程模型的层次研究及其分析D. 西安：西北大学计算机科学系, 2002.2 潘启澍, 姜 兵. 基于Petri网的工作流建模技术及应用J. 清华大学学报（自然科学版）, 2000, 40( 9): 86-89.3 岳晓丽, 杨 斌, 郝克刚. 信牌驱动式工作流计算模型J. 计算机研究与发展, 2000, 37(12): 1 513- 1 519.4 van der AALST W M P. Petri-net-based workflow mana

15、gement softwareA . SHETH A. Proceedings of the NFS Workshop on Workflow and Process Automation in Information SystemsC. Georgia： Athens , 1996, 114118.5 张明明，杨文龙. Petri网化简与实现 A . 杨文龙. 基于Petri网的并发软件开发方法及其支持工具的研究C. 北京: 科学技术文献出版社, 1993. 55-65.6 任爱华, 唐培和, 雒力旭, 等. 基于Petri网的并发系统死锁检测方法A. 杨文龙. 基于Petri网的并发软件开

16、发方法及其支持工具的研究C. 北京: 科学技术文献出版社, 1993. 6681.(编 辑曹大刚)Workflow model analysisJIN Bei FENG Wei-bing(Institute of Software Engineering, Northwest University, Xian 710069, China)Abstract: The default of process design is found by Workflow model Analysis. The proper direction and scientific gist are provided

17、. The Xinpai-driven model is transformed to Petri net and normal Petri net, and then to general Petri net. The characters of extending Xinpai-driven model are researched in Petri net space. The deadlock in Petri net predigested is analysised. Key words: workflow model Petri net deadlock作 者 简 介晋 蓓，女，陕西韩城人，生于1973年10月。2000年至2003年于西北大学计算机系进修计算机软件与理论专业，并攻读硕士学位。主要从事计算机软件理论中的系统学研究工作。近期在西北大学学报(自然科学版)增刊上发表有“Java AWT中的设计模式举例”、“建立在工作流基础上的回退解决方案”、“浅谈软件项目管理”等学术论文。10