樊广军，熊劲华

FAN Guang-jun, XIONG Jin-hua

(中南大学 机电工程学院 高性能复杂制造国家重点实验室，长沙 410012)

0 引言

作为PDM系统的重要组成部分，工作流管理有利于工作流的建立与执行，从而达到简化业务流程的目的。然而，现有的工作流管理解决方案是用来处理静态业务流程。当一个工作流程发生变化的时候，这些解决方案会完全中止执行受到影响的工作流程实例，然后从头开始执行修改过的工作流程实例。这种简单化的解决方案会导致任务已经完成的工作流节点被重复执行，从而造成系统资源的浪费。目前许多学者对工作流的研究大多局限于工作流建模，有关动态工作流变化的问题却没有得到很好的解决，现存的解决方案不能够为管理工作流变化提供有效的方法[1]。因此，对PDM系统中动态工作流变化的分析与研究是十分必要的。

1 PDM系统中工作流的表达

工作流是一类能够完全或部分自动执行的业务过程，根据一系列过程规则，文档、信息或任务能够在不同的执行者传递、执行[2]。作为一种计算机化的业务流程，工作流可以采用Petri网(Petri Net, PN)、有向图(Directed Network Graph,DNG)等许多正式方法对其建模[3,4]。因为基于有向图的表达形式被广泛的应用在各种业务平台中，所以本文采用它来实现工作流程平台。于是，一个工作流W可以用一个二元组(N,C)来表示，其中N={n1,n2,...}为工作流中的各个活动，在工作流模型中表现为节点；C={c1,c2,...}为各个活动间的次序关系，在工作流模型中表现为节点间的连接线。图1举例说明了一个简单的工作流W=(N,C)，其中N={n0,n1,n2,n3,n4}，C={c0,c1,c2,c3,c4}。如果连接线c指向节点n，那么c是节点n的输入连接线；反之c是节点n的输出连接线。每一个节点n又可以用一个四元组(t,u,Ci,Co)来表示，其中t代表相关任务，u代表相关用户，Ci代表所有输入连接线，Co代表所有输出连接线。每一条连接线c由一个三元组(r,ns,ne)表示，其中r是关于c的响应，ns是连接线c的开始节点，ne是连接线c的结束节点，节点ns是节点ne的前节点，节点ne是节点ns的后节点。一条连接线的响应类型决定了它的触发条件，假如一个节点被成功执行，则它的输出连接线将会触发“接受”响应，否则其连接线将会触发“拒绝”响应。图2提供了一个带有不同响应连接线的示例。

图1 由五个节点和五条连接线组成的一个简单的工作流

图2 两种响应类型：“接受”和“拒绝”

在实际的工作流管理系统中，工作流被定义成模板或图示的形式。当一个工作流模板被初始化，它就被称之为实例。任何时候，一个工作流实例中的所有节点可以按照状态的不同划分为三种类型：就绪提交节点，等待执行节点，已完成节点[5]。工作流实例中节点的状态在执行过程中会发生变化，节点不同状态间的转换如图3所示。

图3 状态转换

每个节点的初始状都是“就绪提交”，当此状态的节点被其用户开发来执行时，这时节点状态为“等待执行”。如果节点被成功执行，它的状态就转化成“完成”，否则就变成“就绪提交”状态。必须引起注意的是，有一些节点可能由于“拒绝”响应而被多次执行。理想状态为，工作流实例应该是未受中断影响而一直执行完成。然而，工作流变化会在实际的工程环境中发生。一个工作流实例的变化通常有可能是：1）节点的增加或去除；2）连接线的增加或去除；3）节点属性的修改[6]。一旦工作流实例受上述变化的影响，它将被迫中止执行。此后，这种变化会应用于受影响的工作流实例。通常情况下，修改后的工作流模板将会用来初始化工作流实例，并且该实例将重新启动。在普通工作流管理系统中，重启工作流实例将会导致所有节点回到初始状态，而不论这些节点现有状态情况。这是一种消极的处理方式，因为所有在重启实例中的节点都将再执行一次。

2 节点识别

为了方便动态工作流变化的管理，主要依据以下三个条件对节点进行识别，依次对这三个条件识别完成后，才能确定节点n在新工作流实例中是否需要重新执行。这三个条件为：1）节点n的属性和连接线(触发条件)是否发生了变化，即节点是否为未变节点；2）节点n的任务是否已经完成，即节点n是否为完成节点；3）节点n的所有前节点是否都不需要重新执行，即节点n的所有前节点是否都为可绕开节点。

2.1 未变节点的识别

假设一个工作流模板T1，一个被初始化的工作流实例W1。当执行W1时，工作流模板T1改变成T2，一个新工作流实例W2在模板T2中被初始化，用来取代工作流实例W1。对于实例W1中的任何一个节点n可能发生属性改变或连接线改变。如果该节点的位置在实例W2中发生了改变，事实上就是该节点的连接线发生了改变，因此该节点属于第二种情况。假设节点n在新工作流实例W2中发生了改变，并且它的名称也变化了，那么该节点被认定为一个新节点。

2.1.1 节点属性变化的识别

在工作流实例中，一个节点的属性主要包括任务与用户两个部分。如果任务发生了变化，那么该节点应当识别为变化的。如果节点的用户发生了改变，那么该节点可以认为没有变化。因为用户的改变不会影响节点的状态，如果节点的任务已经完成了，那么在新的工作流实例中，新用户就不用去执行该任务了；如果节点处于就绪提交状态或等待执行状态，不论用户改变与否，它在新工作流实例中都要被执行。

因为节点的用户名具有唯一索引，所以发现节点用户的改变是比较容易的，而发现节点任务的改变却是比较困难。一般的，节点的任务可能由人工或系统自动产生。人工产生的任务往往用来代表一系列描述信息或文档(包括文本和图形)，因此通过比较描述信息或文档标识(文档编号、大小、修改时间等)可以比较容易的区分两个人工产生的任务。如果任务是由系统自动的生成的，它实际上是一个可以调用的计算机程序。通过比较两个计算机程序的全路径(如果它们都是本地可执行文件)或统一资源定位(如果它们来自远程服务器的调用)，可以明确的把它们区分开来。然而，应该有一种方法用来检查这种情况：当计算机程序发生了变化而它的全路径或统一资源定位却没有改变。为了解决这样的问题，自动产生的任务应该有版本管理功能，即它能对版本进行响应。作为一个例子，接下来的逻辑方法可以用来判断一个节点的任务是否发生了变化。

如果两个节点n1，n2有相同的属性，那两个节点的关系可以表示为n1en2。

2.1.2 节点连接线变化的识别

工作流实例中的节点也可能发生连接线的变化，图4举例说明了一些连接线变化的类型。如图所示，在(a)中节点n2的位置变化导致节点n2连接线的改变；在(b)中增加节点n3和节点n4导致节点n1连接线的改变。

图4 连接线的改变

为了解决上述问题，需要设定以下规则：

1)任何两个工作流实例的开始节点是相同的。

理想情况是，如果两个节点不仅属性相同，而且连接线也相同，那么这两个节点相同。对于旧工作流实例中的节点n，如果在新工作流实例中有一个节点n满足n=n，则说明节点n没有变化。

2.2 完成节点的识别

判断一个节点在旧工作流实例中是否为完成节点是比较简单的，因为所有的工作流管理系统都允许节点的状态查询，通过访问节点状态属性的方式来获得节点的状态。

2.3 可绕开节点的识别

如果一个节点的任务在旧工作流实例中被执行完成，在新工作流实例中仍然有效而不需要重新执行，那么该节点在新工作流实例中就是可绕开节点[7]。显然，可绕开节点应该是1）旧工作流实例中存在的，2）已经执行完成的。然而，以上两个条件还是不足以确定一个节点是否为可绕开节点，其缘由是一个节点的执行状况受到其输入情况的影响。为了掌握节点输入情况的关键部分，本文定义了如下概念：

1）如果连接线c对于节点n1来说是输出连接线，对节点n2来说是输入连接线，那么节点n1就是节点n2的前节点。两个节点之间的相互关系可用n1→n2来表示。

2）如果n1到n2之间有一个节点集{nai}使得n1→na1,na1→na2,...,nan→na2，即n1→n2，那么可以认为n1到n2之间有一个路径。

为了确定新工作流实例中的节点是否为可绕开节点，需要增加一个概念：一个指向当前节点的路径中的所有节点都为可绕开节点。

因为一个可绕开节点在旧工作流实例和新工作流实例中产生的输出结果是相同的，所以可绕开节点的聚合肯定也会产生相同的效果。因此，使用下面三个条件判断一个节点在新工作流实例中是否为可绕开节点是足够的。

1）节点n的属性在新工作流实例没有改变；

2）节点n在旧工作流实例中被执行完成；

显然，在一个新工作流实例中，开始节点总是可绕开节点，因为它总是满足以上三个条件(在所有的工作流管理系统中，任何工作流实例中的开始节点都是由系统自动完成)。

我们可以运用以上三个条件，对新工作流实例中的每一个节点进行分析，然后确定其是否为可绕开节点。判断步骤如下所示：

1)建立一个包括新工作流实例W2中所有节点的有序列表L；

2)从列表L中去除W2中的开始节点，并把开始节点设置为可绕开节点；

3)对于列表L中的任何节点n，核查在旧工作流实例W1中是否有一个节点n，使得n与n有相同的属性，并且n是被执行完成的。如果节点n不满足这两个条件，再次从步骤(1)开始执行，进行下一个节点的判断；若节点n满足这两个条件，则进行下一步。

4)识别W2中所有的节点，确定其中是否存在指向节点n的路径。若存在，则该路径中所有的节点都为可绕开节点，那么就可以把节点n设置成可绕开节点，并从列表L中移除，重新回到步骤(1)再进行下一个节点的判断。

5)当列表L中所有的节点都经过了判断，核实列表 的长度有没有发生变化。如果发生了变化，再次从步骤1开始判断；如果长度没有发生变化，中止整个判断步骤，因为列表L中的所有可绕开节点已经被识别出来，并且已从列表L中移除。

以上的非递归步骤确保了在一个或多个可绕开节点识别以后，有序列表L中的所有节点都会得到处理。尽管这种方式是非常简单和健壮的，但由于一些位于有序列表前端的节点在识别是否为可绕开节点之前已经被重复判断了多次，从而导致该种方式缺乏效率。

一种更有效的理念就是运用新工作流实例的拓扑结构来检查节点，该理念能够使这些节点有更多的机会被识别为可绕开节点。显而易见的是，在新工作流实例中，由于开始节点总是可绕开节点，所以它是第一个被检查到的可绕开节点。基于已有的规则，如果在新工作流实例中存在指向节点 的路径中有一个节点不是可绕开节点，那么节点 就不是可绕开节点。因此，从新工作流实例的开始节点，即第一个可绕开节点开始，沿着开始节点的输出连接线方向，遍历整个工作流的方法是非常合理的。在开始节点的所有后续节点中，这些非可绕开节点能够被识别出来，通过这样的方式能简化工作流实例，避免不必要的检查。为了实现上述这些理念，本文开发了一种递归方法，如下所述：

1)如果输入节点n是新工作流实例的开始节点，或者该节点的所有前节点都是可绕开节点，那么把节点n设置为可绕开节点。

2)经过步骤(1)之后，如果输入节点n是可绕开节点，则找出节点n的所有后续节点，把每一个后续节点设置为这种流程的输入节点，重复相应的流程；否则就退出该流程。

以上的方法从第一个可绕开节点，开始节点开始。该方法只测试了一个可绕开节点的后续节点，通过利用工作流实例的拓扑结构，可以避免对非可绕开节点的检测。但是，对内存的巨大需求却成为该方法的一个主要问题。当处理大量工作流实例的时候，这样的一种递归算法可能会严重的降低工作流管理系统的运行效率。因此，针对工作流，适度的运用递归方法是合理的。为了处理大量的工作流的变化，这就需要有高效稳定的非递归方法。

为了提出一种非递归方法，本文引入了节点层的概念。节点 的层指的是从开始节点到节点 的路径中节点的个数[8]。例如，在一个路径n0→n1→n2→n3中，节点n2和n3的层分别为3和4。如果从开始节点到节点n有多条路径，那么节点n的层被定义为最短路径中节点的个数。

当评估一个节点成为可绕开节点的可能性时，从前面层的节点开始运行是可取的。因为这些节点有更多的机会成为可绕开节点，能够更早的从有序列表中移除。随后，在有序列表中对节点进行排序之后，能够运用先前提及的非递归方法来实现对可绕开节点的识别。通过合理的消耗内存，节点排序能够有效的减少动态工作流变化的处理时间。

3 应用实现

在上述理论研究的基础之上，运用Java开发语言，以MyEclipse 9.0 M1为开发环境，SQL Server 2005为数据库，开发了支持动态工作流变化的工作流管理系统，并实现与已有PDM系统的集成。系统界面如图5所示。用户可以根据不同企业的工作习惯，灵活的使用可视化的工作流编辑器，建立相应的工作流程。为了方便对动态工作流变化的管理，运用Java程序来实现所提出的方法，程序执行步骤如下：

1）打开PDM系统，在工作流编辑器中产生必要的数据集对象。

2）获得一个流程实例。

3）获得流程的新旧工作流模板。

4）把旧工作流实例保存在内存中，给工作流过程附加新的工作流模板。

5）识别新工作流实例中的所有可绕开节点。

6）对新工作流实例进行初始化，执行所有可绕开节点。

7）把修改后的工作流过程释放给所有等待执行节点的用户。

图5 工作流管理系统界面

4 结束语

工作流管理是PDM系统的重要组成部分，是其基本功能，对动态工作流变化进行分析与研究可以提高工作流管理系统的柔性。将动态工作流变化管理技术应用到现有的PDM系统中来，实现了产品设计开发相关数据的完整性，提高了企业管理经营的自动化水平。

[1]刘艳平,赵武,熊欣.基于PDM的产品设计过程动态工作流管理[J].机械设计与制造,2009,(1):225-227.

[2]欧阳昱.工作流与访问控制[M].北京:航空工业出版社,2010.

[3]罗海滨,范玉顺,吴澄.一种面向企业用户的工作流模型[J].计算机集成制造系统,2000,6(3):55-59.

[4]陈四根,蒋增强,安苏华,等.基于有向图的工作流建模及其运行[J].合肥工业大学学报:自然科学版,2007,30(1):60-65.

[5]王伟,蒋增强,刘名周,等.PDM系统中动态工作流的分析与研究[J].合肥工业大学学报:自然科学版,2010,33(11):1618-1622.

[6]徐兆宏,戴跃洪,王永峰.PDM系统中工作流程动态变化的研究[J].设计与研究,2007,(5):13-14.

[7]W.M.P.van der Aalst,S.Jablogski.Dealing with work flow change:identification of issues and solutions[J].International Journal of Computer Systems Science&Engineering.2000,15(5):267-276.

[8]L.Pudhota,E.Guntama,E.Chang,etc.Extension of activity diagrams for flexible business work flow modeling[J].Computer Systems Science and Engineering.2003,18(13):137-152.