基于Petri网的工作流过程建模和时间性能分析

肖作斌,孙　鹏,张智慧,李小春

(1.空军工程大学 信息与导航学院,陕西 西安　710077;2.北京信息职业技术学院 电子工程系,北京　100015)



基于Petri网的工作流过程建模和时间性能分析

肖作斌1,孙鹏1,张智慧2,李小春1

(1.空军工程大学 信息与导航学院,陕西 西安710077;2.北京信息职业技术学院 电子工程系,北京100015)

摘要介绍了基于Petri网的工作流建模技术,并针对一个复杂的企业生产经营活动的流程构建了一个简化灵活的模型,利用随机Petri网的性能分析方法对建立的模型进行了时间性能分析。结果表明,文中的性能分析方法可对复杂的模型进行有效地简化分析。

关键词工作流;Petri网;工作流网;时间性能

工作流是现实世界的业务过程全部或部分在计算机应用环境下自动执行的表示形式,其使得多个参与者之间按照预先定义的规则自动地传递文档、信息或任务,从而促使总体业务目标得以实现。而工作流模型的建立是工作流执行的前提和基础,工作流建模的目的就是将业务流程形式化,便于其在计算机上进行分析和处理。

目前国内外学者提出了各种各样的工作流建模方法[1],其中基于Petri网的建模技术具有直观的图形表示、形式化的语义、状态和事件的显示表示以及丰富的数学分析技术等特点,能够满足工作流模型的建模需求,现有的基于Petri网工作流建模方法有很多,如时间、着色、分层等[2-4]方法。在此基础上,研究人员针对工作流模型的性能评价技术也开展了相关研究,如采用扩展的时间Petri网模型来进行工作流模型的时间性能计算和分析[5];通过线性推理来估计时间性能的上下界[6];运用遍历网中所有路径的方法来计算时间性能[7]等。

本文介绍了Petri网和工作流网的基本概念以及从Petri网到工作流网的执行映射。为降低时间性能分析的复杂度,本文采用了随机Petri网的性能分析方法对建立的模型进行简化分析。经实例分析,可证明该分析方法对于复杂工作流模型的时间性能分析是简便有效的。

1基于Petri网的工作流网

1.1　定义

Petri网最早在20世纪60年代由Carl Adam Petri提出。因其有着坚实严谨的数学基础、完全形式化的语义、强大的表达能力、直观的图形表示等特点,Petri网成为工作流建模和分析的主要工具。Petri 网的定义如下[8]

定义1一个四元组PN=(P,T,F,M0)是Petri网,当且仅当

(1)P∩T=∅

(2)P∪T≠∅

(3)F⊆P×T∪T×P

(4)dom(F)∪cod(F)=P∪T

工作流过程的网模型中含有两个特殊的库所,其中一个表示过程的开始,另外一个表示过程的结束,在此分别称其为开始库所和结束库所,用i和o表示。针对工作流网模型的这一特点对Petri网进行相应的限制就得到了工作流网,由此工作流状态的变化便能用工作流网清晰的描述出来。在Petri网的基础上,工作流网的定义如下:

定义2Petri网系统PN=(P,T,F,M0)是一个工作流网(WF_net)[9]的充分必要条件是:

(1)存在一个源库所i∈P,使得i=∅。

(2)存在一个终止库所o∈P,使得o=∅。

(3)对于每个结点x∈P∪T,x都在从i到o的一条路径上。

满足上述条件的Petri网称为一个工作流网,记为WFN(WorkFlow Net)。

定义3一个连续时间随机Petri网(SPN)是个六元组(P,T,F,W,M0,λ),其中P={p1,p2,…,pm}是库所的非空有限集合,T={t1,t2,…,tm}是变迁的非空有限集合,W∶F→{0,1,2,…}是有向弧函数,M0∶P→{0,1,2,…}是初始标志,λ={λ1,λ2,…,λm}是变迁平均实施速率集合。

1.2　Petri网到工作流网的映射

工作流管理联盟(WFMC)在工作流模型中定义了4种基本路由结构:顺序路由、并行路由、选择路由和循环路由,复杂的工作流模型均由这4种基本的流控制结构复合而成。因此,在利用Petri网理论对工作流模型进行建模时,首先,4种基本结构进行Petri网建模,然后对复杂工作流模型的基本结构进行分析,最终建立基于Petri网的工作流模型。

在每一种路由结构进行建模前,首先引入4种构造模块,分别是:并行发散(AND_split)、同步聚合(AND_join)、选择发散(OR_split)和选择聚合(OR_join),其在工作流网基本组件中经常出现,因此用统一的符号分别表示这4种构造模块,如图1所示。

图1　工作流网基本组件中的构造模块

将4种构造模块应用到路由结构的建模中,得到工作流网的4种基本组件[10]:顺序组件、并行组件、选择组件以及循环组件,如图2所示。在此,用变迁表示活动,用库所表示状态,“○·”表示启动库所,其中的“·”表示托肯。

图2　工作流网的基本组件

2建模实例和模型时间性能分析

2.1　建模实例

结合一个复杂的企业生产经营活动流程,利用基于Petri网的建模技术进行建模。图3给出了企业生产经营活动的详细流程,然后针对该流程建立了工作流网模型,如图4所示。对于图4中各个变迁的描述如下:t1为客户需求,t2为审核订单,t3为计算成本,t4为检查库存,t5为修改订单,t6为确认订单,t7为制订计划,t8为自制,t9为外协,t10为采购,t11为检验,t12为国产,t13为进口,t14为装配,t15为发货。

图3　企业生产经营活动流程

图4　工作流网模型

2.2　模型分析

工作流系统的时间性能是衡量一个工作流过程优劣的重要指标,时间性能将直接影响工作流系统的实际可行性。由于现实中多数工作流系统的模型变迁时延是服从指数分布函数的,所以在这里利用 随机Petri网的性能分析方法对建立的模型进行时间性能分析,其性能等价公式可对复杂的系统进行性能等价化简,降低分析的复杂性。下面给出工作流模型的顺序、并行、选择、循环这4种基本结构的性能等价公式[11]。

接下来对图4中建立的的工作流网模型进行时间性能分析。表l给出了图3中变迁的延时时间和实施概率,其中延时时间的单位为单位时间。在进行性能分析之前先对建立的模型进行改动和化简,由于t8和t9处都要到达库所p9,然后也都将经过变迁t11,所以做出改动后如图5所示,通过分析模型对其进行化简,得到的化简模型如图6所示,其中变迁t2、t3、t4、t6等价化简为tA,变迁t8、t11等价化简为tB,变迁t9、t11等价化简为tC,变迁t10、t12、t13等价化简为tD,变迁t14、t15等价化简为tE。

表1　变迁的延时时间和概率分配

图5　改动后的工作流网模型

图6　化简模型

这样,通过使用4种结构的性能等价公式,由内到外、由繁至简,不断地对模型进行等价化简,最终求出了整个系统的性能等价时间。

3结束语

本文利用基于Petri网的建模技术对复杂的企业生产经营活动流程进行建模,构建出一个简化模型,并应用4种基本结构的性能等价公式对模型进行时间性能分析。建模与性能分析表明,基于Petri网的建模技术在为复杂的业务流程进行建模时优势明显,同时本文的性能分析方法在对复杂模型进行性能分析时是简便可行的。

参考文献

[1]陈广智,潘嵘,李磊.工作流建模技术综述及其研究趋势[J].计算机科学,2014,41(S1):11-17.

[2]傅作为,乐晓波,王慧英.加权的时间Petri 网工作流模型研究[J].计算机工程与应用,2014,50(15),55-58.

[3]龚凌玲,钟勇.基于着色Petri网的工作流模型研究[J].计算机应用,2008,28(6):291-294.

[4]Jiang Hang,Ding Xiangqian.Modeling of hierarchcal petri net-based workflow[C].Wuhan:Control and Industrial Engineering(CCIE),2011.

[5]姜浩,董逸生.一种基于扩展时间Petri 网的工作流时间性能评价方法[J].计算机研究与发展,2005,42(5):849-855.

[6]刘婷,林闯,刘卫东.基于时间Petri网的工作流系统模型的线性推理[J].电子学报,2002,30(2):153-156.

[7]李建强,范玉顺.基于Petri网的工作流模型性能评价方法[J].计算机应用,2001,21(6):4-6.

[8]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,2005.

[9]Vander Aalst W,Van Hee K.Workflow management:model,methods and system[M].Beijing:Tsinghua Press,2004.

[10]Vander Aalst WMP.The application of petri nets to workflow management[J].Journal of Circuits,Systems,and Computers,1998,8(1):22-66.

[11]林闯.随机Petri网和系统性能评价[M].北京:清华大学出版社,2005.

Workflow Process Modeling Based on Petri Nets and Its Time Performance Analysis

XIAO Zuobin1,SUN Peng1,ZHANG Zhihui2,LI Xiaochun1

(1.School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China;2.Department of Electronic Engineering,Beijing Information Technology Institute,Beijing 100015,China)

AbstractWorkflow modeling technique has been the basis for the entire business process implementation,so selecting efficient modeling techniques for achieving actual complex business processes is particularly important.The time performance evaluation is also an important aspect in the evaluation of workflow models.Firstly,the workflow modeling techniques based on Petri nets are introduced.And then a complex process of production and operation is combined to construct a simplified and flexible model.The average time performance is analyzed using the stochastic Petri net.The results show that a complex model can be analyzed effectively and simply by the proposed performance analysis method.

Keywordsworkflow;Petri net;workflow net;time performance

中图分类号TP317.1

文献标识码A

文章编号1007-7820(2015)10-044-05

doi:10.16180/j.cnki.issn1007-7820.2015.10.013

作者简介:肖作斌(1990—),男,硕士研究生。研究方向:工作流管理。E-mail:xiaozuobin123@126.com

基金项目:中国博士后基金资助项目(2014M562585)

收稿日期:2015-06-03