工作流模型時(shí)間與費(fèi)用性能評(píng)估算法

潘 軍 劉 麗

(北京航空航天大學(xué)飛行器控制一體化技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100191)

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

1 工作流過(guò)程模型

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

1)節(jié)點(diǎn)類(lèi)型.

①活動(dòng)節(jié)點(diǎn):普通節(jié)點(diǎn)、子過(guò)程節(jié)點(diǎn);

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

③標(biāo)志節(jié)點(diǎn):開(kāi)始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn).

2)有向連接弧類(lèi)型.

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

2 無(wú)環(huán)模型評(píng)估算法

2.1 系數(shù)值法

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

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

系數(shù)值法的計(jì)算過(guò)程是按照活動(dòng)圖的基本的拓?fù)漤樞蛞来芜M(jìn)行計(jì)算.對(duì)于沒(méi)有錯(cuò)誤的無(wú)環(huán)模型，計(jì)算完成后結(jié)束節(jié)點(diǎn)的系數(shù)值等于1.

2.2 進(jìn)度與費(fèi)用評(píng)估算法

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

模型的費(fèi)用計(jì)算公式:

其中，ci為節(jié)點(diǎn)i的費(fèi)用估計(jì)值;ki為節(jié)點(diǎn)i的系數(shù)值，無(wú)環(huán)結(jié)構(gòu)中0≤ki≤1.

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

1)開(kāi)始節(jié)點(diǎn)的完成時(shí)間為0，即T1=0;

2)活動(dòng)節(jié)點(diǎn)、與分支節(jié)點(diǎn)和或分支節(jié)點(diǎn)的完成時(shí)間為該節(jié)點(diǎn)的前連接節(jié)點(diǎn)的完成時(shí)間加上活動(dòng)耗費(fèi)的時(shí)間，即 Tw=Tv+tw，(v，w)∈E;

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

4)或匯聚節(jié)點(diǎn)的完成時(shí)間計(jì)算公式為

對(duì)模型中的所有的節(jié)點(diǎn)按照拓?fù)漤樞驈拈_(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)遍歷計(jì)算完成后，則TWF=Tn.

無(wú)環(huán)工作流模型進(jìn)度與費(fèi)用評(píng)估算法步驟:

1)假設(shè)有n個(gè)活動(dòng)節(jié)點(diǎn)，初始化每一個(gè)活動(dòng)節(jié)點(diǎn)的時(shí)間ti和費(fèi)用ci.邏輯節(jié)點(diǎn)和標(biāo)志節(jié)點(diǎn)的時(shí)間ti=0，費(fèi)用ci=0.對(duì)n個(gè)節(jié)點(diǎn)進(jìn)行簡(jiǎn)單的拓?fù)渑判?，則這n個(gè)節(jié)點(diǎn)中第1個(gè)節(jié)點(diǎn)為開(kāi)始節(jié)點(diǎn)，第n個(gè)節(jié)點(diǎn)為結(jié)束節(jié)點(diǎn).設(shè)置k1=1，T1=0;

2)參照系數(shù)法的規(guī)則，依照拓?fù)漤樞驈拈_(kāi)始節(jié)點(diǎn)開(kāi)始依次計(jì)算每一個(gè)節(jié)點(diǎn)的系數(shù)值;

3)利用費(fèi)用計(jì)算公式計(jì)算工作流模型的平均費(fèi)用CWF;

4)按照進(jìn)度計(jì)算規(guī)則，依照拓?fù)漤樞驈拈_(kāi)始節(jié)點(diǎn)開(kāi)始依次計(jì)算每一個(gè)節(jié)點(diǎn)的Ti，計(jì)算完后TWF=Tn.

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

3 循環(huán)結(jié)構(gòu)的提取算法

3.1 基本定義

強(qiáng)連通分量定義:有向圖強(qiáng)連通分量在有向圖G中，如果2個(gè)節(jié)點(diǎn)vi和vj之間有一條從vi到vj的路徑，同時(shí)還有一條從vj到vi的路徑，則稱(chēng)兩個(gè)頂點(diǎn)強(qiáng)連通.如果有向圖G中任意兩個(gè)頂點(diǎn)都強(qiáng)連通，那么圖G就為強(qiáng)連通圖.非強(qiáng)連通圖的極大強(qiáng)連通子圖，稱(chēng)為強(qiáng)連通分量.計(jì)算有向圖模型的強(qiáng)連通分量的常用算法為T(mén)arjan［5］算法.

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

圖1 連接弧分類(lèi)示例模型

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

本文定義七元組來(lái)標(biāo)識(shí)每一個(gè)循環(huán)結(jié)構(gòu):

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

3.2 NN元素分析

一個(gè)循環(huán)結(jié)構(gòu)一般由1個(gè)標(biāo)志或分支節(jié)點(diǎn)和至少一個(gè)標(biāo)志或匯聚節(jié)點(diǎn)組成.因?yàn)橥荒Ｐ椭腥我?個(gè)循環(huán)結(jié)構(gòu)的這4個(gè)元素是不可能完全相同的，所以七元組中后4個(gè)元素可以作為一個(gè)循環(huán)結(jié)構(gòu)的主要標(biāo)志元素.通過(guò)對(duì)連接弧集合E進(jìn)行分析，得到所有的條件連接弧中屬于循環(huán)條件連接弧的數(shù)量m，m即為該模型中循環(huán)結(jié)構(gòu)的數(shù)量.分析模型中循環(huán)條件連接弧的作用，如果將其斷開(kāi)，那么對(duì)應(yīng)的循環(huán)結(jié)構(gòu)在整個(gè)模型中將不再存在.用一個(gè)布爾數(shù)組Enable［m］來(lái)表示該循環(huán)條件連接弧是否是斷開(kāi)，當(dāng)其值為0時(shí)，表示該循環(huán)連接弧是斷開(kāi)的.當(dāng)所有的循環(huán)條件連接弧都斷開(kāi)后，有環(huán)模型就變成了無(wú)環(huán)模型.

用七元組就能單獨(dú)表示和分析一個(gè)循環(huán)結(jié)構(gòu).下面改進(jìn)Tarjan算法，使得能夠求得每一個(gè)循環(huán)結(jié)構(gòu).

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

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

3.3 NK與CK元素分析算法

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

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

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

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

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

3.4 條件概率更新

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

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

1)對(duì)于循環(huán)結(jié)構(gòu)的標(biāo)志或分支節(jié)點(diǎn).

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

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

2)對(duì)于循環(huán)結(jié)構(gòu)的非標(biāo)志或分支節(jié)點(diǎn).

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

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

PAct:該或分支節(jié)點(diǎn)到該循環(huán)結(jié)構(gòu)標(biāo)志或分支節(jié)點(diǎn)的概率值.

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

PHuofen:此次提取的循環(huán)結(jié)構(gòu)的標(biāo)志或分支節(jié)點(diǎn)的循環(huán)條件概率值.

KHuofen:循環(huán)結(jié)構(gòu)的標(biāo)志或分支節(jié)點(diǎn)到該或分支節(jié)點(diǎn)的概率值.

如果 Type［i］=1，則

如果 Type［i］=0，則

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

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

③PHuofen計(jì)算規(guī)則.在提取循環(huán)結(jié)構(gòu)時(shí)，EHF對(duì)應(yīng)的循環(huán)條件轉(zhuǎn)移概率為αi，則PHuofen=αi.

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

3.5 七元組分析算法

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

循環(huán)結(jié)構(gòu)提取算法步驟:

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

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

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

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

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

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

4 任意模型進(jìn)度與費(fèi)用評(píng)估算法

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

4.1 標(biāo)志或分支節(jié)點(diǎn)參數(shù)分析

確定模型中標(biāo)志或分支節(jié)點(diǎn)的個(gè)數(shù)n.定義布爾數(shù)組Q［n］，初始值為0，表示該標(biāo)志或分支節(jié)點(diǎn)沒(méi)有計(jì)算過(guò).

標(biāo)志或分支節(jié)點(diǎn)進(jìn)度和費(fèi)用計(jì)算步驟:

1)初始化Q［n］;

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

3)確定第i個(gè)標(biāo)志或分支節(jié)點(diǎn)對(duì)應(yīng)的m個(gè)七元組，設(shè)置j=1;

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

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

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

得到每個(gè)標(biāo)志或分支節(jié)點(diǎn)的進(jìn)度和費(fèi)用值后，就可以評(píng)估整個(gè)模型的進(jìn)度和費(fèi)用值.

整個(gè)模型進(jìn)度與費(fèi)用分析步驟:

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

2)計(jì)算每一個(gè)標(biāo)志或分支節(jié)點(diǎn)的進(jìn)度和費(fèi)用值;

3)用無(wú)環(huán)算法計(jì)算模型費(fèi)用值CWF和進(jìn)度值TWF.

5 實(shí)例分析

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

圖3 復(fù)雜工作流模型實(shí)例

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

表1活動(dòng)節(jié)點(diǎn)參數(shù)信息

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

6 結(jié)束語(yǔ)

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

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)格工作流費(fèi)用優(yōu)化方法［J］.計(jì)算機(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］范玉順.工作流管理技術(shù)基礎(chǔ)［M］.北京:清華大學(xué)出版社，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