支持过程改进的工作流仿真及优化技术研究

刘　磊，余汾芬

（1.浙江理工大学先进制造技术研究所，浙江　杭州　310033；2.安庆职业技术学院　机电工程系，安徽　安庆　246003；

3.安庆医药高等专科学校，安徽　安庆　246052）

支持过程改进的工作流仿真及优化技术研究

刘磊1，2，余汾芬3

（1.浙江理工大学先进制造技术研究所，浙江杭州310033；2.安庆职业技术学院机电工程系，安徽安庆246003；

3.安庆医药高等专科学校，安徽安庆246052）

业务流程重组（BPR）是增强企业竞争能力的关键，而工作流技术是支持过程改进的有效技术.至今为止，工作流仿真和优化还是一个薄弱环节.本文提出了一种基于petri网的工作流仿真方法和工作流优化的关键路径方法（CPM），从而为支持企业业务过程改进找到了一个可行的思路.最后，给出工作流仿真系统JXWorkflow具体实例分析.

过程改进；工作流仿真；工作流优化；Petri网；关键路径

自上世纪九十年代初，企业的核心竞争力由之前的时间、成本逐步转移到对整个业务流程的控制，业务流程重组（BusinessProcessReengineering，BPR）的概念应运而生，它的主要标志是以企业过程为中心，并通过ISO9001质量标准检测和CMM过程成熟度评估.而工作流技术则是实现企业业务过程自动执行和各部分信息交互的有效方法，它起源于业务过程的自动化，通过企业过程的计算机模型表示，从而实现文档、信息和任务的自动执行，继而实现企业业务过程的自动化处理.但是工作流模型在建模阶段不可能完全考虑到所有的情况，业务过程中深层的语义规则也不可能完全挖掘出来，因此，工作流仿真和优化便成为支持企业业务过程改进的关键技术[1].

1　Petri网仿真

工作流仿真是对模型评估、分析业务过程、发现瓶颈问题并对业务模型进行优化的有效方法.它可以在系统运行之前对模型进行跟踪，配置，设置仿真环境，利用离散事件驱动的方式使得流程向下流转，自动推进工作流实例，通过对流程的仿真，得到一系列关于工作流模型运行的统计数据，并分析业务过程、活动和资源等动态对象，从而来判断、评估或评价真实流程的性能..

Petri网具有描述不确定和随机特征的复杂系统的能力，它从关注过程的角度，兼顾严格语义和图形语言两个方面，既可以作为描述系统模型的图形化工具，也可以建立描述诸如系统方程等系统模型行为的数字化工具，是一种描述和分析复杂系统的有效模型工具.

定义1（WF-net） 一个PN可以用一个5元组表示成为，如果以下条件成立[2]：

1、对结点i∈P，·i=Ø，则i称源库所；

2、对结点o∈P，o·=Ø，则o称为汇结库所；

3、对于每一个结点x∈P∪T而言，它必定都位于某一条从i到o的路径上.

此时，可以认为PN=(P,T,F)是工作流网.

WF-net的有以下性质：

1、只有唯一一个源库所，即i；

2、也只有唯一一个汇结库所，即o；

3、如果在PN中添加一个连接汇结库所o和源库所i的变迁t*（即·t={o}且t*·={i}），得到PN是强连接的，而且对于每一个结点x∈P∪T，必定位于一条从i到o的路径上.

定义2（合理性） 由一个WF-netPN=(P,T,F)描述的业务过程，如果以下条件成立：

1、对每个状态M，假设它可以从初始状态i达到，则必存在一个发生序列，而且它是从状态M到状态o的，即：∀M(i→*M)⇒(M→*o)；

2、只有唯一一个正常结束状态，即状态o：∀M(i→*M∧M≥o)⇒(M-o)；

3、不存在死变迁，即：∀t∈T，∃M,M1，使得(i→*M→tM1).

此时，可以认为该过程是合理的.

我们可以通过构造变迁—自由选择子网距阵Bn×k与变迁—资源距阵Cl×k来分析多维工作流网模型PN的性能[3]，下面通过实例来说明.

图1(a)为一个由有向网络图描述的工作流模型，假设其开始活动、结束活动及所有逻辑节点的时间、需求的资源等均为零，该业务过程中所消耗的资源{R1,R2,R3,R4}的状态向量为{1，2，1，1}.图1(b)为经模型映射后得到的自由选择多维工作流网模型.

对图1(b)的模型进行分解，得到两个自由选择子网，如图2(a)-(b)，它们分别描述了两种业务实例I1和I2的处理过程.

图1　模型映射示例

图2　模型分解

构造变迁-自由选择子网距阵B2×13和变迁-资源距阵C，如下所示[6]：

假设总业务实例到达速率λ=0.2，业务实例1和业务实例2在总业务实例中所占的百分比β={β1，β2}={0.5，0.5}，得到λI={0.1，0.1}，即I1和I2的到达速率均为0.1.

下面其性能进行分析.对应于多维工作流网中的13个变迁可以得到μ={μ1,μ2,…,μ13}={0,0,0.2,1,0.5,0.167,0.167, 0,0,0.25,0}，其中从μ1至μ13分别表示变迁ts，t1A，t2A，tA1，tA2，tA3，tA4，tA5，tA6，tB，tC，tA7，tE的触发延迟均值的倒数，即μi=1/α (ti)，从而得到：

λI×B2×13=[0.2,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.2,0.2,0.2,0.2]，ω=Cl×k×(λI×Bn×k)T=[0.20.20.20.2]T分别指资源{R1,R2, R3,R4}的业务实例到达速率.从图中我们可以看出，资源R1参与变迁tA1，tA5的触发，所以其平均服务速率为ηi=∑(μi× λti/∑λti)=0.183.通过同样的计算可以得到R2，R3及R4的平均服务速率分别为0.75，0.33和0.25.由于资源R1的服务负载ρ1=ω1/η1=0.2/0.183=1.093>1，造成系统不稳定，其配置显然不满足要求.如果我们增加数量至2，ρ1=ω1/η1=0.2/(2× 0.183)=0.546<1，此时资源R1的配置能够满足系统稳定性的要求.通过同样的方式我们可以验证：资源R2，R3及R4的配置均满足系统稳定性的要求.

2　关键路径优化技术

工作流可以看成一个由串联、并联、选择和循环4种控制结构组成和相互连接的活动网络.运行时，活动的服务器服务时间服从指数分布并且用户的服务需求的到达过程服从泊松分布.因此，根据工作流活动的可操作性这一特点，可以把工作流看成其中每个活动都是独立的M/M/1排队网.假设每个活动的到达率、服务率和选择、循环的概率是确定的，那么我们可以计算出工作流活动网所有活动的到达和完成时间.各种结构的平均执行时间按如下公式进行计算[4]：

1、顺序结构wt=∑(1/μt-λi)；

2、选择结构wt=max(∑(1/μt-piλi))，其中∑pi=1，pi表示各分支到达的可能性；

3、循环结构wt=(1/pμt-λ)+K+(1/pμn-λ)；

4、并行结构wt=max(∑(1/μt-λi)).

按图3所示的规则将工作流模型转换为树形表达[5].算法如下：

Procedure

Calculated_Critical_Path(workflow.roott)

Begin

Object=workflow.root;

Ifobject.type=ActivityThen

SelectobjectforCalculated_Critical_Path(object);

Else

Begin

Forallchildrenobject;

Calculated_Critical_Path(object.child);

Ifobject.type=SerialThen

Object.Completion_Time=

Sum_Completion_Times_of_Children(object);

Ifobject.type=AndThen

Begin

Object.Completion_Time=

MaxCompletion_Times_of_Children(object);

Exclude_Nodes_in

图3　基本工作流结构的树形表示和完成时间的计算方法

Non_MaxChildren_Subtree_from_CP(object);

End

Ifobject.type=OrThen

Object.Completion_Time=SumCompletion_Times_of_

Children(object);

Ifobject.type=IterateThen

Object.Completion_Time=

Iterate_Formula_for_Completion_Time(object);

End;

End;

3　仿真机制及系统实现

基于上述研究基础,笔者所在的课题组在开发了一个工作流仿真系统-JXWorkflow，它是运行在虚拟环境之上的.其工作流仿真机制如图4所示，由表示层（即用户操作界面,包括设置仿真环境及参数、显示仿真动画和生成仿真报表）、业务逻辑层(工作流仿真引擎)和数据库层(包括工作流实例库、工作流资源库以及仿真信息库)构成，它以时间、成本、资源利用率、等待队列作为仿真指标，来综合分析和评价企业业务流程模型的性能,其计算方法如表1所示[6].

指标计算方法时间（小时）　　活动时间=工作时间+等待时间（等待资源时间+阻塞时间+非活动时间）按价值类型：成本=增殖活动成本+业务增殖活动成本+非增殖活动成本按资源类型：成本=劳动力成本+设备成本+原材料成本+其他按时间类型：成本=标准成本+超时成本过程性能（%）　　资源利用率=∑资源忙时间/（资源时间-非活动时间-无效时间）成本（元）

JXWorkflow系统的仿真组织策略如下：首先确定活动执行的组织单元，其次进行工作流模型的资源配置；然后对过程中的活动进行属性配置；最后设置仿真运行环境.经过多次仿真，得到一组仿真数据，通过对仿真数据的分析来发现业务流程的瓶颈问题，找到关键路径，进而达到优化和改进业务流程的目的.

图4　工作流仿真机制

4　结束语

目前大多数工作流系统对模型的合理性和有效性缺乏足够的支持，不仅安全可靠性差，而且风险极高，资源浪费.就工作流仿真而言，难点在仿真内容的复杂性和仿真指标的确定，比如信息流的仿真和历史数据挖掘等仿真机制的实现；对于工作流模型结构的优化，缩短关键路径的平均执行时间是提高工作流执行效率的有效方法，在使用优化方法对工作流模型结构进行优化时，还应该遵照企业运行过程，保留合理的业务逻辑关系，不能盲目优化模型结构，造成无法实际应用.

〔1〕武星.成本最优化工作流技术驱动的研发协同软件即服务应用［J］.计算机集成制造系统，2013，19（8）：1750-1752.

〔2〕许春霞.基于随机Petri网的工作流仿真［J］.计算机技术与发展，2009，19（4）：88-89.

〔3〕赵新晓.支持可定制建模方式的工作流系统的研究及实现［D］.山东大学，2012.71-75.

〔4〕高保强.工作流仿真结果分析［J］.计算机工程，2010，36（10）：45-46.

〔5〕李海波.基于时间关键路径的工作流模型优化方法［J］.机电产品开发与创新，2005（6）：205-206.

〔6〕文俊浩.基于WDAG的工作流模型优化分析［J］.计算机工程，2010，36（1）：30-32.

TP311

A

1673-260X（2016）08-0019-03

2016-05-28

2015安徽省高校自然科学研究项目 《可拓学下的协同产品商务 （CPC）及其在安徽制造业中的应用研究》（KJ2015A390）；2014安徽省质量工程教学研究项目 《产教融合校内实训基地培养制造类高素质技能人才的研究与实践》（2014jyxm535）