工作流网合理性验证的矩阵实现

刘 川，陈金玉

(重庆大学自动化学院，重庆 400044)

工作流技术［1］是随着生产和办公自动化等领域对计算机技术的引入而逐渐提出和发展的。在工作流应用系统［2］的开发过程中，一般需要经过业务流程的分析和建模、流程定义、流程发布、投入运行等过程。但如果等到投入实际运行后才发现流程模型不合理，则可能导致不可挽回的巨大损失。

一般工作流应用开发系统都提供了建模工具，但一些系统却缺少建模后对模型结构进行合理性验证的工具，比如较出名的开源工作流系统jBPM4［3］系列及以前的版本，在没有验证工具的情况下需要设计人员来把握业务流程的合理性。显然随着模型的日益复杂，对模型合理性的正确把握也相应更困难。

本研究在工作流管理系统及业务流程建模技术的基础之上，通过对现有Petri网［4］相关建模及验证技术的分析，对文献［5］提出的工作流网模型的合理性验证算法进行了改进，把对应的Petri网形式的工作流网模型表示为2个矩阵及向量形式，并通过矩阵及向量运算来进行工作流模型的合理性验证。

1 工作流网模型

工作流网是以Petri网为基础的一种网结构。基本的Petri网是一种有向二部图，一般包含4个基本元素:库所(place)、变迁(transition)、有向弧(arc)和表示描述系统动态变化的资源标记(token)。

在图形上用圆形表示库所，用小黑点表示标记，用矩形表示变迁，用有向弧连接库所到变迁或连接变迁到库所。库所与库所以及变迁与变迁是不允许直接连接的。限于篇幅，本文用到基本定义如基本Petri的定义、Petri网的前集和后集、Petri网的变迁发生规则等请参考文献［6］。

2 工作流网合理性验证的矩阵实现

工作流网(WF-ne)的概念是Alast提出的，是以Petri网为基础的，其定义和合理性条件请参考文献［7］。

合理性是一个工作流网应该满足的最基本要求，即应该满足任何执行的案例过程都能结束，不存在死任务，且结束的时候只有终结库所有一个标志，其他库所均为空。虽然合理性是一个最低的要求，不涉及其他可维护性问题，但合理性要涉及工作流的动态特性，并不是很容易验证。

2.1 算法基本思路

文献［5］的合理性验证方法主要是基于可达图，采用向量表示来逐步验证可能的状态，根据最终的结果来检验合理性。

考虑到在不合理网中可能出现不仅结束库所有标志，并且其他库所都还有标志的这种不合理情况，为了能减少状态空间的数量，在算法中加入这种情况的判断。工作流网的合理性定义参考文献［5］。本研究的算法思路描述:

1)采用广度优先算法，记录工作流网的输入输出矩阵［8］，并从初始状态集合S={M0}开始。

2)根据建立的矩阵判断S中的状态能否实施变迁，满足则实施变迁得到新状态集合S'，已经出现过的状态不在S'中，同时通过向量来记录触发过的变迁、经历过的库所。

3)如果结束库所有标志出现，则判断是否为不合理情况。若为合理情况则继续执行步骤4);否则算法结束，工作流网模型是不合理的。

4)把S'的值赋给S，重复步骤 2)，直到 S中的元素都没有变迁能发生。

5)如果S中的元素都是形如{0，0，…，1}的终止态，且所有的变迁都发生过，所有的库所都经历过，则该网是合理的;否则存在错误。

2.2 相关矩阵向量描述

根据上面的思路，采用矩阵及向量的简单运算来验证前面转换的模型的合理性。

定义1 PN=(P，T;F)为一个Petri网。将Petri网中的库所标记为 P={P1，P2，…，Pm}，变迁标记为 T={T1，T2，…，Tn}。

矩阵A－称为Petri网PN的输入矩阵:

矩阵A+称为Petri网PN的输出矩阵:

矩阵A=A+－A－，称为Petri网PN的关联矩阵(incidence matrix)，用Ai*、A+i*、A－i*分别表示矩阵A、A+、A－的第i行形成的行向量。

定义2 设 PN=(P，T;F，M)为一个 Petri网，把状态M表示为一个m维行向量，即M=［M(P1)，M(P2)，…，M(Pm)］，其中 M(Pi)表示库所Pi在状态M下的标志数。由定义可知M是一个m维非负向量。如果对于任意的p∈P，都有M1(p)≤(M2(p)，则称M1被M2覆盖，或者说M2覆盖M1。

引理1 设 PN=(P，T;F，M)为一个 Petri网，A为其关联矩阵，ti∈T，由变迁发生规则及向量的比较立即可得M［ti］＞M1的充分必要条件为M≥Ai－*。

引理2 设 PN=(P，T;F，M)为一个 Petri网，A 为其关联矩阵，ti∈T，如果 M［ti］＞ M1，则由变迁发生规则及定义1的关联矩阵有M1=M+Ai*。

定义3 (向量的或运算)已知向量X、A、B，令 X=A∪B，则

设M0为工作流网的初始状态即{1，0，…，0}，同时用一个集合H来存放发生过的状态，最初时令H={M0}。

用集合 N来存放产生的新状态，最初也令N=∅。

用一个n维向量Ts［n］来标记各个变迁是否已发生，Ts［i］=1表示第i个变迁已经被触发过，尚未触发的用 Ts［i］=0来表示，其中:i=1，…，n;最初 Ts=(0，0，…，0)。

对于每个库所是否被经历过的情况，采用一个m维向量Ps来记录，其中m是库所数，Ps［i］=1表示第i个库所已经历过，Ps［i］=0则表示未经历，最开始的状态为 Ps={1，0，…，0}。

2.3 具体实现步骤

1)采用广度优先的方法，把工作流网模型的库所依次编号为 P1，P2，…，Pm，变迁依次标记为T1，T2，…，Tn。按定义 1 分别建立输出矩阵 A+、输入矩阵A－以及关联矩阵A。

2)设立初始状态 Ts=(0，0，…，0)，PS={1，0，…，0}，M0={1，0，…，0}，历史状态集合H={M0}，产生的新状态集初始为N=∅，设置当前状态向量M=M0，还可以设置状态使能标记fire来判断在某个状态下是否有变迁能发生。fire为false表示没有变迁能发生，如果为true则表示有变迁能发生。令fire=false，以便于程序实现。

3)根据输入矩阵A－及当前状态M，由引理1判断是否有变迁能发生，分别进行处理。对每一个能发生的变迁产生的新状态如果没有在历史状态集H中出现，则加入新状态集N中，并且对结束库所出现标志的情况及时检查是否是不合理的，而对于没有变迁能发生的情况则判断是否有不合理情况出现。这一步骤的具体实施步骤:

①根据引理1，判断变迁Ti(i表示第i个变迁)能否发生，即如果存在输入矩阵的第i行满足，则设置fire=true标记有变迁发生，继续步骤②，否则对下一个变迁进行判断。

②根据引理2计算变迁Ti发生后的状态M'=M+Ai*，判断是否达到结束库所，即［m］是否为1。若为 0则继续步骤③。若为 1，则判断M'［1］到 M'［m －1］是否均为 0，若是则继续步骤③;否则结束算法，说明结构不合理。

③对M'进行已有状态判断。如果M'对每一个 Mi∈H，都不满足 Mi≤M'(即没被 M'覆盖)，则转步骤④，否则对下一个变迁，转步骤①对其进行判断。

④ 将M'加入新状态集合 N，N=N∪{M'}，M加入出现的历史状态集H，H=H∪{M}，变迁Ti已发生，故设置发生标志Ts［i］=1，设置已经历过的库所 PS=PS∪M'。

4)判断fire是否为false，如果为true转步骤5)。如果为false则表示在状态M下没有变迁可以发生，应该为最终结果，则判断M是否为{0，0，…，1}，如果不是则网结构不合理，结束算法，如果是转5)。

5)如果N为空，表示没有新状态，则转步骤6);否则，设置状态标识fire=false，从集合N中取出一个元素 Ni，则 N=N －{Ni}，令 M=Ni，转步骤3)。

6)最后，检查向量 Ts和PS，如果 Ts=(1，1，…，1)，并且 PS={1，1，…，1}，则表示该工作流网所有的变迁都能发生，所有的库所都经历过，即不存在死锁现象，表明工作流网是合理的。

3 实例验证

下面给出一个保险索赔的工作流网模型实例，根据上面的实现步骤，进行实例验证。保险索赔的工作流网模型如图1所示。对其进行广度优先，以及对库所和变迁编号后的模型如图2所示。

图1 保险索赔的工作流模型

图2 广度优先编号后的模型

根据图2建立输入矩阵A－、输出矩阵A+和关联矩阵A(行为T1～T9，列为P1～P9):

根据本文描述的算法步骤，有:

1)设立初始状态 Ts=(0，0，…，0)，PS={1，0，…，0}，M0={1，0，…，0}，历史状态集合H={M0}，新状态集初始为N=∅，设置当前状态向量M=M0。

2)在状态M0下只有T1能发生，得到状态M1=(0，1，0，0，0，0，0，0，0)，经过判断 M1为新状态，N={M1}，Ts=(1，0，0，0，0，0，0，0，0)，PS=(1，1，0，0，0，0，0，0，0)，H={M0}。

3)从N中取出M1，在M1状态下只有T2能发生，得到状态 M2=(0，0，1，1，0，0，0，0，0)，经过判断M1为新状态，N={M2}，Ts=(1，1，0，0，0，0，0，0，0)，PS=(1，1，1，1，0，0，0，0，0)，H={M0，M1}。

4)从N中取出M2，在M2状态下T3～T6都能发生，则分别得到状态 M3=(0，0，0，1，1，0，0，0，0)，M4=(0，0，0，1，0，1，0，0，0)，M5=(0，0，1，0，1，0，0，0，0)，M6=(0，0，1，0，0，0，1，0，0)，经过判断均为新状态，N={M3，M4，M5，M6}，Ts=(1，1，1，1，1，1，0，0，0)，PS=(1，1，1，1，1，1，1，0，0)，H={M0，M1}。

5)从N中取出M3，在M3状态下T3、T4、T7都能发生，则分别得到状态 M7=(0，0，0，0，2，0，0，0，0)，M8=(0，0，0，0，1，1，0，0，0)，M9=(0，0，1，0，0，0，0，0，1)，当产生状态 M9为结束库所出现了标志，经过判断M9为不合理的情况，算法结束。

4 算法及实现分析

本文算法理论上可以对任意工作流网模型进行合理性验证。对比较复杂的工作流网而言，状态数可能呈指数级增长，但通过矩阵和向量的比较运算来判断变迁发生及记录变迁发生后的状态，使算法步骤更简洁，相对更利于计算机程序实现。

通过上面的实例可以看出，在算法的具体实现中，当结束库所出现标志时即对不合理情况进行及时判断，在不合理时避免了后续状态的验证，在一定程度上减少了验证状态的数量。对于合理情况也是可以判断的，但相对于原算法，除了用2个矩阵和向量表示以及较简洁的运算实现以外，并没有什么算法理论上的效率提升。

5 结束语

把工作流网模型表示为输入输出2个矩阵和2个库所和变迁的向量，通过矩阵的比较和加减运算实现了变迁的判断和发生状态记录，完成了对工作流网模型的合理性验证，并通过及时判断结束库所出现标志的合理性来减少后续状态的判断次数，效率有了一定的提升，具有一定的实际意义和参考价值。

随着工作流模型和规模的扩大，验证状态也呈指数级别增长，还需要对模型进行化简等优化操作来减少验证的状态，同时，对于不合理的情况，该算法本身也不能定位具体是哪些结构导致了结构的不合理性，这都需要进一步研究。

［1］付伟.工作流技术综述［J］.河北北方学院学报，2007，23(2):13－15.

［2］侯志松，冯启高.工作流管理系统开发实录［M］.北京:中国铁道出版社，2010.

［3］胡奇.jBPM4工作流应用开发指南［M］.北京:电子工业出版社，2010.

［4］秦凯，姜浩.一种基于Petri网的工作流模型分解方法［J］.计算机技术与发展，2008，18(1):97 －100.

［5］周福明，吴斌，顾庆，等.基于Petri网的工作流建模与正确性分析［J］.计算机科学，2005，32(2):121 －124.

［6］吴哲辉.Petri网导论［M］.北京:机械工业出版社，2006.

［7］van der Alast W M F，van Hee K.工作流管理—模型、方法和系统［M］.王建民，闻立杰，译.北京:清华大学出版社，2004.

［8］喻斌，武友新.工作流过程建模中验证技术的研究［J］.微计算机信息，2008，24(1－3):220 －222.