潘 軍 劉 麗

(北京航空航天大學飛行器控制一體化技術重點實驗室，北京100191)

工作流管理的目標是，通過將工作活動有序化，以及合理地調(diào)用與這些活動相關聯(lián)的人力資源和信息資源，來幫助企業(yè)高效地達到業(yè)務目標.在已有的研究中，Petri網(wǎng)已經(jīng)被廣泛地應用于業(yè)務流程的性能分析中［1］.另一方面，工作流的設計者可能從以前活動執(zhí)行情況的統(tǒng)計信息中獲得，或根據(jù)自己的經(jīng)驗估算出工作流每個活動的大概執(zhí)行時間，他們希望有一種有效的時間性能評估方法，來估計工作流程的平均周轉時間.也有很多學者針對工作流模型的費用的計算算法進行研究，但是大多研究針對的是無環(huán)結構［2］.

1 工作流過程模型

一個完整的工作流模型包括節(jié)點集合N和有向連接弧集合E兩類［3］，具體類型包括:

1)節(jié)點類型.

①活動節(jié)點:普通節(jié)點、子過程節(jié)點;

②邏輯節(jié)點:與分支、或分支、與匯聚和或匯聚節(jié)點;

③標志節(jié)點:開始節(jié)點、結束節(jié)點.

2)有向連接弧類型.

包括普通連接弧、條件連接弧.連接弧是一個二元組(i，j)，i，j分別為連接弧前后節(jié)點索引號.每一個條件連接弧都設有一個條件概率參數(shù)α.

2 無環(huán)模型評估算法

2.1 系數(shù)值法

無環(huán)工作流模型系數(shù)值法采用系數(shù)值傳遞的計算規(guī)則如下.

開始節(jié)點的系數(shù)值總是為1，并將該系數(shù)值傳遞給后續(xù)節(jié)點.與分支節(jié)點的系數(shù)值等于前節(jié)點傳遞來的系數(shù)值，并傳遞該系數(shù)值給所有的后續(xù)連接節(jié)點.與匯聚節(jié)點的系數(shù)值等于前節(jié)點傳遞來的系數(shù)值任意一個，并傳遞該系數(shù)值給后續(xù)節(jié)點.或分支節(jié)點的系數(shù)值等于前連接節(jié)點傳遞來的系數(shù)值，傳遞給或分支的后連接節(jié)點的系數(shù)值等于或分支節(jié)點的系數(shù)值乘以或分支節(jié)點到該后連接節(jié)點的條件概率值.或匯聚節(jié)點的系數(shù)值等于所有前節(jié)點傳遞來的系數(shù)值之和，并將該系數(shù)值傳遞給后連接節(jié)點.活動節(jié)點的系數(shù)值等于前節(jié)點傳遞來的系數(shù)值，并傳遞該值到后續(xù)節(jié)點.

系數(shù)值法的計算過程是按照活動圖的基本的拓撲順序依次進行計算.對于沒有錯誤的無環(huán)模型，計算完成后結束節(jié)點的系數(shù)值等于1.

2.2 進度與費用評估算法

分析無環(huán)工作流結構，計算出每一個節(jié)點在該模型中的系數(shù)值，再用下面的公式和規(guī)則計算出該模型的費用值和進度值.

模型的費用計算公式:

其中，ci為節(jié)點i的費用估計值;ki為節(jié)點i的系數(shù)值，無環(huán)結構中0≤ki≤1.

工作流模型進度的計算［4］參照下列規(guī)則:

1)開始節(jié)點的完成時間為0，即T1=0;

2)活動節(jié)點、與分支節(jié)點和或分支節(jié)點的完成時間為該節(jié)點的前連接節(jié)點的完成時間加上活動耗費的時間，即 Tw=Tv+tw，(v，w)∈E;

3)與匯聚節(jié)點的完成時間為其所有前連接節(jié)點的完成時間的最大值加上自身節(jié)點耗費的時間，即 Tw=max(Tv+tw)，(v，w)∈E;

4)或匯聚節(jié)點的完成時間計算公式為

對模型中的所有的節(jié)點按照拓撲順序從開始節(jié)點到結束節(jié)點遍歷計算完成后，則TWF=Tn.

無環(huán)工作流模型進度與費用評估算法步驟:

1)假設有n個活動節(jié)點，初始化每一個活動節(jié)點的時間ti和費用ci.邏輯節(jié)點和標志節(jié)點的時間ti=0，費用ci=0.對n個節(jié)點進行簡單的拓撲排序，則這n個節(jié)點中第1個節(jié)點為開始節(jié)點，第n個節(jié)點為結束節(jié)點.設置k1=1，T1=0;

2)參照系數(shù)法的規(guī)則，依照拓撲順序從開始節(jié)點開始依次計算每一個節(jié)點的系數(shù)值;

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

4)按照進度計算規(guī)則，依照拓撲順序從開始節(jié)點開始依次計算每一個節(jié)點的Ti，計算完后TWF=Tn.

這些算法能很有效地分析無環(huán)模型，對于有環(huán)模型，本文提出了將有環(huán)模型轉化為無環(huán)模型的算法，再利用無環(huán)模型算法進行分析.

3 循環(huán)結構的提取算法

3.1 基本定義

強連通分量定義:有向圖強連通分量在有向圖G中，如果2個節(jié)點vi和vj之間有一條從vi到vj的路徑，同時還有一條從vj到vi的路徑，則稱兩個頂點強連通.如果有向圖G中任意兩個頂點都強連通，那么圖G就為強連通圖.非強連通圖的極大強連通子圖，稱為強連通分量.計算有向圖模型的強連通分量的常用算法為Tarjan［5］算法.

條件連接弧可以用來組成循環(huán)結構和選擇結構，將條件連接弧分為2類:循環(huán)條件連接弧和非循環(huán)條件連接弧.圖1中條件連接弧1是循環(huán)條件連接弧，2和3為非循環(huán)條件連接弧.將或匯聚的前連接弧也分為2類，循環(huán)普通連接弧和非循環(huán)普通連接弧.圖1中連接弧4是循環(huán)普通連接弧，連接弧5是非循環(huán)普通連接弧.

圖1 連接弧分類示例模型

對于單環(huán)模型，節(jié)點數(shù)大于1的強連通分量就是一個循環(huán)結構.對于多環(huán)模型，直接用Tarjan算法得到的強連通分量是由多個循環(huán)結構耦合而成，因此通過改進Tarjan算法來提取出模型中的每一個循環(huán)結構.

本文定義七元組來標識每一個循環(huán)結構:

其中，NN為循環(huán)結構中所有節(jié)點的集合;NK為循環(huán)結構中所有節(jié)點的系數(shù)值集合;CK為該循環(huán)結構的強連通分量系數(shù);NHF為循環(huán)結構中標志或分支節(jié)點在節(jié)點集合N中的索引號;EHF為循環(huán)結構中標志或分支節(jié)點的后循環(huán)條件連接弧在連接弧集合E中的索引號;NHH為循環(huán)結構中標志或匯聚節(jié)點集合在節(jié)點集合N中的索引號構成的集合;EHH為循環(huán)結構中標志或匯聚節(jié)點的前循環(huán)連接弧集合在連接弧集合E中的索引構成的集合.

3.2 NN元素分析

一個循環(huán)結構一般由1個標志或分支節(jié)點和至少一個標志或匯聚節(jié)點組成.因為同一模型中任意2個循環(huán)結構的這4個元素是不可能完全相同的，所以七元組中后4個元素可以作為一個循環(huán)結構的主要標志元素.通過對連接弧集合E進行分析，得到所有的條件連接弧中屬于循環(huán)條件連接弧的數(shù)量m，m即為該模型中循環(huán)結構的數(shù)量.分析模型中循環(huán)條件連接弧的作用，如果將其斷開，那么對應的循環(huán)結構在整個模型中將不再存在.用一個布爾數(shù)組Enable［m］來表示該循環(huán)條件連接弧是否是斷開，當其值為0時，表示該循環(huán)連接弧是斷開的.當所有的循環(huán)條件連接弧都斷開后，有環(huán)模型就變成了無環(huán)模型.

用七元組就能單獨表示和分析一個循環(huán)結構.下面改進Tarjan算法，使得能夠求得每一個循環(huán)結構.

1)遍歷模型中所有的或分支節(jié)點，判斷其所有的后向連接弧是否是循環(huán)連接弧.如果有則建立一個七元組，計算NHF和EHF.計算完成后會得到m個七元組，分別代表著m個循環(huán)結構.建立布爾數(shù)組Enable［m］，并初始化為0;

2)從第1個七元組開始，斷開除該循環(huán)結構的所有其他m-1個循環(huán)連接弧，即在分析第i個循環(huán)結構時:如果k=i那么Enable［k］=1;反之Enable［k］=0.利用Tarjan算法分析模型.其中節(jié)點個數(shù)不為1的強連通分量即為該循環(huán)結構，該強連通分量的節(jié)點集合構成七元組中的NN元素.分析NN集合中的或匯聚節(jié)點和其前循環(huán)普通連接弧，并將其中的標志或匯聚節(jié)點和循環(huán)一般連接弧信息存儲在NHH和EHH這2個元素中.

3.3 NK與CK元素分析算法

提取某一個循環(huán)結構時需要計算CK和NN集合內(nèi)的所有節(jié)點的系數(shù)值NK.算法步驟如下:

1)備份所有條件連接弧的條件概率值;

2)NN集合內(nèi)非當前循環(huán)結構標志或分支節(jié)點的條件概率值需要重新計算.為每個或分支節(jié)點定義一個布爾數(shù)組Cycle［n］，n表示該或分支節(jié)點的后非循環(huán)條件連接弧的個數(shù).第i個條件連接弧的后連接節(jié)點在NN集合內(nèi)則Cycle［i］=1，反之為0，再利用式(3)進行計算，PArc的定義在后面會提到.

3)將循環(huán)結構在標志或分支節(jié)點處斷開，利用無環(huán)結構系數(shù)法計算所有NN集合內(nèi)節(jié)點的系數(shù)值NK，計算該循環(huán)結構的強連通分量系數(shù)CK.用αi表示當前提取的循環(huán)結構中EHF元素代表的循環(huán)條件連接弧的條件概率值，則CK=αi/(1-αi);

4)還原所有條件連接弧的條件概率值.

3.4 條件概率更新

提取完某一個循環(huán)結構時，需要對該循環(huán)結構NN中的或分支節(jié)點的條件連接弧的條件概率進行重新計算，節(jié)點示意圖如圖2所示.

圖2 或分支節(jié)點示例圖

1)對于循環(huán)結構的標志或分支節(jié)點.

假設該或分支節(jié)點有n個條件連接弧，其中1到m是循環(huán)條件連接弧，那么或分支節(jié)點將是m個循環(huán)結構體的標志節(jié)點，后n-m個是非循環(huán)條件連接弧.每個連接弧的條件概率值為αi.

定義一個布爾數(shù)組Pick［n］表示這個或分支節(jié)點的條件連接弧是否已經(jīng)提取過，初始值都為1，表示沒有提取過.那么在提取第j個循環(huán)條件連接弧代表的循環(huán)結構之后，Pick［j］=0，對于第i個條件連接弧，如果 Pick［i］=1，那么 αi=αi/(1-αj).

2)對于循環(huán)結構的非標志或分支節(jié)點.

假設該或分支節(jié)點有n個非循環(huán)條件連接弧，其中1到m是屬于該循環(huán)結構的條件連接弧，即連接弧的后續(xù)節(jié)點在該循環(huán)結構的節(jié)點集合NN內(nèi)，后n-m個是不屬于該循環(huán)結構的條件連接弧.每一個連接弧的條件概率值為αi.

定義一個布爾數(shù)組Type［n］表示這個或分支節(jié)點的條件連接弧是否屬于循環(huán)結構，值為1時表示屬于.這里需要計算幾個因子:

PAct:該或分支節(jié)點到該循環(huán)結構標志或分支節(jié)點的概率值.

PArc:該條件連接弧到該循環(huán)結構標志或分支節(jié)點的概率值.

PHuofen:此次提取的循環(huán)結構的標志或分支節(jié)點的循環(huán)條件概率值.

KHuofen:循環(huán)結構的標志或分支節(jié)點到該或分支節(jié)點的概率值.

如果 Type［i］=1，則

如果 Type［i］=0，則

①PAct計算規(guī)則.在節(jié)點集合NN范圍內(nèi)，定義一個double數(shù)組K［n］，初始值為0，n為NN集合節(jié)點個數(shù)，循環(huán)結構的標志或分支節(jié)點在集合NN中的編號為NHuofen，該或分支在NN集合中的編號為N1，設置K［N1］=1.0，具體分析過程采用的是系數(shù)值法，從節(jié)點N1開始到節(jié)點 NHuofen結束.計算完成后 PAct=K［NHuofen］.

②PArc計算規(guī)則.在節(jié)點集合NN范圍內(nèi)，定義一個double數(shù)組K［n］，初始值為0，n為NN集合節(jié)點個數(shù)，循環(huán)結構的標志或分支節(jié)點在集合NN中的編號為NHuofen，該或分支節(jié)點在該條件連接弧下的后續(xù)連接節(jié)點在NN集合中的編號為N2，設置K［N2］=1.0.具體分析過程采用的是系數(shù)值傳遞方法，從節(jié)點N2開始到節(jié)點 NHuofen結束.計算完成后 PArc=K［NHuofen］.

③PHuofen計算規(guī)則.在提取循環(huán)結構時，EHF對應的循環(huán)條件轉移概率為αi，則PHuofen=αi.

④KHuofen計算規(guī)則.在節(jié)點集合NN范圍內(nèi)，定義一個double數(shù)組K［n］，初始值為0，n為集合節(jié)點個數(shù).對于NN集合中第i個節(jié)點，如果該節(jié)點為標志或匯聚節(jié)點則K［i］=NK［i］.該或分支在NN集合中的編號為N1，具體的分析過程采用逆向的系數(shù)值查詢方法.具體規(guī)則如下:或分支節(jié)點系數(shù)值等于其前節(jié)點的查詢得到系數(shù)值;或匯聚節(jié)點的系數(shù)值等于其所有的前節(jié)點查詢得到系數(shù)值之和;與匯聚節(jié)點的系數(shù)值等于其某一個前節(jié)點查詢得到的系數(shù)值;與分支節(jié)點的系數(shù)值等于其前節(jié)點查詢得到的系數(shù)值;活動節(jié)點的系數(shù)值等于其前節(jié)點查詢得到的系數(shù)值.對于任意類型的節(jié)點如果其前節(jié)點對應的K［i］≠0，則查詢返回值為K［i］.從節(jié)點N1開始，計算完成后KHuofen=K［N1］.

3.5 七元組分析算法

對于任意的工作流模型，提取出所有的循環(huán)結構，將有環(huán)的工作流模型轉化為無環(huán)模型.定義一個布爾數(shù)組S［m］，m為循環(huán)結構的個數(shù)，該數(shù)組初始值為0，表示循環(huán)結構沒有被提取.

循環(huán)結構提取算法步驟:

1)調(diào)用NN分析模塊，初始化S［m］;

2)按順序判斷S［m］數(shù)組中的值，找到其中布爾值為0的最小編號i;

3)提取NN集合中的除本身循環(huán)結構的標志或分支節(jié)點之外所有標志或分支節(jié)點對應的循環(huán)結構，即對這些循環(huán)結構遞歸調(diào)用步驟3)和步驟4)，遞歸完成后進入步驟4);

4)提取該強連通分量，并利用斷開循環(huán)結構的方法來斷開這個循環(huán)結構，將這個循環(huán)結構轉變?yōu)闊o環(huán)結構.對這個無環(huán)的循環(huán)結構進行系數(shù)法分析，確定NK和CK，并利用上面提到的算法更新其中或分支節(jié)點的條件概率值，并設置S［i］=1;

5)判斷S［m］數(shù)組中是否還有不為1的布爾值，如果存在則跳轉到步驟2)，否則結束計算.

至此得到了所有循環(huán)結構的七元組數(shù)據(jù).

4 任意模型進度與費用評估算法

得到每一個循環(huán)結構七元組數(shù)據(jù)后需要用這些七元組數(shù)據(jù)對模型中的所有標志或分支節(jié)點的費用和進度進行計算.在提取完所有的循環(huán)結構后，節(jié)點集合N中的每一個標志或分支節(jié)點會對應其中的m個七元組，m為該或分支節(jié)點的后循環(huán)條件連接弧的個數(shù).利用七元組中的信息計算對應的費用和進度值作為標志或分支節(jié)點的費用和進度值，再利用無環(huán)費用和進度分析的算法分析整個模型的進度和費用值.

4.1 標志或分支節(jié)點參數(shù)分析

確定模型中標志或分支節(jié)點的個數(shù)n.定義布爾數(shù)組Q［n］，初始值為0，表示該標志或分支節(jié)點沒有計算過.

標志或分支節(jié)點進度和費用計算步驟:

1)初始化Q［n］;

2)按順序判斷Q［n］數(shù)組中的值，找到其中布爾值為0的最小編號i.如果不存在則結束計算;

3)確定第i個標志或分支節(jié)點對應的m個七元組，設置j=1;

4)如果這第j個循環(huán)結構中存在其他的標志或分支節(jié)點k，且 Q［k］=0，則 i=k，并跳轉到步驟3).否則將第j個七元組對應的循環(huán)結構在或分支處斷開，并用無環(huán)結構進度與費用分析算法計算CCycle和TCycle.七元組對應的強連通分量系數(shù)Kj，利用下面的公式更新或分支標志節(jié)點的進度和費用:

5)j=j+1，如果 j≤m，則跳轉到步驟 4)，否則Q［i］=1，并跳轉到步驟2).

4.2 整個模型參數(shù)分析

得到每個標志或分支節(jié)點的進度和費用值后，就可以評估整個模型的進度和費用值.

整個模型進度與費用分析步驟:

1)初始化Enable［m］所有值為0，用系數(shù)法確定該無環(huán)結構的每一個節(jié)點的系數(shù)值;

2)計算每一個標志或分支節(jié)點的進度和費用值;

3)用無環(huán)算法計算模型費用值CWF和進度值TWF.

5 實例分析

以圖3所示中的模型為例，圖中活動節(jié)點的參數(shù)信息如表1所示.其中條件連接弧轉移概率值設置如下:或分支1節(jié)點指向活動9的概率值為0.2，指向活動8的概率值為0.3，指向活動2的概率值為0.2，指向活動6的概率值為0.3.或分支2節(jié)點指向活動3和活動7的概率值都為0.5.或分支3節(jié)點指向活動4和活動5的概率值都為0.5.

圖3 復雜工作流模型實例

本文將算法集成到了工作流管理平臺中.在輸入了上面的參數(shù)后，直接分析得到結果.其中或分支1標志節(jié)點的T=1.5 d，C=300.或分支3標志節(jié)點的T=14.25 d，C=2 850.整個模型的T=16.33 d，C=3266.67.

表1活動節(jié)點參數(shù)信息

本文同時用傳統(tǒng)的多次仿真求平均值算法估算該模型，通過1 000次仿真后得到模型T=16.36 d，C=3272.39，算法的容許誤差為 1%.通過對比得到，該結果與新算法結果近似，誤差只有0.18%.而新算法只需運算一次，執(zhí)行效率極高.對于復雜結構的工作流模型新算法能高效準確地進行進度與費用性能的評估.

6 結束語

本文針對復雜模型的結構特點，提出復雜模型逐步簡化的算法，從而達到評估復雜模型時間和費用性能的目的.利用VC++開發(fā)了工作流管理軟件，并用多種常用實例成功驗證了該算法的可行性.該算法不足之處在于需要有精確并且完整的輸入?yún)?shù).因此在引入復雜的進度和費用參數(shù)模型的計算模型中，該算法需要進一步改進.

References)

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

［2］苑迎春，李小平.基于串規(guī)約的網(wǎng)格工作流費用優(yōu)化方法［J］.計算機研究與發(fā)展，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