復(fù)雜工作流模式的重構(gòu)研究

摘 要：通過分析在實際工作流中易出現(xiàn)的復(fù)雜模式，探究了以往文獻中的重構(gòu)算法不能處理這些模式的原因。通過對算法進行修正，使該算法能夠?qū)?fù)雜模式進行有效處理。通過實驗證明，改進后的算法仍能保持良好的性能，適用性較強。

關(guān)鍵詞：復(fù)雜模式; 結(jié)構(gòu)化工作流網(wǎng)； 日志完整性； 重構(gòu)算法

中圖分類號：TP311文獻標(biāo)志碼：A

文章編號：1001-3695(2007)03-0027-03

工作流管理是近年來發(fā)展最為迅速的計算機應(yīng)用技術(shù)之一，它已被廣泛地應(yīng)用于辦公自動化、業(yè)務(wù)流程重組(Business Process Reengineering，BPR) 及其他需要規(guī)劃和管理工作流的領(lǐng)域。但通過對目前大多數(shù)工作流系統(tǒng)的分析，發(fā)現(xiàn)它們往往是一個缺乏反饋的開環(huán)控制模型。這樣的模型易出現(xiàn)以下一些問題：①在流程定義階段，定義的流程是否能夠真實反映當(dāng)前企業(yè)實際流程；②在流程實施階段，實際的業(yè)務(wù)活動是否與設(shè)計的流程活動相吻合。這些問題的存在，導(dǎo)致目前很多工作流沒有發(fā)揮出應(yīng)有的效能。在文獻[1，5，6]中，提出了一種基于事件的工作流重構(gòu)解決方案。該方案包括構(gòu)建依賴—頻率表、推導(dǎo)依賴—頻率圖、工作流網(wǎng)構(gòu)建三個部分，能夠處理簡單的工作流模式，抑制干擾數(shù)據(jù)影響；但對于在企業(yè)業(yè)務(wù)流程中容易存在的一些復(fù)雜的工作流模式，該方案尚不能有效地處理。本文通過對工作流管理系統(tǒng)應(yīng)用場景中容易出現(xiàn)的復(fù)雜模式的重構(gòu)問題進行分析，通過修正重構(gòu)算法，擴展其適用的日志類型，使重構(gòu)技術(shù)能夠處理更多的實際業(yè)務(wù)流程，達到改善工作流技術(shù)應(yīng)用效能的目的。

1 基本概念1.1 結(jié)構(gòu)化工作流網(wǎng)

一個工作流網(wǎng)N可定義為一個三元組（P，T，E）。N是一個結(jié)構(gòu)化工作流（Structured Workflow，SWF）網(wǎng)，必須滿足下面三個條件：

SWF網(wǎng)作為工作流網(wǎng)的一類，允許WfMC[2]規(guī)范所有的路由結(jié)構(gòu)，如順序、并發(fā)、條件和循環(huán)路由，以及基本的塊結(jié)構(gòu)（并發(fā)、同步聚合、選擇執(zhí)行、異或聚合等）。SWF網(wǎng)的結(jié)構(gòu)對網(wǎng)絡(luò)行為的表達能力很強，因而在工作流建模中受到了廣泛支持，是一種強壯的工作流模型分析工具，有著很好的理論支持[3]。

1.2 工作流事件之間的排序關(guān)系

一個工作流日志W為事件序列q的集合。一個事件可以用一個流程實例和一個任務(wù)標(biāo)志符來表述，e=(c，t)。工作流事件e就是任務(wù)t相對于一個給定流程實例c的執(zhí)行。一個典型的工作流日志如表1所示。

假設(shè)A、B是工作流事件，W是工作流日志。下面定義工作流事件之間的四種排序關(guān)系：

(1)跟隨關(guān)系A(chǔ)>wB。當(dāng)且僅當(dāng)在事件序列中出現(xiàn)事件跟隨記錄，如從日志記錄中可以直接查找到事件B跟隨事件A后面的記錄。

2 復(fù)雜模式重構(gòu)問題分析

文獻[4]通過改進傳統(tǒng)Petri 網(wǎng)的變遷元素和增加觸發(fā)機制，提出了二十余種工作流模式。這些模式雖為大多數(shù)學(xué)者所接受，但其中仍有一些模式有待商榷。限于篇幅，不討論這些問題，仍沿用Aalst提出的模式。自循環(huán)、互為循環(huán)、內(nèi)置任務(wù)、重復(fù)任務(wù)、不可見庫所、非自由選擇等模式在文獻[4]中被定義為工作流模型中的復(fù)雜模式。在這些模式中，自循環(huán)和互為循環(huán)模式在實際工作流中容易出現(xiàn)，而文獻[1]中提出的重構(gòu)方法不能處理這些模式，需要進行改進。

2.1 自循環(huán)任務(wù)模式（圖1）

在自循環(huán)任務(wù)模式中 ，同一個任務(wù)可以被順序執(zhí)行多次。這種模式自身隱含了一個條件判斷，根據(jù)該條件，任務(wù)自身執(zhí)行多次。例如，必須進行三次集體討論才能形成決議的任務(wù)。但要在流程模型中描述這種任務(wù)，其輸入庫所P_I必須等于其輸出庫所P_O。對于SWF網(wǎng)而言，自循環(huán)任務(wù)只能有一個連接庫所。圖1（b)的網(wǎng)絡(luò)就是通過重構(gòu)算法得出的網(wǎng)絡(luò)。該網(wǎng)中，自循環(huán)任務(wù)A與兩個庫所相連。導(dǎo)致這種情況出現(xiàn)的原因是：根據(jù)1.2節(jié)中對因果關(guān)系→w的定義，不可能出現(xiàn)A>_wA和A≯_wA關(guān)系同時存在的情況，所以無法推導(dǎo)出A→_wA關(guān)系。

2.2 互循環(huán)任務(wù)模式（圖2）

就互循環(huán)任務(wù)模式而言，文獻[1]中的算法可以推導(dǎo)出任務(wù)之間的并發(fā)關(guān)系，但是在推導(dǎo)出的兩個任務(wù)之間卻沒有聯(lián)系。圖2（a）的網(wǎng)絡(luò)N₁和N₁是原始網(wǎng)絡(luò)，圖2（b）的網(wǎng)絡(luò)是通過算法重構(gòu)得到的。在重構(gòu)出來的網(wǎng)絡(luò)中，任務(wù)A和B之間沒有任何輸入/輸出弧相關(guān)聯(lián)。但如果在A、B之間加入跟隨關(guān)系A(chǔ)→_wB和B→_wA，那么文獻[1，5，6]中的算法也能夠?qū)₁和N₂進行正確重構(gòu)。

3 復(fù)雜模式的重構(gòu)

在文獻[1]中重構(gòu)算法包括構(gòu)建依賴—頻率表、推導(dǎo)依賴—頻率圖和構(gòu)建工作流網(wǎng)三個階段。再增加兩個階段，即前驅(qū)處理（預(yù)處理）和后置處理。在前驅(qū)處理階段，修正日志完整性假設(shè)，使所有事件之間的序關(guān)系可以得到，將日志和得到的排序關(guān)系作為輸入，根據(jù)重構(gòu)算法，可重構(gòu)出一個SWF網(wǎng)；在后置處理階段，對已經(jīng)得到的SWF網(wǎng)進行調(diào)整，就可以適應(yīng)于更多實際情況中的工作流。 下面通過自循環(huán)任務(wù)和（兩個任務(wù)之間）互循環(huán)任務(wù)模式為例來闡明如何對復(fù)雜模式進行處理。其中對于自循環(huán)任務(wù)模式，處理集中在前驅(qū)階段和后置階段；對于互循環(huán)任務(wù)模式，處理集中在前驅(qū)階段，主要是對日志完整性和序關(guān)系進行重新定義。

3.1 自循環(huán)任務(wù)模式處理

為了在SWF網(wǎng)中處理自循環(huán)任務(wù)模式，需要解決兩個問題：在日志中如何定義該模式；在SWF網(wǎng)中如何通過簡單模式對其進行圖形化描述。

如果在日志W中出現(xiàn)類似事件序列t₁t₁，如圖1的日志，存在這樣的事件序列xaay。

網(wǎng)結(jié)構(gòu)：對于SWF網(wǎng)而言，自循環(huán)任務(wù)模式可認(rèn)為是圖1所示的結(jié)構(gòu)，該結(jié)構(gòu)由三個任務(wù)和一個庫所構(gòu)成，其中任務(wù)A僅與一個庫所相連接。

自循環(huán)任務(wù)模式的SWF網(wǎng)結(jié)構(gòu)定義：

（1）任務(wù)A在SWF網(wǎng)中，不與起始庫所或者結(jié)束庫所相關(guān)聯(lián)。

（2）任務(wù)A不能有一個以上的輸入庫所。根據(jù)SWF網(wǎng)的定義，SWF網(wǎng)不允許同步和選擇結(jié)構(gòu)同時出現(xiàn)。

（3）任務(wù)A不能有一個以上的輸出庫所；因為這些庫所可能包含不止一個托肯。SWF網(wǎng)是安全的Petri網(wǎng)，而被稱為安全的充要條件是托肯的最大數(shù)目不超過1。

（4）至少需要兩個其他任務(wù)（X和Y），任務(wù)X需要在與A相連的唯一庫所中放置一個托肯。

循環(huán)任務(wù)A，輸入任務(wù)X和輸出任務(wù)Y可以在日志W(wǎng)中被標(biāo)志。對于任何一個這樣的結(jié)構(gòu)，最少包括三種因果關(guān)系：X→_wY、X→_wA和A→_wY。此外，由于任務(wù)A僅與一個庫所相關(guān)聯(lián)，如果將任務(wù)A從這個結(jié)構(gòu)中移走，而X→_wY跟隨關(guān)系的存在，庫所P₁仍可以被挖掘出來。換句話說，在不考慮任務(wù)A時，仍可以通過文獻[1]中的算法對工作流日志進行分析，重構(gòu)出基本SWF網(wǎng)結(jié)構(gòu)。

基于上述推理，本文進行下面的處理：

（1）增加一個前驅(qū)處理階段，在這個階段，任務(wù)A及其相鄰任務(wù)X和Y都被標(biāo)記和記錄。將這個任務(wù)A從日志中除去，由上所述，X→_wY關(guān)系存在，那么基本的SWF網(wǎng)仍能夠被重構(gòu)出來。

（2）將文獻[1]中的算法運用到經(jīng)過處理的日志上，將會得到一個工作流網(wǎng)，這個網(wǎng)包含著X→_wY因果關(guān)系和庫所P₁。

（3）再增加一個后置處理階段，在這個階段，根據(jù)已有的事件記錄，任務(wù)A應(yīng)關(guān)聯(lián)到正確的庫所P₁上。

該方法不需要修改文獻[1]中的重構(gòu)算法，僅需增加兩個輔助階段來處理這種復(fù)雜模式。

3.2 互循環(huán)任務(wù)模式的處理

根據(jù)1.3節(jié)中日志完整性定義，無法區(qū)分兩個任務(wù)之間的關(guān)系是并發(fā)還是相互循環(huán)。換句話說，任務(wù)A和B之間可能因為相互依賴而構(gòu)成循環(huán)。一個需要兩個資源協(xié)作且具有嚴(yán)格執(zhí)行順序的模式，就可以視為互循環(huán)任務(wù)模式。例如，需要兩位作者相互協(xié)作來共同完成一個文檔的編寫，作者甲先編寫前面三節(jié)，完成后交給作者乙；乙開始編寫第四、五節(jié)，完成后交給甲；甲再開始編寫第六、七節(jié)，完成后交給乙；乙編寫第八、九、十節(jié)……直到寫完最后一節(jié)，編寫文檔工作結(jié)束，進入下一個任務(wù)。根據(jù)日志完整性的定義，一個日志即使不包含aba這樣的事件序列，也是完備的。例如在圖1中的N₁，日志W(wǎng) ={xay，xabw，xw，zbw，zbay，zy}就可以認(rèn)為是完備的，但是該日志并沒有包含aba。互循環(huán)任務(wù)的處理（圖3），首先需要對日志完整性進行重新定義。

在SWF網(wǎng)結(jié)構(gòu)中，根據(jù)1.2節(jié)中事件序關(guān)系的定義，對于圖3任務(wù)A和B之間的關(guān)系，利用文獻[1，5，6]中的算法進行處理，往往將任務(wù)A、B推導(dǎo)為并發(fā)任務(wù)。如果要處理互循環(huán)任務(wù)模式，就需要對日志完整性以及事件序關(guān)系的定義進行修正。在日志完整性定義中，原來僅假設(shè)日志W(wǎng)相對跟隨關(guān)系>w是完備的。在修訂版本中，日志完整性不僅是指兩兩任務(wù)實例之間的跟隨關(guān)系，日志是完備的；對于發(fā)生在三個任務(wù)之間的跟隨關(guān)系，日志同樣應(yīng)是完備的。如果aba事件序列存在，一個完備的日志W(wǎng)就必須包含這種記錄?；诖耍覀儗ぷ髁魇录呐判蜿P(guān)系進行重新定義：

根據(jù)定義1，能夠?qū)⒉l(fā)任務(wù)與互循環(huán)任務(wù)區(qū)分出來，兩個任務(wù)a和b（a≠b）為并發(fā)任務(wù)的充要條件是，當(dāng)且僅當(dāng)在日志W(wǎng)中沒有出現(xiàn)類似aba這樣的事件序列子串。在新定義的基礎(chǔ)上，再結(jié)合文獻[1，5，6]中提出的算法，通過構(gòu)造依賴—頻率表，推導(dǎo)出依賴—頻率圖，結(jié)合圖與表來重構(gòu)工作流網(wǎng)。

3.2.1 構(gòu)建依賴—頻率表

這個步驟主要是通過在日志中分析流程各事件的總發(fā)生次數(shù)（#A、#B）、事件之間的跟隨記錄（#A>B、#B>A），來推導(dǎo)出事件之間的局部依賴強度(記為$A→L B，A、B代表流程中的任意兩個事件，兩者可以是相鄰事件也可以是非相鄰事件)，以及全局依賴關(guān)系強度(記為$A→B)。

在一個流程實例中，任務(wù)A和B之間可以有多個任務(wù)，N是這些事件的總數(shù)，那么全局依賴關(guān)系強度$A→B可視為關(guān)聯(lián)因子δ的指數(shù)函數(shù)(δ)n，δ取值范圍為[0，1]。根據(jù)實驗數(shù)據(jù)，δ=0.8較好。當(dāng)任務(wù)B直接發(fā)生在任務(wù)A的后面，若兩者之間沒有其他工作流事件，N＝0，$A→B值最大取為1；隨著N增加，依賴關(guān)系逐漸減弱。對所有流程實例的日志進行這樣的處理，用得到的值除以min(＃A，#B)，就可以得出工作流事件A與B之間的全局依賴關(guān)系的強度。

3.2.2 推導(dǎo)依賴—頻率圖

一般說來，沒有必要為每一對工作流事件建立一個規(guī)則來判斷兩者之間是否存在因果關(guān)系。每一個非初始事件必然有一個導(dǎo)致其發(fā)生的事件；每一個非最終的事件必然要有一個依賴它的事件。利用這些信息，可大大縮小查找范圍。對于兩個工作流事件X和Y依賴關(guān)系(記為DE(X，Y))的啟發(fā)式定義如下：

其中，A>X表示DE(A，X)取值最大的事件是X；Y>A 表示DE(Y，A) 取值最大的事件是Y。在工作流日志上利用上面的定義可以導(dǎo)出依賴—頻率圖，圖中所有連接均與模型定義相吻合，且沒有遺漏。

3.2.3 從依賴—頻率圖中生成工作流網(wǎng)

依賴—頻率圖上沒有確定分支、匯聚的類型。但根據(jù)依賴—頻率表的信息，再結(jié)合依賴—頻率圖中的節(jié)點頻率，最終可以判斷匯聚/分支的類型。例如，要檢測從任務(wù)A到任務(wù)B和C的分支類型是與還是或，可以查看依賴—頻率表中的#B>C和#C>B。若是與分支，也即存在著關(guān)系B//C，那么B>C和BC和C>B的情況都不會出現(xiàn)。

4 實驗

為了驗證改進后算法的性能，本文基于UOSFLOW進行了一組實驗。UOSFLOW是中興通信按照WfMC規(guī)范，采用面向服務(wù)的設(shè)計思想，基于J2EE架構(gòu)開發(fā)的分布式工作流管理系統(tǒng)。該系統(tǒng)包括工作流執(zhí)行引擎、工作流設(shè)計器、流程管理監(jiān)控、工作流仿真模塊以及流程重構(gòu)模塊。流程重構(gòu)通過分析流程日志來完成。

在實驗中，日志數(shù)據(jù)可以是來自一個運行著的信息管理系統(tǒng)；也可以是手工生成的日志文件；還可以通過工作流仿真器產(chǎn)生仿真日志。 為了評估該算法，使用上述所有的三種方式。在表2中，*T表示流程中包含的總?cè)蝿?wù)數(shù)，*L表示流程執(zhí)行次數(shù)，*E則表示算法的執(zhí)行時間（單位是s）。

為了對算法進行全面的評估，實驗中*T最大取值達到100，能完全滿足實際業(yè)務(wù)流程的需求；*L最大取值達到500（在這種情況下，日志文件大小約為10 MB），這樣大的樣本可以充分測試算法的性能。從表2中可以明確地得出，改進后的算法仍具有很好的性能，可以很好地滿足大多數(shù)具有復(fù)雜模式的實際業(yè)務(wù)流程的重構(gòu)工作。

5 結(jié)束語

在文獻[1，5，6]中，通過對工作流日志中的事件記錄進行分析，提出一種基于工作流事件的重構(gòu)算法。算法能夠?qū)Υ蟛糠止ぷ髁鬟M行重構(gòu)處理，但在識別具有復(fù)雜模式的工作流時，仍存在著不完整性。本文分析了在實際工作流中易出現(xiàn)的復(fù)雜模式，探究了文獻[1，5，6]算法不能處理這些復(fù)雜模式的原因。通過對該算法進行修正，包括重定義日志完整性和事件排序關(guān)系，增加相應(yīng)的預(yù)處理階段和后置處理階段等，使該算法能夠?qū)@些復(fù)雜模式進行有效處理。未來還有大量的工作，包括對重復(fù)任務(wù)、內(nèi)置庫所以及非自由選擇等復(fù)雜模式的研究。總之，我們希望通過擴展和完善該算法，來處理更多類型的工作流日志。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。