基于Petri网的工作流模型的研究与仿真①

孟广学

(华北科技学院计算机学院，北京 东燕郊 101601)

0 引言

Petri网主要是通过对工作流任务之间的属性关系进行描述建立模型的一种工具，它的优点是能够充分对并发的、离散的事件进行动态方面的属性描述，通过对属性的描述利用图形化的工具进行模型的建立，再结合数学的理论和定义，进行模型算法方面的分析和评价，典型的Petri网具备以下特点:首先它是一种图形化的建模工具，具有直观、易用的优点，在资源紧张时或有冲突造成资源并发时能够形象化地描述和化解;其次，它又具有数学化的建模描述能力，结合信息论和随机过程论对系统的不确定性或随机性进行分析。

活动在执行的过程中，依据不同的执行顺序，定义四种执行过程的基本模型［1］:

1)顺序执行也称为串行执行:如图1(a)所示，多个任务分先后次序依次执行。如有任务A和B两个任务要执行，A任务执行完了再执行B任务。

2)选择执行也称为有条件的分支执行顺序:如图1(c)所示，首先对执行的条件进行判断，判断哪个任务执行的条件成立就执行哪个任务，按照条件的优先权的高低有选择的执行。

3)并行执行也可称为同时执行顺序:如图1(b)所示，两个任务同时执行或以任意的顺序进行，如任务C和任务B就是并行地执行。

4)重复执行也可称为循环执行顺序:如图1(d)所示，每个任务只要条件成立，可以循环的多次执行。

图1 工作流四种基本模型

1 工作流模型服务时间的等价分析方法

对于一个复杂的基于Petri网工作流模型直接进行等价服务时间的分析较为困难，必须依据基本的模型进行简化的处理，分别计算每种连接方式的等价服务时间，最后在计算整体模型的性能参数。

1.1 并联模型的服务时间的等价分析方法［4］

性能等价服务时间的期望值为:

1.2 选择模型的服务时间的等价分析方法［4］

1.3 串联模型等价服务时间的分析方法［4］

下面以产品销售过程为例来具体说明基于Petri网的工作流建模及性能分析过程。

2 模型的建立

首先这里涉及到的产品销售过程的用户需求，主要包括:

1)用户向公司发出订单，指出需要的计算机配置和数量，公司接收到用户的订单后根据用户提出的配置要求检查库存及价位等信息进行决策。

2)要对以上订单情况进行检查和审核，通过审核可以接受，则执行下一步，否则向用户发出通知或信函，告知结果或提出修改意见，修改订单，接着交给办事员发出反馈意见。

3)接受订单后一方面要通知用户付款，另一方面要发出生产通知。这两个过程是并行的过程。发出生产通知后要进行装配计算机然后发货此时流程结束。按照需求进行分析得出整个销售过程的流程图如图2所示。

图2 产品销售过程流程图

4)整个流程通过以下活动完成销售业务过程。

(1)用户向公司发出订单，指出需要的产品配置和数量，在Petri模型中用变迁t0表示。

(2)公司接收用户订单，在模型中用变迁t1表示。

(3)公司对用户订单进行检查，即指以下3个活动的并发过程，可用一个瞬时变迁表示:计算价格，在模型中用变迁t2表示;检查零部件库存是否满足需求，在模型中用变迁t3表示;进行配置检查，确认用户的订单技术上是否可行，在模型中用变迁t4表示。

(4)进行决策，在模型中用变迁t5表示。如果通过检查，则继续执行;如果未通过检查，则向用户发出信函，解释为什么订单不能完成，并提出修改意见，修改订单，在模型中用变迁t10表示，接着交给办事员发出反馈意见，在模型中用变迁t11表示。

(5)准备接收订单的确认通知，它就是指一方面通知用户付款，另一方面发出生产通知的两个并行过程，它本身可用一个瞬时变迁表示。通知用户付款，在模型中用变迁t8表示。

(6)用户接到通知，进行付款，在模型中用变迁t9表示。

(7)发出生产通知，在模型中用变迁t6表示。

(8)装配计算机，在模型中用变迁t7表示。

(9)发货，在模型中用变迁t12表示。

针对上面实例的系统流程图，在定义Petri网模型时，各个任务之间的先后关系用库所节点p(O)来表示;用变迁节点t矩形(□)表示系统中的任务;任务和工作流逻辑关联形式用弧(⌒)表示;圆圈中带有黑点(⊙)标记的表示执行状态。由此对工作流进行建模的实施过程中用到的变迁的含义定义如表1所示。

表1 产品销售过程工作流Petri网模型中变迁的含义

在分析系统流程图2的基础上，结合表1的定义建立系统工作流的Petri网模型如图3所示。其中假设接受订单的概率为a，修改订单的概率为1－a;当有用户向公司提交订单时，首先要接受公司的审核和检查，检查和审核的过程设为并发的活动，利用Petri网模型进行描述时，使用一个瞬时的变迁来表示;公司对提交的订单检查通过后准备接受订单时也可以用一个瞬时变迁，并发处理发出生产通知和通知用户付款这两个过程。

图3 产品销售过程工作流网模型图

3 模型的性能等价分析

3.1 petri网模型的变迁的平均延迟时间

本文研究过程中假设变迁 t0，t1，t2，t3，t4，t5，t6，t7，t8，t9，t10，t11，t12的平均延迟时间分别为:

其中延迟时间的单位为分钟。另外，对t5的分支选择处设接收订单的概率α1=0.91。

3.2 性能等价计算

性能等价计算的原则是:首先由里到外，通过性能的等价变化将复杂的结构化简到最简单，在简化模型的过程中，要依据基本的四种模型进行，首先分析模型的串联、并联、选择和循环关系的基本构成，然后根据相应的等价公式计算出整个系统相关的性能参数。经过串、并和选择的化简，得到如图4所示的模型:

图4 产品销售过程最终模型简化图

3)最后由串联公式(3)求出总的性能等价时间

计算出模型的性能等价时间以后，可以根据相应的公式计算系统的吞吐率和平均处理的任务数等性能参数。实例系统的模型中只存在一个标记，所以吞吐率是等价时间的倒数，即λ123456789101112=3.29 ×10－4(任务/每分钟)，一天内的平均处理任务数为24×60×3.29×10－4=0.474(个)。

4 仿真分析

基于Petri网的工作流模型可以使用多种方法进行仿真分析，其中ExSpect是一种比较完善的仿真工具，Expect是一个免费的编程工具语言，用来实现自动和交互式任务进行通信，而无需人的干预。

随着Expect的不断发展，其功能越来越强大，已经成为系统管理员的的一个强大助手。Expect需要Tcl编程语言的支持，使用ExSpect工具结合ExSpect语言能够有效地监控和分析业务流程。本节利用ExSpect工具及语言对上节的产品销售实例系统进行仿真设计及相应的性能分析。

下面针对以上所建立的产品销售过程的实例模型进行仿真研究;在ExSpect中建立系统的主模型main，如图5所示:

图5 主程序main的仿真模型图

上图中system节点设置为generator，check_order表示对用户订单进行检查的部分，这部分包括检查配置，检查库存数量和计算价格三个部分。handel_order表示对订单进行处理的部分，主要包括订单存在问题时修改订单和订单要求能够满足而接受订单需要交款发货两种情况。在仿真的过程中check_order和handel_order需要分别建立的模型。其中check_order检验订单的仿真模型如图6所示。

图6 check_order的仿真模型图

在图6中的处理框check中的代码是xmsg＜－order_arrived，其含义是指将order_arrived中的标志交给xmsg，仿真过程中对配置的检查，库存数量的检查和价格的计算三个部分主要体现其信息的走向，如果配置不合格或者库存不足，则给出需要修改订单的结论;如果合格，则要返回相应的信息，还要计算出价格，做出接受订单的决定。仿真结果图7给出了信息传递的方向和过程。

图7 check_order的仿真结果图

当用户的订单被检查过以后，需要根据订单的检查结果选择是接受订单还是修改订单，修改订单需要发出反馈意见，而接受订单一方面要发出付款的通知，另一方面还要发出生产或者装配的通知。仿真过程中简化模型，建立模型时考虑收到款后才进行装配产品的情况，从而建立handel_order处理订单的仿真模型如图8所示。

在仿真软件ExSpect中通过属性的设置可以得到平均时延的近似值。本节的仿真过程中使用和上一节性能等价计算中一致的假设条件。从而得出如图9的仿真结果。

图8 handel_order的仿真模型图

图9 handel_order的仿真结果图

在图9中，subrun表示仿真实验的次数;xarrivals表示一次实验中到达的标志数量，在我们的实例中表示处理的订单数量;xaverage表示对订单进行处理的平均时延，也就是我们在性能等价时间中计算出来的系统总的性能等价时间;xvariance表示平均时延的可靠性。根据上图我们得出的平均时延的近似值约为3037.644。与上节中计算的等价时间3043.277之间的误差小于1%，符合时间精度的要求。

5 结论

对复杂工作流模型进行性能方面的分析非常必要，依据实际的销售流程建立的模型非常复杂而且规模巨大，对性能的分析比较困难，必须对复杂的工作流模型依据四种基本模型进行等价的简化，根据基本模型的计算方法进行定量分析，为改进和完善模型提供合理依据。

［1］ 何建佳，徐福缘，张燕，王玉玺，何胜学.基于角色的供需网工作流建模与分析［J］.计算机应用研究，2010，(10):3813 －3815

［2］ 龙鹏飞，郑凯，林勇.基于Agent技术的工作流模型的研究与设计［J］.计算机工程与科学，2009，(01):99 －100，112

［3］ Andrews M，Anta A F，Zhang L，Zhao Wenbo.Routing forenergy minimization in the speed scaling model.Proceedings of the 29th IEEE Conference on Computer Communications(INFOCOM’10).2010，339 －345

［4］ 范玉顺.工作流管理技术基础〔M」，北京:清华大学出版社，2001

［5］ Pang Shanchen，Li Yin，He Hua，Lin Chuang.A model fordynamic business processes and process changes.Chinese Journal of Electronics，2011，20(4):632－636

［6］ 孔劼，蔡皖东.网络的联合污染模型［J］.计算机应用，2011，31(8)

［7］ W.M.P.vanderAalst.Three Good reasons for Usinga Petri－net－based Workflow management System ［J ］， In: NavatheS， WakayamaT，eds.Proeeedings of the intermational Working Conferenee on Infonnation and Proeess Integrtion in Enterprises(IPIC’96)，Camebridge，Massachusetts:Kluwer Aeademic Publishers，1996:179－201

［8］ WFMC.Wbrkflow Management Coalition temunology＆ glossary(WFMC1000)［M］，1994

［9］ WFMC.The workfiow reference model(WFMC1003)［M］，1995

［10］ 陈曦，周彦，乐晓波.匡迎春.Petri网化简新技术研究［J］.计算机工程与应用，2012，48(5)

［11］ GeorgakoPolous D，HomickM，Sheth A.An Overview of Workflow Management:From Proeess-Modeling to Wbrkflow Automation Infrastr Ueture［J］，Distributed and Parallel Database，2010，3(2):119－152

［12］ Leylnann F，Altenhuber W.Managing Business Proeesses as an Information Resouree［J］，IBM System Joumal，2009，33(2):326 －348