b基于Petri网的工作流优化分析

文章编号:1003-207(2005)03-0050-06

基于Petri 网的工作流优化分析

周江波,凌　鸿,胥正川

(复旦大学管理学院,上海　200433)

摘　要:工作流管理技术是实现企业业务过程重组、过程管理与过程自动化的核心技术。在工作流参考模型中,工作流验证和优化是过程定义工具的重要组成部分。在综述相关研究论文和经典Petri 网理论的基础上,提出了基于Petri 网的工作流合理性验证算法和过程优化算法。最后通过保险索赔过程的优化实例,验证了工作流优化算法的有效性。

关键词:工作流管理;Petri 网;验证;优化中图分类号:C931 文献标识码:A

收稿日期:2004-09-18;修订日期:2005-05-23基金项目:国家863/CIM S 主题资助项目(2002AA413210)作者简介:周江波(1982-),男(汉族),湖北黄冈人,复旦大学管

理学院信息管理与信息系统系硕士生,研究方向:企业过程重组、工作流管理.

1　引言

工作流是一类能够完全或者部分自动执行的经营过程,它根据一系列过程规则、文档、信息和任务能够在不同的执行者之间进行传递与执行[1]。按照工作流管理联盟(WfMC )提出的工作流参考模型(Workflow Reference M odel ),过程定义工具(Pro -cess Definition Tools )是整个工作流管理系统的基础,其质量直接影响了整个工作流管理系统WfWS (Wo rkflow Management System )的应用范围和对变化的适应能力[2]。目前,活跃在市场上的工作流产品不下百余种。比较有代表性的是Staffware Plc 公司的Staffw are 、IBM 公司的MQseries .Actio n Tech -nologies 公司的Action Wo rkflow 等,但这些产品基本上都不具备自动优化功能,只有一部分具有一定的工作流验证功能[3]

。工作流验证和优化是工作流参考模型中过程定义工具的主要组成部分,进行这方面的研究对理论和实践都有重要的意义。

W .M .P .van dr Aalst 首先把Petri 网应用于工作流建模,并论证了Petri 网可以表述工作流管理联盟规定的各种工作流[4]。我们以Petri 网作为建模语言,还因为它具有以下优点:(1)由于Petri 网图形表达方式的自然性和准确性,使得模型看起来直观且易理解;(2)Petri 具有许多分析工具可以借用,如

可达图、标识树、不变量等;(3)Petri 具有形式化语义,有强大的数学理论支持,这使得可以对建立好的模型进行仿真、分析和验证(4)独立了提供商,Petri

网不属于某个公司的软件包,不会因为厂商并购而消失[4,5]。

本文首先综述了工作流验证和优化已有的研究成果,然后在经典Petri 网理论基础上,分别提出了工作流验证和优化算法,然后通过对保险索赔案例的实例分析,定量的说明了优化的效果,从而也证实了算法的有效性。

2　文献综述

在工作流验证方面,WASIM SADIQ 等以有向无环图作为建模语言,使用五种归纳法则(终结符归约、顺序归约、邻接归约、闭合归约和重叠归约)来难证工作流的正确性。如果一个工作流过程是正确的,最终可以使用上面五种归约法则归约为空,反之,该过程存在语义上的错误[6]。但李红臣等在文献[7]中对归约法则的完备性提出了置疑,甚至给出了归约法错误验证的过程。赵磊等在文献[8]中提出了基于状态空间的验证方法,但是目前大多数工作流建模都是基于语言而不是基于活动的,应用存在很大的局限性。Henry H .Bi 等在文献[9]中提出了工作流验证的过程逻辑方法,可检查出过程中的死锁。但并没有解决验证中的同步丢失、活锁等问题。W .M .P .van der Aalst 在文献[3,4]中给出了工作流网的定义并就其特性进行了深入的研究,但并没有明确的提出工作流合理性验证算法。

在工作流优化方面,大多是把过程优化放在具

第13卷　第3期2005年 6月 中国管理科学Chinese Journal of Management Science

Vol .13,No .3

June ,　2005DOI :10.16381/j .cn ki .issn 1003-207x .2005.03.009

体某一行业或领域来研究,如给出了车间作业的优化[10],不带行业特性的过程优化研究较少。谢玉凤、史美林等在条件化有向图的基础上,通过分析工作流的复杂度和执行时间,提出了协商节点和相似节点合并规则;还讨论了删除冗余节点的规则[11]。何辉、黄丽华等利用带有参数的有向超图为企业过程建模,然后根据最小化等同超图理论过程优化的三条规则,用于简化企业过程,识别和减少非增值活动[12]。这两种方法主要是通过识别和删除冗余节点或非增值活动来实现优化,而本文旨在对企业业务过程中出现频率最高的顺序过程通过并行和合并来实现优化。

3　Petri网及工作流合理性验证

工作流验证的目的是在过程设计时检验工作流的正确性,避免执行时出现异常。过程异常包括死锁(deadlock)、死任务(deadtask)、活锁(livelock)等。在工作流模型实际实施之前,探测其中可能存在的各种过程异常可以降低工作流运行时的停产、检查和修复的成本,具有重大的经济意义。

1962年,德国科学家Carl Adam Petri在其博士论文《用自动机通信》中首次提出了Petri网理论。经过40多年的发展,经典Petri网(Classical Petri Net)已被Petri本人和其追随者们以多种不同的方式进行了扩展,例如层次Petri网(Hierarchy Petri Net),颜色Petri网(Colo red petri Net),时间Petri网(Time/Timed Petri Net),随机Petri网(Stochastic etri Net)。在过程建模、分析和优化领域,Petri网已成为强有力的工具之一。文献[3,13]对经典Petri 网理论和建模路由有详细的介绍。

定义(工作流网WF-net)Petri网PN=(P,T.F)是WF-net(工作流网),当且仅当:

(1)存在一个开始库所i∈P,使得·i=;

(2)存在一个汇结库所o∈P,使得o·=;而且

(3)每一个节点x∈P∪T都位于从i到o的一条路径上。[3]

定理　一个工作流网(WF-net)是合理的,当且仅当(PN,i)是活的而且是有界的[4]。

从定理中我们可以得出,一个Petri网是一个合理的工作流网必须满足以下条件:

(1)Petri网存在唯一的开始库所i和唯一的汇结库所o;

(2)Petri网中的每一个变迁,都能从开始状态i 到达该变迁的就绪状态;

(3)状态o是从状态i可达的唯一最终状态,且结束时其中会有且仅有一个标记,而其他库所里没有标记。

条件1保证每一个过程有一个明确的开始时间和结束时间;条件2保证过程中的每一个任务(变迁)都是可能实施的,不存在不可达的变迁;条件3保证了过程中不会存在死锁(在到达结束状态之前发生了阻塞)、活锁(把过程带入无休止的循环)和过程结束时没有标记停留在非汇结库所之中。通过以上的分析,下面给出验证工作流的合理性算法。

(1)把工作流图中的每一个库所和变迁都加上标识0,表示该库所或变迁不可达。

(2)让标记(token)按照过程图的顺序遍历每一库所和变迁,遍历过的库所和变迁的标识由0变为1,表示从不可达变为可达;同时用两个队列R,S分别记住p(前置条件)为空的库所和p(后置条件)为空的库所。遍历直到汇结库所里有标记(token)或者没有变迁可以执行时结束。

(3)L(X)表示队列长,

如果L(R)=0,提示“被检验的工作流图无开始库所,不合理”,算法结束;

L(R)>1,提示“被检验的工作流图开始库所不唯一,不合理”,算法结束;

L(S)=0,提示“被检验的工作流图无汇结库所,不合理”,算法结束;

L(S)>1,提示“被检验的工作流图汇结库所不唯一,不合理”,算法结。

L(R)=L(S)=1,执行第4步。

(4)遍历完毕时,如果还有标识为0的库所,则提示“被验证的工作流图中有不可达库所,不合理”,并在图中显示不可达的库所,算法结束;如果还有标识为0的变迁,则提示“被验证的工作流图中有不可达变迁,不合理”,并在图中显示不可达的变迁,算法结束。

(5)检查汇结库所标识,如果标识为0,则提示“被验证的工作流图中有死锁,不合理”,算法结束;否则检查汇结库所第一次有token时的状态,该状态下如果存在具有token的非汇结库所,则提示“过程结束时过程中仍有标记,不合理”,算法结束;否则提示“被检验的工作流图是合理的,通过验证”;算法结束。

该合理性验证算法可以检查出过程中存在的各种语法和语义上的错误:开始库所、结束库所不唯一,死锁,死任务,活锁,同步丢失(lack of sy nchro-

·

51

·

第3期 周江波等:基于Petri网的工作流优化分析

nization ),结束状态不正确,从而确保了过程的正确性。实际企业建模过程中,活动的数目一般不会很多(少于100个),而且可以通过划分“子过程”的方法把复杂过程简化,所以被检验的工作流中活动的数目一般少于100个,不存在计算上的指数爆炸问题。

4　工作流优化

顺序过程是企业中出现频率最高的业务过程,对它的优化可以大幅度的提高整个工作流的指标,如平均完成时间、资源利用效率等,从而能够为企业带来可观的经济效益。图1是利用Petri 网描述的顺序过程,假设新案例到达过程的平均速率是每小时24个,且案例到达数目服从Possion 分布;task1和task2所需的服务时间都是4分钟,各有两个专门的资源负责完成

。

下面介绍两种针对顺序执行的过程优化方法:并行优化和合并优化。

并行优化:如果task1的执行结果不构成task2执行的必要条件,改顺序执行为并行执行。因为并行执行可以缩短案例的平均完成时间,提高办事效率。优化后的过程如图2

。

合并优化:当task1和task2是紧邻的两个任务并且它们需要同一个资源完成时,合并task1和task2为一个新任务task12。合并省去了不必要的交接手

续,可以节约操作时间(从原来的8分钟变为现在的7分钟)。优化后的过程如图3

。

根据排队论原理,可计算得出的优化前后过程

主要指标(如表1)。从表中不难看出优化后过程在平均完成时间、实际处理时间和平均等待时间三个指标上都有明显的改善。

表1　顺序过程优化前后的指标

执行路由平均完成时间

实际处理时间

平均等待时间

资源利用率

顺序执行22.28.014.280.0%并行执行15.04.011.080.0%合并执行

9.5

7.0

2.5

70.0%

图8给出对工作流中顺序执行路由的优化算法:

(1)检验已输入过程的合理性(参见本章验证过程合理性算法);如果通过验证,则提示“过程合理性验证已通过”,执行步骤2;如果不能通过验证,则提示“过程不合理,请修改合理之后再进行优化”,算法结束。

(2)检验过程中的主要指标:平均完成时间,平均等待时间,资源利用率。(3)找出过程中的顺序结构

;

如果没有找到,算法结束;否则执行4。(4)(A )如果task1和task2由同一个资源完成,合并task1和task2为task12(如图5)

;

(B )如果task1和task2由不同的资源完成,且task1的后置条件不构成task2执行的前置条件,那么把顺序结构改为并行结构(如图6)

。

·52·中国管理科学 2005年

5.返回第2步

5　保险索赔案例

下面我们通过保险索赔案例来定量的说明优化的效果。

保险公司XYZ 的上海分部有一项业务为处理该公司上海范围的汽车保险索赔,一般来说,到达XYZ 公司的汽车保险索赔案例为每小时4个,且到达过程近似服从possion 分布。下面为XYZ 公司处理保险索赔的过程:客户提出的保险索赔由部门Reception 的员工A 负责登记,登记一个索赔的时间一般为10分钟;登记完成后,交由部门Process 的员工B 对保险索赔进行分类,四成为简单索赔,六成为复杂索赔,这一过程需时5分钟。对于简单索赔,需要部门Process 的员工C 检查保险(包括检查险种、承保期限和承保金额),需时10分钟;员工D 打

电话给修车厂了解车辆损坏情况,需时10分钟,并

且这两个任务是相互独立的;对于复杂索赔,不但需要检查保险和员工打电话给修车厂这两个程序,而且还需要员工C 在两个程序之间检查车辆的损伤记录,需时5分钟,检查损伤记录需在检查保险之后才能完成。在这些前期工作完成之后,案例交由部门Process 的经理E 先决定是否赔偿,需时5分钟。通常来说,大约30%的索赔案例不需赔偿,则部门Reception 的员工F 给客户发信通知客户处理结果,需时10分钟;大约70%的索赔案例需要赔偿,则由经理E 确定赔偿金额,需时5分钟,之后交由部门Finance 员工G 支付赔偿金,需时5分钟,并且发信通知客户处理结果。

运用Petri 风建模理论,得出XYZ 公司上海分部的保险索赔处理过程如图7所示

:

根据排队论原理,可以求得案例的平均完成时间为3.68小时,实际平均处理时间为1.00小时,索赔案例的平均等待时间2.68小时,过程中员工的A ,B ,C ,D ,E ,F ,G 的忙碌程度(资源利用率)为(0.67,0.33,0.87,0.67,0.57,0.67,0.23);从上面的过程分析数据看出,员工C (负责检查保险并检查复杂案例的损伤记录)最为忙碌,大部分的案例材料会集中在这里,是过程的瓶颈。而员工B 和员工G 在过程中较为轻闲,可以委派其承担其他的工作任务。下面运用优化算法对上述索赔过程进行优化:

第一步:首先找到从库所sim ple 到库所C5的顺序结构,因为检查保险和打电话给修车厂是相互独立的,check -insurance 和phone -garage 由不同的资源完成且check -insurance 执行的后置条件不构成

phone -g arage 执行的前置条件,满足优化条件(A ),所以可以按照工作流优化算法将顺序结构改为并行结构:接着找到从库所complex 到库所C3的顺序结

构,因为复杂索赔索例中变迁check -insurance 和变迁check -histo ry 由相同的资源完成,满足优化条件(B ),所以可以按照工作流优化算法将二者合并成一个大的变迁check -insurance &history ,时间为12分钟;过程中从库所OK 到库所C8也为顺序结构,但是它不满足优化的条件,不能优化:

第二步,新生成的包含变迁check 和变迁phone -garage 的顺序结构也满足优化条件(A ),也可将顺序结构变为并行结构。优化后过程如图8所示。

·

53·第3期 周江波等:基于Petri 网的工作流优化分析

优化后过程的平均完成时间为2.29小时,实际处理时间为0.80小时,等待时间为1.49小时,员工过程中员工的A,B,C,D,E,F,G的忙碌程度(资源利用率)为(0.67,0.33,0.75,0.67,0.57,0.67,0.

23)。过程优化前后的主要指标对比如下表所示:

表2　优化前后索赔过程的主要指标

主要指标平均完成时间实际处理时间平均等待时间

优化前3.681.002.68

优化后2.290.801.49

减少值1.390.201.19减少百分比37.77%20.00%44.40%

6　结语及展望

本文提出的工作流验证算法可以有效地检查出工作流过程中可能存在的各种异常,优化算法可以对出现频率最高的顺序过程实现自动优化。本文的案例是作者从实际保险索赔过程中抽象出来的,忽略了一些细节,过程相对比较简单,实际的企业业务过程可能要复杂得多。本文在工作流过程优化方面的研究还值得进一步深入,如探讨循环过程的自动优化、选择过程的自动优化等。

参考文献:

[1]Workflow M anagement Coalition.T he Workflow reference

model[S].WfM C TC00-1003,1994.

[2]范玉顺,等.工作流管理技术基础[M].北京:清华大学

出版社&施普林格出版社,2001.

[3]W.M.P.van der A alst.Wo rkflow M angement-models,

methods and systems[M].M IT Press,2002.

[4]W.M.P.v an der A alst.T he application of Petri nets to

Wo rkflow Managemnt[J].The Journal of Circuits,Sy s-tems,and Computers,1998,8(1):21-66.

[5]王景光,等.基于Petri网的信息系统建模[J].中国管理

科学,2000,8(2):20-27.

[6]W asim Sadia et al.A naly zing process models using g raph

reductio n techniques[J].Information Systems,2000,25

(2):117-134.

[7]李红臣,等.工作流系统中的业务过程建模及分析[J].

计算机研究和发展,2001,38(7):798-804.

[8]赵磊,等.基于状态空间的工作流模型验证[J].计算机

工程和应用,2004,10:220-222.

[9]Henry H.Bi et al.Process logic fo r v erify ing the cor rectness

of business process models[C].P roceedings of the2004I n-ternational conference on information systems(2004ICI S),

2004,91-100.

[10]张人千,等.基于成本的车间作业优化模型及实证研究

[J].中国管理科学,2002,10(5):74-77.

[11]谢玉凤,等.基于条件化有向图的工作流过程优化[J].

计算机学报,2001,24(7):729-735.

[12]何辉,等.基于超图的企业过程描述和简化原理[J].计

算机应用研究,2001,7:86-89.

[13]T adao M urara Petri nets:P roperties,analysis and applica-

tions[J].P roceeding of I EEE,1989,77(4):541-580.

·

54

·中国管理科学 2005年

Petri Net -Based Workflow Optimization Analysis

ZHOU Jiang -bo ,LING Hong ,XU Zheng -chuan

(School of M anagement ,Fudan University ,Shanghai 200433,China )

A bstract :Workflow management technology is the core technology to realize business process reengineering ,process management and process automation .In the wo rkflow reference model ,wo rkflow verification and opti -mization are tw o key segments of process definition tool .After reviewing related research papers ,on the founda -tion of the classical Petri net theo ry ,the Petri net -based algorithm for verify ing the sound of w orkflow processes and process optimization are proposed .Optimization of insurance claim process as an example verifies the validity of the process optimization algorithm .

Key words :w orkflow m anagement ;Petri net ;verification ;optimization

·

55·第3期 周江波等:基于Petri 网的工作流优化分析

Petri网发展综述

1． Petri 网发展综述 Petri 网模型时C 。A 。petri 博士于1962年提出来的，他的提出专门应用这样一类系统，即系统中国含有相互作用的并行分支。作为研究系统的一种工具，petri 网理论用一个petri 网作为以恶系统的模型——系统的数学表示。从petri 网的观点来看待一个系统，集中地表现为两个本原的概念，即事件和条件。事件是系统中大声地动作，条件即系统的状态。系统中的动作的发生是由系统的状态来决定的，协调的状态演变是由系统的事件来驱动的。而这些状态可以用一组条件来描述。条件满足动作即可发生，动作发生后达到下一状态，它可以揭示出被模拟的系统的结构和动态行为方面的重要信息。这些信息可以用来对被模拟的系统进行估价并提出改进系统的建议。六十年代petri 网的研究以孤立的网系统为对象，以分析技术和应用方法为目标，通过网论丛七十年代开始研究，主要内容为网系统的分类及各网类之间的关系，包括：并发论，同步论，网逻辑和网拓扑，八十年代petri 网的研究在世界及中国有了较大的发展，近年来国内的主要研究集中在petri 网的语义，公平性，活性，网运算，网化简，PN 机理论等等。 当今计算机技术的发展日新月异，计算机计算能力的发展促进了模拟技术的应用和发展，用一个数学模型，比如petri 网来表示一个系统，然后，通过一定的算法让计算机对模型分析，就可以得到有关系统的性质。由于计算机计算的高速性和准确性，这就使得对巨大，复杂人工难以胜任的系统的模拟成为可能。 随着科学技术的发展出现了许多大规模的信息处理系统，如：并行程序，分布式操作系统，大规模的通信网络系统等等。由于petri 网可以精确描述系统事件之间的顺序并发关系，所以它是分析并发系统的强有力的工具。 Petri 网的研究工作沿着两个方向发展。第一，纯petri 网理论；第二，应用petri 网理论。 纯petri 网理论是为发展应用petri 网理论所需要的基本概念，技术和手段所做的研究。近年来petri 网理论的研究取得了不少研究成果，如petri 网的结构性质；petri 网语言：随机网，颜色网；谓词变迁系统等等。有国内吴哲辉教授和美国的T 。Murata 教授共同提出的petri 网的公平性取得了十分完整的结果，对于解决网系统中两个变迁（变迁组）的发生的关系提出了理论依据。蒋昌俊教授建立了PN 机理论构架，在交叠语义和偏序语义下获得反映真并发行为的文法及其PN 机结构，揭示它们的计算能力及其相互关系。 应用petri 网理论主要从事用petri 网模拟，分析和洞察系统的研究。这方面不单要求对petri 网及其模拟技术有深厚的知识，而且必须对应用领域相当熟悉。结合当今技术的发展越来越多地应用到通讯系统，分布式系统，并行计算机系统及自然科学社会科学的很多方面。 应用petri 网理论的一个重要方面就是并发系统petri 网分析工具的构造。Petri 网被应用于分析和设计系统时，如果系统规模较大则其对应模型必将十分复杂。人工分析显然是低效且不十分可靠的。因此，分析中若能有效地使用计算机则可十分迅速可靠的得到petri 网的性质。 2．Petri 网 Petri 网是用于描述分布式系统的一种模型。它既能描述系统的结构，又能模拟系统的运行。描述系统结构的部分称为网。从形式上看，一个网就是一个没有孤立结点的有向二分图。 定义1 满足下列条件的三元组N=（S ，T ；F ）称作一个网： 1） φ≠T S （1.1）

petri网的理论及应用

Petri网的综述及应用 蔡振宇 摘要： 一、Petri网的发展 Carl Adam Petri于1962年在他的博士论文中首次提出了有关Petri网的概念。自上世纪八十年代第一次Petri网理论和应用的国际研讨会的召开以来,与之相关研讨会在世界范围内就开始以一年一度的频率召开。人们通常称赞Petri网描述异步并发与图形表示的能力，而这两个特点来源于其网状结构。世间万物皆由网构成，只是这个网是有形的或是无形的，万事万物在这些网上发生着变化。事物间依赖关系，正是Petri网的完美体现。描述物理世界的客观存在，使客观存在成为论文的研究对象，同时还必须保证凡是用其描述的系统都能转换为客观存在。前者称为系统模型的仿真性，后者则是系统模型的可实现性。目前Petri 网己扩展成多种形式，如基础Petri网、时间Petri网、层次Petri网、有色Petri网等等[}z6-3 y。 一个Petri网的结构元素包括:库所(place)、变迁(transition)和弧(acr)。库所也称位置，它是一个抽象的词语，不是具体指哪个确定位置，而是建模中恰巧画的位置，它主要的作用是描述网中的一个局部资源状态或者是条件。变迁是用于描述变化着的系统事件，它表示的是一种资源相互作用的事件发生关系。弧的意义是描述资源的使能转化方向，是库所中消耗和产生的依据。如图2-1中，以红点来显示的是托肯(token)或者称为标记，它存在于库所中，呈现库所的资源数量，是Petri网中的一个重要概念。托肯在网中的动态变化意味着网的不同状态。一个简单的网系统模型，如图2-1所示。 -+Petri网从客观的角度对系统的发生进行定性和定量的描述，并能呈现出有规律的定性和定量的改变。在Petri网中，把对象统称为资源。定性相同的资源定为一类，用一个状态元素P来表示。托肯的数量代表了库所P的状态。尸的定性和定量的改变也就是上面所称的变迁T。在建模中库所P用圆圈来表示，变迁T用方框来表示，有向弧用箭头来表示。建模中箭头由圆圈指向方框意味着消