工作流模型时间与费用性能评估算法

潘 军 刘 丽

(北京航空航天大学飞行器控制一体化技术重点实验室，北京100191)

工作流管理的目标是，通过将工作活动有序化，以及合理地调用与这些活动相关联的人力资源和信息资源，来帮助企业高效地达到业务目标.在已有的研究中，Petri网已经被广泛地应用于业务流程的性能分析中［1］.另一方面，工作流的设计者可能从以前活动执行情况的统计信息中获得，或根据自己的经验估算出工作流每个活动的大概执行时间，他们希望有一种有效的时间性能评估方法，来估计工作流程的平均周转时间.也有很多学者针对工作流模型的费用的计算算法进行研究，但是大多研究针对的是无环结构［2］.

1 工作流过程模型

一个完整的工作流模型包括节点集合N和有向连接弧集合E两类［3］，具体类型包括:

1)节点类型.

①活动节点:普通节点、子过程节点;

②逻辑节点:与分支、或分支、与汇聚和或汇聚节点;

③标志节点:开始节点、结束节点.

2)有向连接弧类型.

包括普通连接弧、条件连接弧.连接弧是一个二元组(i，j)，i，j分别为连接弧前后节点索引号.每一个条件连接弧都设有一个条件概率参数α.

2 无环模型评估算法

2.1 系数值法

无环工作流模型系数值法采用系数值传递的计算规则如下.

开始节点的系数值总是为1，并将该系数值传递给后续节点.与分支节点的系数值等于前节点传递来的系数值，并传递该系数值给所有的后续连接节点.与汇聚节点的系数值等于前节点传递来的系数值任意一个，并传递该系数值给后续节点.或分支节点的系数值等于前连接节点传递来的系数值，传递给或分支的后连接节点的系数值等于或分支节点的系数值乘以或分支节点到该后连接节点的条件概率值.或汇聚节点的系数值等于所有前节点传递来的系数值之和，并将该系数值传递给后连接节点.活动节点的系数值等于前节点传递来的系数值，并传递该值到后续节点.

系数值法的计算过程是按照活动图的基本的拓扑顺序依次进行计算.对于没有错误的无环模型，计算完成后结束节点的系数值等于1.

2.2 进度与费用评估算法

分析无环工作流结构，计算出每一个节点在该模型中的系数值，再用下面的公式和规则计算出该模型的费用值和进度值.

模型的费用计算公式:

其中，ci为节点i的费用估计值;ki为节点i的系数值，无环结构中0≤ki≤1.

工作流模型进度的计算［4］参照下列规则:

1)开始节点的完成时间为0，即T1=0;

2)活动节点、与分支节点和或分支节点的完成时间为该节点的前连接节点的完成时间加上活动耗费的时间，即 Tw=Tv+tw，(v，w)∈E;

3)与汇聚节点的完成时间为其所有前连接节点的完成时间的最大值加上自身节点耗费的时间，即 Tw=max(Tv+tw)，(v，w)∈E;

4)或汇聚节点的完成时间计算公式为

对模型中的所有的节点按照拓扑顺序从开始节点到结束节点遍历计算完成后，则TWF=Tn.

无环工作流模型进度与费用评估算法步骤:

1)假设有n个活动节点，初始化每一个活动节点的时间ti和费用ci.逻辑节点和标志节点的时间ti=0，费用ci=0.对n个节点进行简单的拓扑排序，则这n个节点中第1个节点为开始节点，第n个节点为结束节点.设置k1=1，T1=0;

2)参照系数法的规则，依照拓扑顺序从开始节点开始依次计算每一个节点的系数值;

3)利用费用计算公式计算工作流模型的平均费用CWF;

4)按照进度计算规则，依照拓扑顺序从开始节点开始依次计算每一个节点的Ti，计算完后TWF=Tn.

这些算法能很有效地分析无环模型，对于有环模型，本文提出了将有环模型转化为无环模型的算法，再利用无环模型算法进行分析.

3 循环结构的提取算法

3.1 基本定义

强连通分量定义:有向图强连通分量在有向图G中，如果2个节点vi和vj之间有一条从vi到vj的路径，同时还有一条从vj到vi的路径，则称两个顶点强连通.如果有向图G中任意两个顶点都强连通，那么图G就为强连通图.非强连通图的极大强连通子图，称为强连通分量.计算有向图模型的强连通分量的常用算法为Tarjan［5］算法.

条件连接弧可以用来组成循环结构和选择结构，将条件连接弧分为2类:循环条件连接弧和非循环条件连接弧.图1中条件连接弧1是循环条件连接弧，2和3为非循环条件连接弧.将或汇聚的前连接弧也分为2类，循环普通连接弧和非循环普通连接弧.图1中连接弧4是循环普通连接弧，连接弧5是非循环普通连接弧.

图1 连接弧分类示例模型

对于单环模型，节点数大于1的强连通分量就是一个循环结构.对于多环模型，直接用Tarjan算法得到的强连通分量是由多个循环结构耦合而成，因此通过改进Tarjan算法来提取出模型中的每一个循环结构.

本文定义七元组来标识每一个循环结构:

其中，NN为循环结构中所有节点的集合;NK为循环结构中所有节点的系数值集合;CK为该循环结构的强连通分量系数;NHF为循环结构中标志或分支节点在节点集合N中的索引号;EHF为循环结构中标志或分支节点的后循环条件连接弧在连接弧集合E中的索引号;NHH为循环结构中标志或汇聚节点集合在节点集合N中的索引号构成的集合;EHH为循环结构中标志或汇聚节点的前循环连接弧集合在连接弧集合E中的索引构成的集合.

3.2 NN元素分析

一个循环结构一般由1个标志或分支节点和至少一个标志或汇聚节点组成.因为同一模型中任意2个循环结构的这4个元素是不可能完全相同的，所以七元组中后4个元素可以作为一个循环结构的主要标志元素.通过对连接弧集合E进行分析，得到所有的条件连接弧中属于循环条件连接弧的数量m，m即为该模型中循环结构的数量.分析模型中循环条件连接弧的作用，如果将其断开，那么对应的循环结构在整个模型中将不再存在.用一个布尔数组Enable［m］来表示该循环条件连接弧是否是断开，当其值为0时，表示该循环连接弧是断开的.当所有的循环条件连接弧都断开后，有环模型就变成了无环模型.

用七元组就能单独表示和分析一个循环结构.下面改进Tarjan算法，使得能够求得每一个循环结构.

1)遍历模型中所有的或分支节点，判断其所有的后向连接弧是否是循环连接弧.如果有则建立一个七元组，计算NHF和EHF.计算完成后会得到m个七元组，分别代表着m个循环结构.建立布尔数组Enable［m］，并初始化为0;

2)从第1个七元组开始，断开除该循环结构的所有其他m-1个循环连接弧，即在分析第i个循环结构时:如果k=i那么Enable［k］=1;反之Enable［k］=0.利用Tarjan算法分析模型.其中节点个数不为1的强连通分量即为该循环结构，该强连通分量的节点集合构成七元组中的NN元素.分析NN集合中的或汇聚节点和其前循环普通连接弧，并将其中的标志或汇聚节点和循环一般连接弧信息存储在NHH和EHH这2个元素中.

3.3 NK与CK元素分析算法

提取某一个循环结构时需要计算CK和NN集合内的所有节点的系数值NK.算法步骤如下:

1)备份所有条件连接弧的条件概率值;

2)NN集合内非当前循环结构标志或分支节点的条件概率值需要重新计算.为每个或分支节点定义一个布尔数组Cycle［n］，n表示该或分支节点的后非循环条件连接弧的个数.第i个条件连接弧的后连接节点在NN集合内则Cycle［i］=1，反之为0，再利用式(3)进行计算，PArc的定义在后面会提到.

3)将循环结构在标志或分支节点处断开，利用无环结构系数法计算所有NN集合内节点的系数值NK，计算该循环结构的强连通分量系数CK.用αi表示当前提取的循环结构中EHF元素代表的循环条件连接弧的条件概率值，则CK=αi/(1-αi);

4)还原所有条件连接弧的条件概率值.

3.4 条件概率更新

提取完某一个循环结构时，需要对该循环结构NN中的或分支节点的条件连接弧的条件概率进行重新计算，节点示意图如图2所示.

图2 或分支节点示例图

1)对于循环结构的标志或分支节点.

假设该或分支节点有n个条件连接弧，其中1到m是循环条件连接弧，那么或分支节点将是m个循环结构体的标志节点，后n-m个是非循环条件连接弧.每个连接弧的条件概率值为αi.

定义一个布尔数组Pick［n］表示这个或分支节点的条件连接弧是否已经提取过，初始值都为1，表示没有提取过.那么在提取第j个循环条件连接弧代表的循环结构之后，Pick［j］=0，对于第i个条件连接弧，如果 Pick［i］=1，那么 αi=αi/(1-αj).

2)对于循环结构的非标志或分支节点.

假设该或分支节点有n个非循环条件连接弧，其中1到m是属于该循环结构的条件连接弧，即连接弧的后续节点在该循环结构的节点集合NN内，后n-m个是不属于该循环结构的条件连接弧.每一个连接弧的条件概率值为αi.

定义一个布尔数组Type［n］表示这个或分支节点的条件连接弧是否属于循环结构，值为1时表示属于.这里需要计算几个因子:

PAct:该或分支节点到该循环结构标志或分支节点的概率值.

PArc:该条件连接弧到该循环结构标志或分支节点的概率值.

PHuofen:此次提取的循环结构的标志或分支节点的循环条件概率值.

KHuofen:循环结构的标志或分支节点到该或分支节点的概率值.

如果 Type［i］=1，则

如果 Type［i］=0，则

①PAct计算规则.在节点集合NN范围内，定义一个double数组K［n］，初始值为0，n为NN集合节点个数，循环结构的标志或分支节点在集合NN中的编号为NHuofen，该或分支在NN集合中的编号为N1，设置K［N1］=1.0，具体分析过程采用的是系数值法，从节点N1开始到节点 NHuofen结束.计算完成后 PAct=K［NHuofen］.

②PArc计算规则.在节点集合NN范围内，定义一个double数组K［n］，初始值为0，n为NN集合节点个数，循环结构的标志或分支节点在集合NN中的编号为NHuofen，该或分支节点在该条件连接弧下的后续连接节点在NN集合中的编号为N2，设置K［N2］=1.0.具体分析过程采用的是系数值传递方法，从节点N2开始到节点 NHuofen结束.计算完成后 PArc=K［NHuofen］.

③PHuofen计算规则.在提取循环结构时，EHF对应的循环条件转移概率为αi，则PHuofen=αi.

④KHuofen计算规则.在节点集合NN范围内，定义一个double数组K［n］，初始值为0，n为集合节点个数.对于NN集合中第i个节点，如果该节点为标志或汇聚节点则K［i］=NK［i］.该或分支在NN集合中的编号为N1，具体的分析过程采用逆向的系数值查询方法.具体规则如下:或分支节点系数值等于其前节点的查询得到系数值;或汇聚节点的系数值等于其所有的前节点查询得到系数值之和;与汇聚节点的系数值等于其某一个前节点查询得到的系数值;与分支节点的系数值等于其前节点查询得到的系数值;活动节点的系数值等于其前节点查询得到的系数值.对于任意类型的节点如果其前节点对应的K［i］≠0，则查询返回值为K［i］.从节点N1开始，计算完成后KHuofen=K［N1］.

3.5 七元组分析算法

对于任意的工作流模型，提取出所有的循环结构，将有环的工作流模型转化为无环模型.定义一个布尔数组S［m］，m为循环结构的个数，该数组初始值为0，表示循环结构没有被提取.

循环结构提取算法步骤:

1)调用NN分析模块，初始化S［m］;

2)按顺序判断S［m］数组中的值，找到其中布尔值为0的最小编号i;

3)提取NN集合中的除本身循环结构的标志或分支节点之外所有标志或分支节点对应的循环结构，即对这些循环结构递归调用步骤3)和步骤4)，递归完成后进入步骤4);

4)提取该强连通分量，并利用断开循环结构的方法来断开这个循环结构，将这个循环结构转变为无环结构.对这个无环的循环结构进行系数法分析，确定NK和CK，并利用上面提到的算法更新其中或分支节点的条件概率值，并设置S［i］=1;

5)判断S［m］数组中是否还有不为1的布尔值，如果存在则跳转到步骤2)，否则结束计算.

至此得到了所有循环结构的七元组数据.

4 任意模型进度与费用评估算法

得到每一个循环结构七元组数据后需要用这些七元组数据对模型中的所有标志或分支节点的费用和进度进行计算.在提取完所有的循环结构后，节点集合N中的每一个标志或分支节点会对应其中的m个七元组，m为该或分支节点的后循环条件连接弧的个数.利用七元组中的信息计算对应的费用和进度值作为标志或分支节点的费用和进度值，再利用无环费用和进度分析的算法分析整个模型的进度和费用值.

4.1 标志或分支节点参数分析

确定模型中标志或分支节点的个数n.定义布尔数组Q［n］，初始值为0，表示该标志或分支节点没有计算过.

标志或分支节点进度和费用计算步骤:

1)初始化Q［n］;

2)按顺序判断Q［n］数组中的值，找到其中布尔值为0的最小编号i.如果不存在则结束计算;

3)确定第i个标志或分支节点对应的m个七元组，设置j=1;

4)如果这第j个循环结构中存在其他的标志或分支节点k，且 Q［k］=0，则 i=k，并跳转到步骤3).否则将第j个七元组对应的循环结构在或分支处断开，并用无环结构进度与费用分析算法计算CCycle和TCycle.七元组对应的强连通分量系数Kj，利用下面的公式更新或分支标志节点的进度和费用:

5)j=j+1，如果 j≤m，则跳转到步骤 4)，否则Q［i］=1，并跳转到步骤2).

4.2 整个模型参数分析

得到每个标志或分支节点的进度和费用值后，就可以评估整个模型的进度和费用值.

整个模型进度与费用分析步骤:

1)初始化Enable［m］所有值为0，用系数法确定该无环结构的每一个节点的系数值;

2)计算每一个标志或分支节点的进度和费用值;

3)用无环算法计算模型费用值CWF和进度值TWF.

5 实例分析

以图3所示中的模型为例，图中活动节点的参数信息如表1所示.其中条件连接弧转移概率值设置如下:或分支1节点指向活动9的概率值为0.2，指向活动8的概率值为0.3，指向活动2的概率值为0.2，指向活动6的概率值为0.3.或分支2节点指向活动3和活动7的概率值都为0.5.或分支3节点指向活动4和活动5的概率值都为0.5.

图3 复杂工作流模型实例

本文将算法集成到了工作流管理平台中.在输入了上面的参数后，直接分析得到结果.其中或分支1标志节点的T=1.5 d，C=300.或分支3标志节点的T=14.25 d，C=2 850.整个模型的T=16.33 d，C=3266.67.

表1活动节点参数信息

本文同时用传统的多次仿真求平均值算法估算该模型，通过1 000次仿真后得到模型T=16.36 d，C=3272.39，算法的容许误差为 1%.通过对比得到，该结果与新算法结果近似，误差只有0.18%.而新算法只需运算一次，执行效率极高.对于复杂结构的工作流模型新算法能高效准确地进行进度与费用性能的评估.

6 结束语

本文针对复杂模型的结构特点，提出复杂模型逐步简化的算法，从而达到评估复杂模型时间和费用性能的目的.利用VC++开发了工作流管理软件，并用多种常用实例成功验证了该算法的可行性.该算法不足之处在于需要有精确并且完整的输入参数.因此在引入复杂的进度和费用参数模型的计算模型中，该算法需要进一步改进.

References)

［1］ Li Jianqiang，Fan Yushun，Zhou Mengchu.Performance modeling and analysis of workflow［J］.IEEE Transactions on System，2004，34(2):229-242

［2］苑迎春，李小平.基于串规约的网格工作流费用优化方法［J］.计算机研究与发展，2008，45(2):246-253 Yuan Yingchun，Li Xiaoping.Cost optimization heuristics for grid workflow scheduling based on serial reduction［J］.Journal of Computer Research and Development，2008，45(2):246-253(in Chinese)

［3］范玉顺.工作流管理技术基础［M］.北京:清华大学出版社，2001 Fan Yushun.Workflow management［M］.Beijing:Tsinghua University Press，2001(in Chinese)

［4］ Mark Allen Weiss.Data structures and algorithm analysis in C［M］.2nd Edition.Beijing:China Machine Press，2011:230-232

［5］ Tarjan R E.Depth-first search and linear graph algorithms［J］.SIAM Journal on Computing，1972，1(2):146-160