基于Petri網(wǎng)的流程變體合并方法*

王吳松，方 歡，鄭雪文

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

1 引言

流程變體(Porcess Variants)可以被定義為系統(tǒng)流程族(模型)中相似但不同(Similar-but- different)的模型，通過對這些模型進(jìn)行映射，從而發(fā)現(xiàn)這些模型間共同擁有的片段以及存在差異的片段。此時，將從模型中通過映射發(fā)現(xiàn)的片段稱為模型的特征，即這些模型至少有一個共同的特征，也至少有一個特征可相互區(qū)分。從粗粒度的流程系統(tǒng)的角度分析，流程變體是流程族模型中從基模型衍生出的其他相似流程模型；從細(xì)粒度的流程系統(tǒng)的角度分析，流程變體是指各流程模型中那些具有某些共性同時又具備各自個性的模型片段。在組織合并、收購或重組的背景下，不同組織之間的業(yè)務(wù)流程往往存在著多種變體結(jié)構(gòu)。對于組織管理者來說，業(yè)務(wù)流程的諸多變體在組織管理時會耗時耗力，同時也會增加運(yùn)營成本。因此，將以前屬于不同組織或分支機(jī)構(gòu)的諸多流程變體進(jìn)行合并，使之成為特定業(yè)務(wù)背景下的單一流程模型，以此來消除冗余。使得不同組織或分支機(jī)構(gòu)能共同使用這一特定業(yè)務(wù)背景下的單一流程模型，從而降低運(yùn)營成本是具有一定實踐意義的。這種做法對于組織或分支機(jī)構(gòu)來說是有益的，因為輸入的流程變體的相關(guān)性降低，合并后的流程模型的規(guī)模會減小，模型規(guī)模的減小反過來又可以提高模型的可維護(hù)性和可理解性。

文獻(xiàn)[1，2]要求通過流程變體發(fā)現(xiàn)的參考模型能使用一些配置手段(移動、刪除、插入)導(dǎo)出其中任意一個流程變體，即可配置性；文獻(xiàn)[3]要求合并模型應(yīng)考慮所有原始模型的行為，即全面性；文獻(xiàn)[4]要求合并過程模型中的每個節(jié)點(diǎn)都能很容易地追溯回其原始模型，即可追溯性。合并流程變體的目的是讓組織管理者能夠查看業(yè)務(wù)流程的多個變體之間的共性和差異，并對其進(jìn)行管理。此外，組織管理者可以對合并模型進(jìn)行更改操作，并將更改操作傳遞給流程變體，而不需要單獨(dú)對每個變體進(jìn)行更改操作。因而，本文中提出的變體合并算法需要滿足上述3個要求。

現(xiàn)有的合并流程模型的方法大致可以分為2類：第1類是基于流程行為[1,2,5 - 11]；第2類是基于標(biāo)簽相似性[6,10,12]。

第1類方法要求合并模型滿足所有輸入模型的行為，這也就意味著合并模型能夠重放每個輸入模型的行為。文獻(xiàn)[1,2]介紹了由一個參考模型通過一些更改操作(刪除、插入、移動)來配置出流程變體，通過啟發(fā)式搜索方法挖掘流程變體進(jìn)而推導(dǎo)出新的參考模型；文獻(xiàn)[5]提出了一種計算合并模型的方法，而文獻(xiàn)[6]在文獻(xiàn)[5]的基礎(chǔ)上加入了從合并模型中提取上下文信息的算法，并將此上下文信息提供給分析師，用于找到模型中需要集中優(yōu)化的片段；文獻(xiàn)[7]研究了在合并模型中可能會遇到的一些問題，同時也從另外的視角對流程模型的合并進(jìn)行了深層次的研究；文獻(xiàn)[8]提出了一種分解驅(qū)動方法，該方法允許從事件日志集合中發(fā)現(xiàn)層次合并流程模型，并且已發(fā)現(xiàn)的層次結(jié)構(gòu)是由嵌套的抽象化流程片段組成，這也就意味著允許在不同的抽象級別上瀏覽可變性；文獻(xiàn)[9]介紹了一種表達(dá)過程行為特征的形式化語言及其語義，并說明了它是如何支持流程合并的；文獻(xiàn)[10]介紹了一種處理流程變體族的建模方法，該方法的關(guān)鍵是在分解步驟即將主流程分解為子流程，以及決定哪些子過程應(yīng)該一起建模和哪些子過程單獨(dú)建模；文獻(xiàn)[11]通過對遺傳過程發(fā)現(xiàn)方法的擴(kuò)展，從事件日志集合中發(fā)現(xiàn)一個能描述一系列流程變體的可配置流程模型。

第2類方法則是只允許合并基于相同標(biāo)簽的流程模型。文獻(xiàn)[6]介紹了4種合并類型：順序合并、并行合并、條件合并和迭代合并，為了避免無效的合并，通過選擇合并點(diǎn)進(jìn)行合并以此產(chǎn)生一個合理的合并模型；隨著可配置流程模型中可配置節(jié)點(diǎn)的增長，搜索空間的大小是按指數(shù)增加的。文獻(xiàn)[9]介紹了一種擴(kuò)展的事件過程驅(qū)動鏈，這種事件過程驅(qū)動鏈可以用來描述單一模型的相似過程集，同時也減少了管理的流程模型的數(shù)量，且可以區(qū)分集合中發(fā)生合并的每個特定元素的流程邏輯。文獻(xiàn)[11]提出了3種策略：基于窮舉搜索的方法、基于遺傳的方法和貪心啟發(fā)式的方法，并利用事件日志從可配置流程模型中配置流程變體，該方法很好地表示了一個特定分支中流程的特征。

現(xiàn)有的流程變體合并方法都是以事件過程驅(qū)動鏈為建模語言，合并方法以Petri網(wǎng)為建模語言的卻很少涉及。而Petri網(wǎng)作為常用系統(tǒng)建模語言之一，由于其簡單性、表達(dá)并發(fā)性的能力、清晰的語義和數(shù)學(xué)性質(zhì)而受到廣泛推崇，并隨之誕生了大量的仿真分析工具，為分析Petri網(wǎng)性質(zhì)提供了極大方便。同時，在已有的合并方法中[1 - 4]，合并后的模型不能同時滿足上述所提出的3個要求，即可追溯性、可配置性和全面性，并且合并后的模型結(jié)構(gòu)在一定程度上過于冗雜，不利于組織管理者理解，即可理解性較差。

本文主要描述了一種基于Petri網(wǎng)的流程變體合并方法，該方法以流程模型的集合作為輸入，并生成可配置的流程模型。可配置的流程模型是一個建模工具，它以集成的方式捕獲了一系列流程模型。同時，生成的流程模型滿足以下3個要求：可追溯性、可配置性和全面性。并且合并后的流程模型在規(guī)模上得到了一定程度的簡化，便于組織管理者更好地理解模型。

2 相關(guān)概念

定義1(流程模型[13]) 滿足下列條件的三元組PM=(P,T;F)是一個流程模型，其中：

(1)P為庫所集，T為變遷集，將庫所集與變遷集中的元素稱為模型的節(jié)點(diǎn)；

(2)P∪T≠?且P∩T=?；

(3)F是PM的流關(guān)系且F∈(P×T)∪ (T×P)；

(4)dom(F)∪cod(F)=P∪T。其中，dom(F)={x∈P∪T|?y∈P∪T:(x,y)∈F};cod(F)={x∈P∪T|?y∈P∪T:(y,x)∈F}。

此時，dom(F)也表示在定義域中2個相鄰的節(jié)點(diǎn)x與y之間為因果關(guān)系；而cod(F)表示在值域中2個相鄰節(jié)點(diǎn)間用x表示y。

定義2(流程變體[1,2]) 假設(shè)NG是一組流程模型，I表示一組流程更改操作(即刪除、插入、移動)，S0,…,Sn,S′∈NG是一系列的流程模型。設(shè)σ是流程更改操作中的任意一個更改操作，θ?I是一個對初始的流程模型進(jìn)行更改的操作序列，將滿足以下條件的流程模型稱為流程變體：

(1)S0[σ>Sn表示σ作用于S0,且Sn是S0應(yīng)用σ所得到的流程模型；

(2)S[θ>S′表示存在S0,S1,…,Sn∈NG,并且S=S0,S′=Sn,Si[σi>Si+1,i={1,2,…,n-1}，對于這樣的S′，稱為S的流程變體。

定義3(前集與后集、傳遞前集與傳遞后集[14])假設(shè)G為一個流程圖，G中的節(jié)點(diǎn)a是一個二元組(λG(a),τG(a))，其中λG(a)為節(jié)點(diǎn)a的標(biāo)簽，τG(a)為節(jié)點(diǎn)a的類型。在沒有歧義的情況下，可以將下標(biāo)G從(λG(a),τG(a))中刪除。

NG∈G為流程圖中的節(jié)點(diǎn)集合,EG為流程圖的有向邊集合。對于一個節(jié)點(diǎn)a∈NG，將前集定義為·a={m|(m,a)∈G}；類似地，將后集定義為：a·={m|(a,m)∈G}。

定義4(上下文相似性) 假設(shè)G1和G2是2個流程圖，并且M:NG1→/NG2是一個單射。在這一映射規(guī)則下，將G1中的節(jié)點(diǎn)映射到G2中。2個映射節(jié)點(diǎn)a∈NG1和m∈NG2的上下文相似性定義如式(1)所示：

Sim(a,m)=

(1)

定義5(匹配分?jǐn)?shù)) 設(shè)Si和Sj是2個流程變體，M是它們的映射函數(shù)，設(shè)0≤ω1≤1，0≤ω2≤1，0≤ω3≤1是分配給公共節(jié)點(diǎn)、插入或刪除節(jié)點(diǎn)以及插入或刪除邊的權(quán)重值。c1代表公共節(jié)點(diǎn)的集合，c2代表插入或刪除節(jié)點(diǎn)的集合，c3代表公共有向邊的集合，c4代表插入或刪除有向邊的集合,對于cl(l=1,2,3,4)的定義如式(2)～式(5)所示：

c1=dom(M)∪cod(M)

(2)

c2=(NGi+NGj)c1,i≠j

且i=1,2,3;j=1,2,3

(3)

c3={(c,d)∈EGi|(M(c),M(d))∈EGj}∪

{(c′,d′)∈EGj|(M(c′),M(d′))∈EGi}

(4)

c4=(EGi+EGj)c3

(5)

f1表示流程變體中任意公共節(jié)點(diǎn)的距離，f2表示流程變體中插入或刪除節(jié)點(diǎn)的分?jǐn)?shù)，f4表示流程變體中插入或刪除有向邊的分?jǐn)?shù)，fi(i=1,2,4)定義如式(6)～式(8)所示：

(6)

(7)

(8)

則流程變體Si與Sj間的匹配分?jǐn)?shù)定義如式(9)所示：

(9)

3 流程變體間的匹配分?jǐn)?shù)

流程變體之間至少有一個共同的特征、也至少有一個特征相互區(qū)分。模型之間的相似性度量，大多采取因果關(guān)系去衡量，即模型之間的行為輪廓。本文方法是基于流程變體之間的映射關(guān)系，對變體間的共同特征與差異進(jìn)行衡量。為了更好地了解流程變體間的相似程度，本文通過匹配分?jǐn)?shù)來對流程變體進(jìn)行衡量，進(jìn)而得出流程變體間的相似程度。

算法1流程變體間匹配分?jǐn)?shù)

輸入：流程變體Si,Sj。

輸出：匹配分?jǐn)?shù)fS。

步驟1i←1;

步驟2 FORitonDO

步驟3j←i+1;

步驟4publicregions←Map(Si,Sj);

步驟5c1←CountpublicNode(Si,Sj);/*計算變體間公共節(jié)點(diǎn)數(shù)量*/

步驟6VSi←CountNode(Si);

步驟7VSj←CountNode(Sj);

步驟8c2←ComputerInsertedOrDeletedNode(c1,VSi,VSj);/*計算變體間插入或刪除節(jié)點(diǎn)的數(shù)量*/

步驟9c3←CountpublicEage(Si,Sj);/*計算變體間公共有向邊的數(shù)量*/

步驟10ESi←CountEage(Si);

步驟11ESj←CountEage(Sj);

步驟12c4←ComputerInsertedOrDeletedEage(ESi,ESj,c3);/*計算變體間插入或刪除有向邊的數(shù)量*/

步驟13Simi,j←Correlationsimilarity(Si,Sj);/*計算變體間的相似性*/

步驟14f1←Computerdistance(c1,Simi,j);/*計算任意公共節(jié)點(diǎn)距離*/

步驟15f2←ComputerScoreOfInsertedOrDeleted-Node(c1,VSi,VSj);/*計算插入或刪除節(jié)點(diǎn)的分?jǐn)?shù)*/

步驟16f4←ComputerScoreOfInsertedOrDeleted-Eage(c4,ESi,ESj);/*計算插入或刪除有向邊的分?jǐn)?shù)*/

步驟17fSi,jComputerMatchScore(ω1,2,3,f1,2,4);/*計算匹配分?jǐn)?shù)*/

步驟18 ENDFOR

步驟19 RETURNfS

分析流程變體間匹配分?jǐn)?shù)算法，步驟1～步驟3為算法的循環(huán)條件，通過這一循環(huán)得到流程變體間的不同組合。步驟4將變體Si映射到變體Sj上。步驟5～步驟16為計算流程變體間匹配分?jǐn)?shù)的準(zhǔn)備工作，其中步驟5為計算變體Si和變體Sj中共有部分的節(jié)點(diǎn)數(shù)量之和，步驟9與步驟5執(zhí)行一樣的操作，得出公共的有向邊；步驟6～步驟8計算變體Si和變體Sj插入或刪除節(jié)點(diǎn)的數(shù)量，步驟10～步驟12類似；步驟13計算節(jié)點(diǎn)間的上下文相似性，步驟14～步驟16分別計算公共節(jié)點(diǎn)的平均距離、變體Si和變體Sj插入或刪除節(jié)點(diǎn)的分?jǐn)?shù)、變體Si和變體Sj插入或刪除有向邊的分?jǐn)?shù)。步驟17計算變體間的匹配分?jǐn)?shù)。步驟18結(jié)束循環(huán)。步驟19返回匹配分?jǐn)?shù)的值。

算法1中的步驟5利用了式(2)，步驟8利用了式(3)，步驟9利用了式(4)，步驟12利用了式(5)，步驟13利用了式(1)，步驟14利用了式(6)，步驟15利用了式(7)，步驟16利用了式(8)，步驟17利用了式(9)。

如前文所述，匹配分?jǐn)?shù)是用來衡量流程變體間的相似程度。下面通過圖書館借還書籍的業(yè)務(wù)流程圖來對匹配分?jǐn)?shù)進(jìn)行說明，同時，這一業(yè)務(wù)流程圖將作為貫穿全文的案例來使用。圖1 所示即為圖書館借還書籍的業(yè)務(wù)流程圖。

Figure 1 Variants diagram of loaning and returning books process in library

現(xiàn)對圖1中圖書館借還書籍流程變體圖中的變遷做如下說明：A1(讀者刷卡入館)、A2(無目的性的借書)、A3(到借閱區(qū)瀏覽，挑選所需圖書)、A4(自助機(jī)借書)、A5(服務(wù)臺借書)、A6(刷借書證，核對相關(guān)信息)、A7(所在樓層服務(wù)臺辦理借書手續(xù))、A8(借書成功，刷卡出館)、A9(閱讀完畢)、A10(還書前核實)、A11(信息正常)、A12(超期罰款)、A13(還書成功)、A14(指定書籍借閱)、A15(檢索館藏)、A16(書籍在架)、A17(書籍不在架)、A18(預(yù)約指定書籍)、A19(預(yù)約書籍到館)、A20(登錄網(wǎng)上圖書館網(wǎng)址)、A21(網(wǎng)上辦理委托申請)、A22(委托申請辦理中)、A23(取消委托申請)、A24(委托申請成功)、A25(核實地址)、A26(書籍運(yùn)送)、A27(借書成功)、A28(將書寄回)。

匹配分?jǐn)?shù)的數(shù)值越高，則說明2個流程變體間的相似程度越高，即流程變體間共有的共同特征越多。匹配分?jǐn)?shù)0≤fS≤1。若通過算法計算出的匹配分?jǐn)?shù)小于一定的閾值，則對流程變體不進(jìn)行4.1節(jié)的算法2中流程變體的合并操作。此時，從圖書館借還書籍的業(yè)務(wù)流程圖中選擇2個流程變體S2和S3來運(yùn)行算法1，得到這2個流程變體S2和S3的匹配分?jǐn)?shù)fS=0.57。因為流程變體S2和S3的匹配分?jǐn)?shù)為0.57，說明這2個流程變體間的相似程度較高，即所共有的共同特征較多，而從圖1中也不難看出2個流程變體所共有的共同特征有2個部分(即圖1中標(biāo)號為3的框所圈出的部分)?；谒惴?計算這2個流程變體的具體過程在第5節(jié)中給出。

4 流程變體的合并方法

流程變體的合并是在一對可配置的流程圖上(如圖1所示)進(jìn)行的，但是有時也會出現(xiàn)合并2個不可配置的流程圖的情況。為此，文獻(xiàn)[15,16]中提出了一種使用擴(kuò)展的Condec語言對不可配置的流程模型進(jìn)行約束規(guī)范，進(jìn)而將不可配置的流程模型轉(zhuǎn)變成可配置的流程模型的方法，之后再進(jìn)行流程變體的合并。

4.1 算法設(shè)計

算法2流程變體的合并算法

輸入：流程變體S1、S2。

輸出：合并模型MP。

步驟1map(S1,S2)→publicregions∪differentregions;/*將S1,S2映射，劃分公共區(qū)域與差異區(qū)域*/

步驟2P=NULL;//節(jié)點(diǎn)的最大公共區(qū)域為空值

步驟3s=1;

步驟4 WHILEsDO

步驟5IF所有節(jié)點(diǎn)都包含在P中THEN

步驟6s=0;

步驟7ELSETHEN

步驟8Randomchoose(Vm≠Pl);/*隨機(jī)挑選一個節(jié)點(diǎn)*/

步驟9Pl=Searchmaxpublicregion(Vm);/*尋找節(jié)點(diǎn)Vm的最大公共區(qū)域*/

步驟10P.add(Pl);/*將尋找到的最大公共區(qū)域添加到P*/

步驟11s=1;

步驟12ENDIF

步驟13 ENDWHILE

步驟14Addactivity(ST,ET);/*在變體S1和S2中插入開始活動ST與結(jié)束活動ET*/

步驟15Fi=maxpublicregions∪differentregions;//將最大公共區(qū)域與差異區(qū)域拆分為片段

步驟16i=1;

步驟17 WHILEiDO

步驟18matchscorei=computer(Fi);

步驟19IFmatchscorei=1THEN

步驟20Abstractpublicregions(Fi);

步驟21ELSETHEN

步驟22Notabstractpublicregion(Fi);

步驟23ENDIF

步驟24 ENDWHILE

步驟27 ENDFOR

步驟30 ENDFOR

步驟31originalversionMP′←unionpublicregions;

步驟35MP()←MergeRedunancyPlaces(MP″);

步驟36 RETURNMP

分析流程合并算法，步驟1在變體S1與變體S2建立映射關(guān)系，找到變體S1與變體S2相同與差異的一些片段，步驟2～步驟14將變體S1和S2之間的映射劃分為一個僅由匹配節(jié)點(diǎn)和公共的有向邊構(gòu)成的最大公共區(qū)域，其中，s=0,1為判斷是否找到最大公共區(qū)域的條件。步驟15分別對變體S1、S2添加一個開始活動(ST)與結(jié)束活動(ET)。步驟16～步驟25對最大公共區(qū)域進(jìn)行抽象化處理，其中步驟19計算這些片段的匹配分?jǐn)?shù)，步驟20～步驟24為判斷片段可抽象化的條件。步驟25～步驟27對變體S1和S2中的每個有向邊都添加一個注釋。步驟28～步驟30與步驟25～步驟27進(jìn)行的操作類似，只不過是對節(jié)點(diǎn)進(jìn)行操作。步驟31對變體S1和S2中最大公共區(qū)域執(zhí)行并集操作，得到原始版本的合并模型MP′。步驟32將變體S1和S2中替換邊的注釋結(jié)合起來。步驟33對節(jié)點(diǎn)也進(jìn)行類似的操作。步驟34將原始版本的合并模型MP′與變體S1和S2的插入或刪除的節(jié)點(diǎn)進(jìn)行連接，得到合并模型MP″。其連接方式是根據(jù)源和匯在變體S1和S2中的位置。步驟35將合并模型MP″中冗余的庫所合并為一個庫所，以此得到最終的合并模型MP。

定理1(可配置性) 合并模型使用一些配置操作(移動、刪除、插入)導(dǎo)出其中任意一個流程變體。

證明流程變體是由參考模型經(jīng)過一系列的配置操作得到的。本文提出的合并算法旨在將流程變體合并為在一個特定業(yè)務(wù)背景下的單一參考模型。因此，這個單一的參考模型也可以通過配置操作得到任意一個流程變體。

□

定理2(可追溯性) 合并過程模型中的每個節(jié)點(diǎn)都能追溯回其原始模型。

證明合并算法中，對輸入的每個流程變體的節(jié)點(diǎn)與有向邊進(jìn)行了注釋(如在節(jié)點(diǎn)與有向邊中添加了數(shù)字注釋)，確保了在合并后的模型中能更好地追溯來源。

□

定理3(兼容性) 合并模型考慮所有原始模型的行為。

證明因為合并模型是由流程變體經(jīng)由合并算法得來的。利用反證法，假設(shè)合并模型沒有考慮所有原始模型的行為，根據(jù)定理1，合并模型具有可配置性，即合并模型通過移動、刪除、插入等配置操作可以得到任意流程變體。如若假設(shè)成立，則導(dǎo)出的流程變體與合并算法之前的流程變體是不一致的。因此，假設(shè)是不成立的，即合并模型考慮所有原始模型的行為。

□

4.2 基于Petri網(wǎng)的流程變體合并方法的性質(zhì)分析

由于Petri網(wǎng)系統(tǒng)具有安全性、活性等性質(zhì)，本文提出的流程變體合并方法建立在Petri網(wǎng)系統(tǒng)之上。下面對本文提出的基于Petri網(wǎng)的流程變體合并方法的相關(guān)性質(zhì)進(jìn)行分析。

綜上，定理4的(1)得證。(2)和(1)的證明相似，在此不做贅述。

□

5 案例研究

流程變體不同組合間的匹配分?jǐn)?shù)主要分為以下2種情況：組合間匹配分?jǐn)?shù)相同和匹配分?jǐn)?shù)不相同。而本文考慮的是后一種情況，當(dāng)變體數(shù)量龐大時，變體數(shù)量為3個是一個臨界值，如若變體數(shù)量為4個甚至更多，也是通過相同的方法來計算匹配分?jǐn)?shù)，從而挑選出最適配的2個流程變體。因此在本文的研究中選擇3個變體來計算不同變體組合的匹配分?jǐn)?shù)。接下來通過對圖書館借還書籍的流程來進(jìn)一步闡述所提出的方法。以標(biāo)準(zhǔn)借還書籍的流程模型為基礎(chǔ)，通過一系列更改操作(如刪除、插入、置換)來配置流程變體，以此得到3個流程變體，分別為S1(圖1左)、S2(圖1中)和S3(圖1 右)。流程變體S1和S2是線下圖書館借閱書籍的業(yè)務(wù)流程圖，而流程變體S3是線上圖書館借閱書籍的流程圖。對于3個變體來說，其共有的部分為書籍閱讀完畢至還書成功的這一過程；其不同之處就在于，線下圖書館是讀者親自去圖書館挑選所需書籍，而線上圖書館通過客戶端挑選書籍，之后通過郵寄的方式來達(dá)到借書的目的。但是，對變體S1和S2來說，這2個流程變體的共同特征還包括刷卡入館和借書這2個片段；那么，2個流程變體S1和S2中挑選借閱書籍的方式是不同的，流程變體S1是毫無目的性地挑選借閱書籍，流程變體S2是挑選特定的借閱書籍，這種特定的借閱書籍還可能不在架。對于流程變體的具體描述如圖1所示。

之后本文以圖書館借還書籍業(yè)務(wù)流程Si(i=1,2,3)作為算法1和算法2的輸入，驗證本文所提出的流程變體間匹配分?jǐn)?shù)算法和流程變體合并算法。

執(zhí)行算法1中步驟4找到2個變體中的共有部分，用帶標(biāo)號虛線框標(biāo)識出來，對于不同變體間的共有部分用了不同標(biāo)號的虛線框標(biāo)識，如圖2所示；執(zhí)行算法1中步驟5，統(tǒng)計3個流程變體兩兩之間公共節(jié)點(diǎn)的數(shù)量，即圖1中虛線框住的部分就是3個流程變體的公共部分，記為c1；執(zhí)行算法1步驟6～步驟8，計算2個流程變體的總節(jié)點(diǎn)數(shù)，再與公共節(jié)點(diǎn)數(shù)相比較得出變體中插入或刪除節(jié)點(diǎn)的數(shù)量,記為c2。

Figure 2 Abstract fragments F1 and F2

算法1 中的步驟9計算2個變體中公共部分的有向邊的數(shù)量，記為c3；步驟10～步驟12計算變體中插入或刪除有向邊的數(shù)量，記為c4。

算法1 中步驟13計算節(jié)點(diǎn)間的上下文相似性，此時在流程變體間分別選取一個特殊的節(jié)點(diǎn)，由定義5中的式(1)計算得出Sim(a,m)。

算法1中的步驟14計算公共節(jié)點(diǎn)的平均距離、步驟15計算變體Si和變體Sj插入或刪除節(jié)點(diǎn)的分?jǐn)?shù)、步驟16計算變體Si和變體Sj插入或刪除有向邊的分?jǐn)?shù)，對應(yīng)地分別記為f1,f2,f4。

對于流程變體S1和S2、S1和S3以及S2和S3來說，各流程變體之間相關(guān)的數(shù)值詳見表1。

Table 1 Values associated with the matching score between each process variant

執(zhí)行算法1中步驟17，計算變體間的匹配分?jǐn)?shù)，此時將式(9)中的權(quán)重ωi設(shè)置為1，則流程變體Si(i=1,2,3)和之間的匹配分?jǐn)?shù)可由式(9)計算得出，記為fSi,j。

表2中所示為2個流程變體之間的匹配分?jǐn)?shù)。不難看出流程變體S1和S2的匹配分?jǐn)?shù)相對于其他2對的匹配分?jǐn)?shù)要稍微高一點(diǎn)，說明了S1和S2的相似程度略高于其他2對變體。因此，在接下來流程變體的合并算法中，選擇匹配分?jǐn)?shù)稍微高于其他2對的流程變體S1和S2。

Table 2 Matching score fSi,j between process variants

執(zhí)行算法2中步驟1，對變體S1和S2建立一個映射關(guān)系，從而找到流程變體S1和S2中相同與存在差異的一些片段。之后執(zhí)行算法2中的步驟2～步驟14，將變體S1和S2之間的映射劃分為一個僅由匹配節(jié)點(diǎn)和公共的有向邊組成的最大公共區(qū)域。為了找到所有的最大公共區(qū)域，隨機(jī)找一個沒有包含在任何最大公共區(qū)域的匹配節(jié)點(diǎn)，并使用廣度優(yōu)先來搜索該節(jié)點(diǎn)的最大公共區(qū)域，之后使用相同的方法選擇另外的匹配節(jié)點(diǎn)進(jìn)行類似的操作，并以此創(chuàng)建另外一個最大公共區(qū)域。

算法2 中步驟15分別對變體S1、S2添加一個開始活動(ST)與結(jié)束活動(ET)。步驟16～步驟24用Fi標(biāo)記找到的最大公共區(qū)域與差異區(qū)域，之后計算上述2類區(qū)域的匹配分?jǐn)?shù)，將匹配分?jǐn)?shù)計算結(jié)果為1的區(qū)域內(nèi)部行為抽象化，得到了2個抽象化的片段，如圖2所示。并將抽象化片段嵌入到流程變體S1和S2中，簡化了變體S1與S2的結(jié)構(gòu)。執(zhí)行步驟25～步驟30，對有向邊和節(jié)點(diǎn)添加注釋。執(zhí)行完算法2中前30個步驟后得到的流程圖如圖3所示。

Figure 3 Process variants after processing

執(zhí)行算法2中步驟31～步驟34，得到一個合并模型MP″，如圖4所示。合并后的模型應(yīng)當(dāng)滿足這樣的要求：流程圖中的變遷最多有一個輸入庫所或輸出庫所，顯然圖4中的2處變遷不符合提出的要求，因此對合并模型MP″執(zhí)行算法2中的步驟35，將冗余的庫所合并為一個，得到如圖5所示的流程合并模型MP。

Figure 4 Process variants merging model MP″

Figure 5 Process variants merging model MP

流程變體合并模型MP經(jīng)簡化之后，可以使用合并比(fc=|MP|/(|G1|+|G2|))來衡量流程變體的合并情況，即通過節(jié)點(diǎn)的增減情況來衡量流程變體的合并情況。從圖2與圖5中可以分別得出流程變體G1和G2的節(jié)點(diǎn)數(shù)|G1|+|G2|為59,流程變體合并圖MP節(jié)點(diǎn)數(shù)|MP|為17，則合并比為0.29。合并比也從側(cè)面反映了一個事實，即合并比越低，說明2個流程變體合并后所產(chǎn)生的合并圖的效果越好。

6 結(jié)束語

本文以匹配分?jǐn)?shù)作為流程變體相似性的判斷基準(zhǔn)，從備選流程變體中選出一對流程變體作為輸入，輸出是由這2個流程變體合并得到的流程模型。輸出的流程模型具有全面性、可追溯性、可配置性，即保證合并后的模型包含了其輸入的原流程變體，且可以通過對合并后的模型進(jìn)行一些配置推導(dǎo)出原流程變體。此外，本文提出的流程變體合并方法在滿足上述3個性質(zhì)的基礎(chǔ)上，還對變體間的最大公共區(qū)域進(jìn)行了抽象化處理，使得流程變體的規(guī)模在一定程度上得到了縮減。因此，提升了合并模型的可理解性。但是，若作為輸入的多個流程變體具有相同的匹配分?jǐn)?shù)，需要對多個流程變體進(jìn)行合并，最終得到合并模型。而合并的步驟是先將2個流程變體合并，再將得到的模型與第3個流程變體合并，直到所有的流程變體合并完畢。在未來的工作中希望能夠一次性完成多個流程變體的合并，而不需要先將2個流程變體合并 ，再與剩下的流程變體合并，從而大大節(jié)省多個流程變體合并所需要的時間，同時，在多個流程變體的合并過程中也能降低出錯率。