PDM系統中動態工作流變化的分析與研究

樊廣軍，熊勁華

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.