黃 月，朱 銳，李 彤，王基書，湯雅惠 ，呂昌龍

(1.山東大學(xué) 軟件學(xué)院，山東 濟南 250101；2.云南大學(xué) 軟件學(xué)院，云南 昆明 650091；3.云南省軟件工程重點實驗室，云南 昆明 650091；4.云南農(nóng)業(yè)大學(xué) 大數(shù)據(jù)學(xué)院，云南 昆明 650201)

0 引言

伴隨著當(dāng)前全球產(chǎn)業(yè)結(jié)構(gòu)由“工業(yè)型經(jīng)濟”向“服務(wù)型經(jīng)濟”的加速轉(zhuǎn)型，智能制造作為“中國制造2025”的主攻方向，其中涉及到的“柔性制造”和“去中心化”對于過程控制技術(shù)的挑戰(zhàn)更是全方面的。因此，過程驅(qū)動的業(yè)務(wù)過程管理(Business Process Management，BPM)[1]在當(dāng)前生產(chǎn)開發(fā)中的作用日益凸顯。BPM是一套利用過程管理、服務(wù)計算、數(shù)據(jù)挖掘以及工作流等技術(shù)來整合、分析、控制與改進企業(yè)各種業(yè)務(wù)環(huán)節(jié)的全方位管理模式。在實踐中，企業(yè)已經(jīng)針對不同的業(yè)務(wù)場景建立了各種各樣的業(yè)務(wù)過程模型，然而復(fù)雜的業(yè)務(wù)過程模型常面臨著如下問題：

(1)過程模型固有的復(fù)雜性。在過程挖掘領(lǐng)域，過程模型復(fù)雜性長期困擾著相關(guān)從業(yè)人員。特別是在實踐中業(yè)務(wù)過程模型往往會出現(xiàn)模型節(jié)點過多、行為難以分析的問題。例如荷蘭一家信息通信技術(shù)企業(yè)的實施軟件變更管理系統(tǒng)的日志包含案例數(shù)達4萬個，其中事件數(shù)達37萬[2]。面對如此龐大的過程模型，模型往往會呈現(xiàn)出一種“意大利面式”的復(fù)雜結(jié)構(gòu)[3]。

(2)復(fù)雜的業(yè)務(wù)過程模型通常可能包含大量錯誤信息，而這些錯誤信息會對模型分析和控制帶來負面影響。例如死鎖和活鎖[4]，前者會導(dǎo)致模型停止執(zhí)行并停止與環(huán)境的交互，而后者可能會繼續(xù)工作，但模型永遠無法執(zhí)行完畢。因此，對業(yè)務(wù)過程模型進行驗證，發(fā)現(xiàn)其中存在的問題十分必要。

(3)當(dāng)業(yè)務(wù)過程模型十分龐大時，即使不包含復(fù)雜結(jié)構(gòu)，用戶要理解其不同業(yè)務(wù)活動的結(jié)構(gòu)關(guān)系仍然十分困難。因此，對一些龐大的業(yè)務(wù)過程模型進行抽象化，有利于用戶理解總體業(yè)務(wù)過程。當(dāng)一個過程模型中的節(jié)點數(shù)達到數(shù)百乃至數(shù)千時，用戶要理解其圖形結(jié)構(gòu)就已經(jīng)很困難了，更不用說理解其中復(fù)雜的行為語義信息。事實上，用戶很難去理解一個元素數(shù)超過60的過程模型[5]。

在實際的工業(yè)應(yīng)用中，為了克服這些因素，需要通過簡化業(yè)務(wù)過程模型消除模型中的冗余，得到一個關(guān)于復(fù)雜業(yè)務(wù)過程模型的“簡單視圖”，即業(yè)務(wù)過程模型抽象(Business Process Model Abstraction，BPMA)[6]。通過BPMA降低業(yè)務(wù)過程模型的復(fù)雜性，不僅有利于用戶對過程模型的快速理解，更有利于大規(guī)模業(yè)務(wù)過程分析以及提高自動建模質(zhì)量。

為了有效地提高此類復(fù)雜業(yè)務(wù)過程模型的可理解性，本文提出一種基于完全前綴展開的業(yè)務(wù)過程模型結(jié)構(gòu)化簡算法，該算法利用完全前綴展開技術(shù)分析業(yè)務(wù)過程模型中的行為，使用過程樹簡潔直觀地表示模型行為，再根據(jù)過程樹中的行為和語義重構(gòu)業(yè)務(wù)模型。最后通過實驗表明，該算法不但具有正確性和可行性，并且有效降低了業(yè)務(wù)過程模型的復(fù)雜度。

1 問題背景

對業(yè)務(wù)過程而言，常用的形式化建模工具主要有工作流[7]、進程代數(shù)[8]、自動機[9]、Petri網(wǎng)等。其中，Petri網(wǎng)[5]具有精確的數(shù)學(xué)形式定義，能夠描述真發(fā)[10]，并且具有圖形化描述以及嚴格的執(zhí)行語義[11]，是當(dāng)前以圖形方式描述并發(fā)性的最常用形式化工具。因此，本文研究將采用Petri網(wǎng)作為業(yè)務(wù)過程模型的描述工具。

目前，實踐中業(yè)務(wù)過程模型卻呈現(xiàn)海量特征、模型節(jié)點過多、行為難以分析等問題。針對此類規(guī)模龐大且結(jié)構(gòu)復(fù)雜的業(yè)務(wù)過程模型，如何有效地提高其可理解性是亟待解決的問題。當(dāng)前針對該問題的解決方法主要有模型頻繁行為模式發(fā)現(xiàn)[12-14]和精簡模型結(jié)構(gòu)[15-19]等。

其中，模型頻繁行為模式發(fā)現(xiàn)的核心思想是保留日志中具有代表性的關(guān)鍵路徑，除去一些噪聲和非頻繁日志帶來的低頻次行為依賴，從而簡化了模型的規(guī)模。這種方法能夠有效地保留模型中發(fā)生次數(shù)較多的行為，但也可能去掉非頻繁的關(guān)鍵行為。文獻[20]根據(jù)故障和修復(fù)過程理論分析了位置之間的相互作用和過渡點火率函數(shù)，并簡化了隨機Petri網(wǎng)，該方法不適用于復(fù)雜模型的簡化，因為它需要研究每個位置與模型其余部分的相互作用。

精簡模型結(jié)構(gòu)主要強調(diào)從細粒度的過程模型中發(fā)現(xiàn)高層次的粗粒度的模型結(jié)構(gòu)，常用的技術(shù)包括模型優(yōu)化[15-17]、模型整合[18]、日志聚類[19]等。精簡模型結(jié)構(gòu)方面，文獻[21]提出一種結(jié)構(gòu)化的過程，并簡化了該過程中對稱系統(tǒng)的行為，但是該簡化方法僅適用于對稱系統(tǒng)的行為。文獻[22]提出一種向弧添加時間屬性的延遲，從而簡化了過程，同時保留了調(diào)度和死鎖屬性。文獻[23]提出了4種性能等效公式來簡化通用模型結(jié)構(gòu)的過程。文獻[24-25]中利用搜索樹和模型的行為輪廓得到變遷關(guān)聯(lián)搜索樹，從而實現(xiàn)模型的抽象化簡。

無論是頻繁行為模式發(fā)現(xiàn)，還是對模型結(jié)構(gòu)進行精簡，在一定程度上都會對模型的行為造成損失。這就使得一些對模型質(zhì)量要求較高的領(lǐng)域，無法容忍模型行為損失的關(guān)鍵過程，例如軟件開發(fā)版本的重要分支過程、交通事故的保險理賠過程等，這些分支過程雖然在整個業(yè)務(wù)過程中極少出現(xiàn)，但尤為重要[26]，而當(dāng)前的模型化簡算法，無法在保持行為的同時提高此類復(fù)雜業(yè)務(wù)過程模型的可理解性。

針對上述問題，本文將聚焦在保持行為的條件下如何化簡業(yè)務(wù)過程模型。換而言之，即在除去業(yè)務(wù)過程模型的復(fù)雜結(jié)構(gòu)的同時保留模型行為。以此來降低“意大利面式”復(fù)雜結(jié)構(gòu)所引起的模型不易理解問題。如圖1所示為在保持行為的條件下化簡具有復(fù)雜結(jié)構(gòu)的業(yè)務(wù)過程模型的案例，仔細分析可以看出，化簡前后模型中活動的行為未改變，但是模型結(jié)構(gòu)的復(fù)雜度被大幅降低了。

為了在保持模型行為的同時化簡模型的復(fù)雜結(jié)構(gòu)，本文采用過程樹[27-28]對模型行為進行抽象。過程樹是一種包含了過程模型信息的樹形結(jié)構(gòu)圖，過程樹不僅有對應(yīng)的健全模型表示，還支持基本的控制流模式[29]。過程樹中任意兩個活動(葉子節(jié)點)的關(guān)系即它們最近的公共父親節(jié)點。圖1中的業(yè)務(wù)過程模型所對應(yīng)的行為等價過程樹為∝(→(→(×(A,B),×(C,D)),→(×(E,F),G)),→(∝(H,→(K,J)),I))。

盡管圖1中的業(yè)務(wù)過程模型存在對應(yīng)的行為等價過程樹，但是當(dāng)前對于過程樹轉(zhuǎn)化的算法只能針對基于塊結(jié)構(gòu)的過程模型[31-33](Block-Structured Process Model，BSPM)，具體見定義2,與過程樹的行為等價的過程模型[30](process Tree in behavior Equivalent’s Process Model，TEPM)，具體見定義4,是可以轉(zhuǎn)化為行為等價過程樹的模型。TEPM與BSPM的關(guān)系如圖2 所示。因此，本文提出一種可以判斷TEPM行為的算法，從而在不損失行為的情況下化簡業(yè)務(wù)過程模型。綜合上述內(nèi)容，本文的研究內(nèi)容及貢獻主要集中在以下方面：

(1)本文提出一種行為判斷方法，該方法不僅可以支持基于基本塊的過程模型BSPM中簡單的活動關(guān)系判斷，還可以判斷具有復(fù)雜結(jié)構(gòu)的過程模型活動關(guān)系(例如圖1)。其次定義相應(yīng)的可合并的關(guān)系判斷條件，可以選出抽象后不影響活動的行為進行合并。通過不斷循環(huán)這些操作，最終抽象出模型中的TEPM結(jié)構(gòu)。

(2)本文提出一種基于完全前綴展開的業(yè)務(wù)過程模型結(jié)構(gòu)化簡與行為保持的算法，該算法通過活動關(guān)系構(gòu)造過程樹，根據(jù)過程樹與過程模型之間的映射，對模型結(jié)構(gòu)進行化簡。

(3)該算法考慮了業(yè)務(wù)過程模型的復(fù)雜結(jié)構(gòu)的化簡問題，能真正應(yīng)用到業(yè)務(wù)過程模型的化簡之中，具有一定實用性。在保持模型行為的同時消除多余的模型結(jié)構(gòu)，利于增加模型設(shè)計的彈性，提高業(yè)務(wù)過程的執(zhí)行效率。

2 預(yù)備知識

2.1 過程模型和過程樹

定義1業(yè)務(wù)過程模型。業(yè)務(wù)過程模型p是一個四元組，p=(C,A;F,M0)，其中：C是條件的有窮集合，A是活動的有窮集合；F?C×A∪A×C，F(xiàn)是p上的流關(guān)系；M0?C，M0作為p的初始情態(tài)。

本文使用Petri網(wǎng)系統(tǒng)來表示業(yè)務(wù)過程模型，Petri網(wǎng)的其他相關(guān)概念請參閱文獻[34-35]。

定義2基于塊結(jié)構(gòu)的過程模型BSPM[31-33]。設(shè)s為一個過程片段，s可以使用基本塊和有限次地活動重構(gòu)(具體請參閱文獻[31-33])操作得到s，則將該過程片段s稱為BSPM?；緣K具體如圖3所示，其中黑色的活動表示內(nèi)部活動，它不會產(chǎn)生其他任何外部行為。

定義3復(fù)雜結(jié)構(gòu)。設(shè)s為一個過程片段，無法使用基本塊和有限次地活動重構(gòu)(具體請參閱文獻[28-30])操作得到s，則將該過程片段s稱為復(fù)雜結(jié)構(gòu)。

定義4過程模型的行為空間[30]。設(shè)p=(C,A;F,M0)是一個過程模型，設(shè)σ?A*為過程模型p上的一個變遷序列，則p上所有可能發(fā)生的變遷序列的集合稱為p行為空間，記為(p)，則σ∈(p)。

定義5與過程樹行為等價的過程模型TEPM[30]。一個四元組p=(C,A;F,M0)被稱作一個TEPM，當(dāng)且僅當(dāng)存在一個過程樹模型t，使得p與t之間滿足：①不存在σ使得σ∈(p)∧σ(t)；②不存在σ使得σ∈(t)∧σ(p)。

其中:σ表示過程模型p或者過程樹t的一個變遷序列;p和t行為等價，即過程模型p中所有出現(xiàn)的變遷序列一定會在過程樹t中出現(xiàn)，反之亦然。TEPM包含所有BSPM模型和一部分具有復(fù)雜結(jié)構(gòu)的模型，這兩部分模型都有對應(yīng)的行為等價過程樹，換而言之，有對應(yīng)行為等價過程樹的過程模型就是TEPM。

定義6過程樹[27]。對于一個過程模型p=(C,A;F,M0)，A為其活動集，則活動a∈A為一個過程樹；設(shè)M1,M2,…Mn(n>0)為n個過程樹，過程樹間關(guān)系符號記為◎，則◎(M1,M2,…Mn)為過程樹。

本文中使用順序(→)，選擇(×)，并發(fā)(||)，迭代(∝)共4種關(guān)系符號，不同結(jié)構(gòu)對應(yīng)的結(jié)構(gòu)如圖3所示，使用符號◎表示括號內(nèi)的活動關(guān)系。

2.2 完全前綴展開

為分析對業(yè)務(wù)過程模型的行為，本文采用了ESPARZA[36]提出完全前綴展開的方法，該方法與傳統(tǒng)的可達樹或者可達圖不同。完全前綴展開可以將過程模型展開為一個包含截斷事件的分支進程，從而避免可達樹或者可達圖中面臨的狀態(tài)空間爆炸問題。下面對該技術(shù)中一些基本概念進行說明，更多相關(guān)介紹詳見文獻[36]。

定義8分支進程。對于一個過程模型p=(C,A;F,M0)，其分支進程是一個二元組Π=(o,h)，其中o=(S,T;F′)是一個出現(xiàn)網(wǎng)，h是一個從(S,T;F′)到(C,A;F)的映射，其中：①h(P)?C，h(T)?A，h(F′)?F；②Min(o)與M0是雙射關(guān)系，Min(o)表示出現(xiàn)網(wǎng)o中根據(jù)適當(dāng)偏序關(guān)系得到的最小元素集合；③?t1,t2∈T，且t1,t2滿足·t1=·t2∧h(t1)=h(t2)，則t1=t2。

定義10適當(dāng)偏序關(guān)系。一個出現(xiàn)網(wǎng)o=(P,T;G)的適當(dāng)偏序關(guān)系是本地配置之間的關(guān)系，用<·表示適當(dāng)偏序關(guān)系，其中：①<·是對?的改進，即?t,t′∈T有[t]?[t′]，則[t]<·[t′]；②<·通過有限擴展得到保留，即?t,t′∈T有[t]<·[t′]和Mark(t)=Mark(t′)，則對于[t]的有窮擴展[t]?E，存在同構(gòu)變換I，使[t]?E<·[t′]?I(E)。

定義11割集。一個出現(xiàn)網(wǎng)o=(P,T;G)的有限配置C，其割集Cut(C)，是一組只包含co關(guān)系的條件集，Cut(C)被定義為Cut(C)=(Min(N)∪C·)·C。

定義12截斷事件。Π=(o,h)是過程模型p=(C,A;F,M0)的一個分支進程，如果Π中的兩個事件e′和e滿足：①h(Cut([e]))=h(Cut([e′]))，即通過e到達的情態(tài)與e′的相等；②[e′]<·[e]，本地配置[e′]和本地配置[e]是適當(dāng)偏序關(guān)系。將e稱為截斷事件、e′稱為e的對應(yīng)事件，可記為corr(e)=e′：

完全前綴展開的方法通過不斷計算分支進程的可能擴展集擴展模型的分支進程，并在遭遇截斷事件時停止擴展分支進程，從而回避了狀態(tài)空間爆炸問題。圖4是一個完全前綴展開的案例，該案例是針對圖4中復(fù)雜模型P的展開，其中模型P′是模型P的一個包含截斷事件的分支進程。其中[A]={A}，[F]={A,C,F}，[G]={A,C,E,G}。因為[J]= {A,C,E,G,H,K,J}、[G]<·[J]以及Mark([G])=Mark([J])，因此事件J是一個截斷事件，條件6′是一個截斷條件，存在corr(J)=G。

3 業(yè)務(wù)過程模型的化簡

本章首先對基于完全前綴展開的業(yè)務(wù)過程模型結(jié)構(gòu)化簡與行為保持的總體流程進行介紹；然后詳細闡述總體流程中的模型抽象部分，該部分在不影響其他行為的基礎(chǔ)上逐一抽象模型行為；最后闡述分解模型的方法，從而化簡復(fù)雜結(jié)構(gòu)。

3.1 總體流程

基于完全前綴展開的業(yè)務(wù)過程模型結(jié)構(gòu)化簡與行為保持主要步驟可分為兩部分，具體流程圖如圖5所示。①抽象模型。通過完全前綴展開，得到一個包含截斷事件的分支進程，從而判斷每2個活動之間的關(guān)系，出現(xiàn)可合并的活動關(guān)系時，依次重構(gòu)不會影響其他行為的活動關(guān)系。不斷迭代上述操作，直到模型中不存在合并后不影響其他行為的活動關(guān)系。②分解模型。通過遍歷模型中的過程樹逐個將其分解開來，最終輸出化簡后的業(yè)務(wù)過程模型。

3.2 抽象模型

本文的目標(biāo)是簡化業(yè)務(wù)過程模型。抽象模型算法的偽代碼如算法1所示，其重點在于如何判斷活動之間的關(guān)系，然后根據(jù)判斷結(jié)果構(gòu)造不同的過程樹，然后更新模型。該算法主要分為四步：

(1)完全有限前綴展開。將輸入的模型展開，從中獲取相關(guān)信息用于后續(xù)操作。

(2)抽取可合并的活動關(guān)系。判斷展開網(wǎng)中每一組事件之間是否存在可合并的關(guān)系，存在某種關(guān)系時，將其保存到對應(yīng)的活動關(guān)系矩陣中。

(3)判斷是否存在可重構(gòu)的活動關(guān)系。去掉相互沖突的活動關(guān)系，獲得一個無沖突的活動關(guān)系集合。若活動關(guān)系集合為空，輸出過程模型；若活動關(guān)系集合不為空，則進入第(4)步。

(4)活動關(guān)系重構(gòu)。通過依次合并活動關(guān)系集合中的活動關(guān)系更新模型，然后轉(zhuǎn)第(1)步。

通過連續(xù)循環(huán)這些操作，最終將所有TEPM結(jié)構(gòu)轉(zhuǎn)換為過程樹，輸出一個包含過程樹的過程模型。算法1的第4行、第5行、第8行分別對應(yīng)第(2)、第(3)和第(4)步。

算法1抽象模型算法。

輸入：過程模型p=(C,A;F,M0)；

輸出：抽象后的過程模型p=(C,A;F,M0)。

MergeOfProcess(p)

1. flag = true

2. while flag:

3. flag = false

4. RM = IdentifiesRelation(p) //獲取行為矩陣RM，具體見4.2.1節(jié)算法2

5. RL = getRelationList(RM) //獲取活動關(guān)系集合RL，具體見4.2.2節(jié)算法3

6. for each ◎(a1, a2)∈ RL then

7. if ◎(a1, a2)? p.A then

8. p = refactoringOfProcess(p, ◎(a1, a2))

//合并活動關(guān)系，具體見4.2.3節(jié)算法4

9. flag = true

10.return p

在最理想的情況下(模型中結(jié)構(gòu)都屬于TEPM)，算法1可將業(yè)務(wù)過程模型轉(zhuǎn)化為一個完整的過程樹。

一個合理的業(yè)務(wù)過程Petri網(wǎng)模型，通常具有恰當(dāng)終止性(proper termination)、活性(liveness)、無死鎖性(deadlock free)[37]等性質(zhì)。為此，下面對本文提出的算法的相關(guān)性質(zhì)進行分析。

定理1設(shè)過程模型p存在相應(yīng)的行為等價過程樹t，則p必然具有：①恰當(dāng)終止性；②活性；③無死鎖性。

證明①恰當(dāng)終止性包含兩方面：恰當(dāng)終止的和無死事件。

設(shè)過程模型為p相應(yīng)的行為等價過程樹為t。過程樹中的葉子節(jié)點代表活動，分支節(jié)點代表活動關(guān)系。因此，使用遞歸的方法，可以逐步遍歷過程樹的節(jié)點，將其在p中對應(yīng)的活動合并，最終p中的活動被合并為一個活動a。p中只會保留活動a、a的入度和a的出度。p必存在源節(jié)點a的入度、終止節(jié)點a的出度。因此模型p是恰當(dāng)終止的。

根據(jù)過程模型與行為等價過程樹之間的關(guān)聯(lián)，可知過程模型中每一個活動都能對應(yīng)過程樹中的一個葉子節(jié)點。過程樹中任意兩個葉子節(jié)點的最近公共父節(jié)點代表這兩個葉子節(jié)點之間的行為關(guān)系。由此可知過程模型中任意兩個活動必存在某種行為關(guān)系，它們之間是可達的，因此模型p中無死事件。

②和③的證明與①類似，不再贅述。

3.2.1 判定活動關(guān)系

本節(jié)詳細介紹根據(jù)展開網(wǎng)抽取模型行為的方法。首先通過完全前綴展開技術(shù)可以將過程模型展開為一個包含截斷事件的分支進程，從分支進程中可以便利地獲取一些相關(guān)信息，具體需要的信息如表1所示。其中包括CM和oRM兩個二維數(shù)組以及corr和h兩個一維數(shù)組，二維數(shù)組CM表示展開網(wǎng)中的事件間的配置關(guān)系，例如表1中CM[F][C]=√表示事件F的配置包含C；oRM表示展開網(wǎng)中事件間的關(guān)系；符號“<”、“#”和“co”的含義可參見定義7，符號“>”表示逆因果關(guān)系，即aa；數(shù)組corr和h分別表示展開網(wǎng)中事件間的截斷關(guān)系和展開網(wǎng)中的事件到原模型中的映射關(guān)系。通過上述信息可確定業(yè)務(wù)過程模型中的活動關(guān)系。

表1 圖4中完全前綴展開案例的信息

本文使用了順序(→)，選擇(×)，并發(fā)(||)，迭代(∝)4種關(guān)系來描述模型行為。為了構(gòu)建一棵完整的行為等價過程樹，需要先構(gòu)建底層的子樹。因此本文抽取出的活動關(guān)系需滿足兩個條件：①該活動關(guān)系屬于4種關(guān)系中的一種；②所對應(yīng)的兩個活動合并后不改變其他任何行為的活動關(guān)系。下面給出4種關(guān)系的判斷方法，這4種判斷方法可以判斷出任意一組活動間是否存在直接關(guān)系，即不需要通過其他活動，就可直接發(fā)生的行為，例如圖1中的K和J間的順序關(guān)系是在不涉及其活動時就可以發(fā)生，屬于直接關(guān)系；H和J間的迭代關(guān)系是需要通過K才能發(fā)生，不屬于直接關(guān)系。

對于過程模型p=(C,A;F,M0)，Π=(o,h)為過程模型p對應(yīng)的一個包含截斷事件的分支進程，其中，o=(S,T;F′)是一個出現(xiàn)網(wǎng)，h是一個映射函數(shù)，?t1,t2∈T, ?a1,a2∈A,h(t1)=a1,h(t2)=a2。

定義13順序關(guān)系判斷條件。當(dāng)t1,t2滿足下述條件時，a1與a2存在順序關(guān)系，a1先發(fā)生，記為→(a1,a2)。

(1)oRM[t1][t2]= <，即t1與t2之間存在因果關(guān)系。

(2)對于所有t∈T且t≠t1∧t≠t2，①存在CM[t1][t]=CM[t2][t]∧CM[t][t1]=CM[t][t2]；②存在h(t)=h(t2)時，必有h(··t)=h(t1)；③存在corr(t)=t1時，必有h(t)=h(t1)∧oRM[t][t2]=<，以及對于任意t′∈T且t′≠t∧t′≠t2有CM[t][t′]=CM[t2][t′]。

定義14迭代關(guān)系判斷條件。當(dāng)t1,t2滿足下述條件時，a1與a2存在迭代關(guān)系，其中a1先發(fā)生，記為∝(a1,a2)，a2先發(fā)生，記為∝(a2,a1)。

(1)oRM[corr(t2)][t1]= <∧oRM[t1][t2]= <，即存在corr(t2)，并且corr(t2)與t1、t1與t2之間存在因果關(guān)系。

(2)對于所有t∈T且t≠t1∧t≠t2，存在CM[t1][t]=CM[t2][t]。

(3)對于所有t∈T且t≠t1∧t≠corr(t2)，存在CM[t1][t]=CM[corr(t2)][t]。

(4)若h(t2)≠h(corr(t2))，則a1與a2存在可合并的迭代關(guān)系，且a1先發(fā)生；否則，a2與a1存在可合并的迭代關(guān)系，且a2先發(fā)生。

定義15選擇關(guān)系判斷條件。當(dāng)t1,t2滿足下述條件時，a1與a2存在選擇關(guān)系，記為×(a1,a2)或×(a2,a1)。

(1)oRM[t1][t2]= #，即t1與t2之間存在沖突關(guān)系。

(2)corr(t1)=t2或corr(t2)=t1，即t1或t2是一個截斷事件且對應(yīng)事件是對方。

(3)對于所有t∈T且t≠t1∧t≠t2，存在CM[t1][t]=CM[t2][t]。

定義16并發(fā)關(guān)系判斷條件。當(dāng)t1,t2滿足下述條件時，a1與a2存在并發(fā)關(guān)系，記為||(a1,a2)或||(a2,a1)。

(1)oRM[t1][t2]= co，即t1與t2之間存在co關(guān)系。

(2)corr(t1)=null∧corr(t2)=null，即t1和t2都不是截斷事件。

(3)對于所有t∈T且t≠t1∧t≠t2，①存在CM[t1][t]=CM[t2][t]∧CM[t][t1]=CM[t][t2]；②當(dāng)存在hList[t]=hList[t1]時，必有CM[t2][t]==true；③當(dāng)存在hList[t]=hList[t2]時，必有CM[t1][t]==true。

任意兩個事件只要滿足定義13～定義16中的(1)就可以確定相應(yīng)的活動之間存在關(guān)系，但這兩個事件若不能滿足其他幾點，則對應(yīng)的兩個活動合并后必定會對其他活動關(guān)系產(chǎn)生影響。

通過表1中的信息以及上述4種關(guān)系判斷方法，可以從圖1中抽取出×(A,B)、×(C,D)、×(E,F)和→(K,J)4個關(guān)系。利用上述的4種關(guān)系判斷方法，下面本文給出生成行為矩陣算法IdentifiesRelation的偽代碼。

算法2生成行為矩陣算法。

輸入：包含過程樹的過程模型p=(C, A; F, M0)；

輸出：行為矩陣RM。

IdentifiesRelation(p)

1. get an branching processes Π =(o, h)with p //展開過模型程 p

3. T = o.T, get corr、h、oRM、CM form Π =(o, h)、RM=[len(p.A)][len(p.A)]

4. foreach(t1: T)

5. foreach(t2: T)

6. if t1!= t2then

7. if isSequnence(t1, t2)then RM[h(t1)][h(t2)].add(→) //判斷方法參考定義13

8. if isIteration(t1, t2)then RM[h(t1)][h(t2)].add(∝) //判斷方法參考定義14

9. if isChoice(t1, t2)then RM[h(t1)][h(t2)].add(×) //判斷方法參考定義15

10. if isConcurrency(t1, t2)then RM[h(t1)][h(t2)].add(||) //判斷方法參考定義16

11.return RM

3.2.2 選擇可合并的活動關(guān)系

接下來需要選擇可合并的活動關(guān)系，這些可合并的活動關(guān)系需要滿足在重構(gòu)后不會對其他活動關(guān)系造成影響。上文中抽取出的活動關(guān)系是直接關(guān)系，因此只需要考慮有相同活動的關(guān)系是否沖突。

定義17可合并的關(guān)系判斷條件。當(dāng)◎(a1,a2)滿足下述條件時，a1與a2之間的關(guān)系是可合并的。對與任意◎′(a1′,a2′)∈RM且{a1,a2}∩{a1′,a2′}≠?有：①◎只表示一種關(guān)系；②◎=→時◎′=→；③◎=×?xí)r◎′=×或◎′=||；④◎=||時◎′=||；⑤◎=∝時◎′≠∝或a1′≠a2∧a1≠a2′。

迭代關(guān)系合并后會使不同方向的流關(guān)系合并到一處，容易影響其他活動關(guān)系，因此存在其他可合并的關(guān)系時不合并迭代關(guān)系。下面給出選擇合并的活動關(guān)系算法getRelationList。

算法3選擇合并的活動關(guān)系算法。

輸入：行為矩陣RM；

輸出：活動關(guān)系算集合RL。

getRelationList(RM)

1. tRL= {} lRL= {} RL= {}

2. for each ◎(ai, aj)∈ RM then //獲取非空活動關(guān)系

3. if(◎ != ?)tRL.add(◎(ai, aj))

4. foreach(◎(a1, a2): tRL)

5. falg= len(◎)==1 //判斷活動是否滿足定義17中的①

6. foreach(◎′(a′1, a′2): tRL) //判斷活動是否滿足定義17中的②③④⑤

7. if falg and {a1, a2}∩{a′1, a′2}≠? then

8. if ◎==→ and ◎′!= → then flag = false, break

9. else if ◎==× and(◎′==→ or ◎′==∝)then flag = false, break

10. else if ◎==∝ and(◎′!= ∝ or a1′== a2or a1==a2′)then flag = false, break

11. else if ◎==||and(◎′!=||)then flag = false, break

12. if falg then //分別存儲迭代關(guān)系和其他關(guān)系

13. if ◎ == ∝then lRL.add(◎(a1, a2))

14. else then RL.add(◎(a1, a2))

15.if lRL.size > 0 then return RL //判斷是否需要優(yōu)先選擇迭代關(guān)系以外的其他關(guān)系

16.return RL

3.2.3 合并活動關(guān)系

合并活動關(guān)系的基本思想如圖6所示，即刪除原有的兩個活動，增加新活動，并有選擇地令新活動繼承原活動的一部分流關(guān)系。保留那些流關(guān)系，根據(jù)活動關(guān)系可以分為兩種：①活動關(guān)系不屬于迭代關(guān)系，此時在排除需要刪除的條件后，令新活動同時繼承原有的兩個活動的流關(guān)系；②活動關(guān)系屬于迭代關(guān)系，令新活動繼承原活動中先發(fā)生的活動的流關(guān)系，但是有時先發(fā)生的活動的后繼屬于需要刪除的條件，此時令新活動繼承后發(fā)生的活動與其后繼之間的流關(guān)系。

其次還需要刪除一部分條件及其相關(guān)的流關(guān)系，需要刪除的條件可分為3種情況：①不屬于初始情態(tài)，僅僅連接了原有的兩個活動，作為這兩活動的過渡；②不和其他活動產(chǎn)生聯(lián)系的，即出度和入度都為0；③具有相同的情態(tài)、前集和后繼[38]的兩個條件，刪除其中一個。這3種情況中第①種容易影響流關(guān)系的選擇，需在選擇流關(guān)系前確定。后兩種情況受流關(guān)系的影響，在最后確定。

算法4是合并活動關(guān)系算法refactoringOfProcess，其中流關(guān)系的選擇對應(yīng)第5～8行。刪除條件的3種情況分別對應(yīng)第2行、第10行和第11-15行。

算法4合并活動關(guān)系。

輸入：過程模型p=(C, A; F, M0), 需要合并的活動關(guān)系◎(a1, a2)；

輸出：過程模型p′=(C, A; F, M0)。

refactoringOfProcess(p, ◎(a1, a2))

1. newa = ◎(a1, a2), delA = {a1, a2} //新建新的活動、選擇需要刪除的活動

3. delF = { e1×e2|e1×e2∈p.F and {e1, e2}∩(delA∪delC)≠?} //選擇需刪除的流關(guān)系

4. p′=(p.C-delC, p.A + newa-delA; F-delF, p.M0) //根據(jù)之前的選擇更新模型

5. if ◎ ==∝ then //根據(jù)關(guān)系類型，增加新的流關(guān)系

6. p′.F += {newa×c|c∈((a1·?delCa2·: a1·)-delC)}∪{c×newa|c∈(·a1-delC)}

7. else then

8. p′.F += {newa×c|c∈((a1·+a2·)-(·a1+·a2)-delC)}∪{c×newa|c∈((·a1+·a2)-(a1·+a2·)-delC)}

9. newC = p′.C

10.for(i = newC; i >= 0; i--) //遍歷模型中的條件

11. if(·newC[i]==?∧newC[i]·==?)then p′.C-= newC[i],continue//newC[i]出入度為0時刪除

12. for(j = i-1; j >= 0; j--)//存在newC[j]且與newC[i]有相同的情態(tài)、前集和后繼時，刪除newC[i]

13. if(newC[i]∈M0∧newC[j]∈M0∧·newC[i]==·newC[j]∧newC[i]·== newC[j]·)

14. p′.F-= { e1×e2|e1×e2∈p.F and {e1, e2}∩(newC[i])≠?}

15. if newC[i]∈ M0then p′.M0-= newC[i]

16. p′.C-= newC[i], break

17.return p′

3.3 分解模型

抽象模型通過遍歷模型中所有的過程樹，然后根據(jù)根節(jié)點(代表孩子節(jié)點的行為)，將其對應(yīng)的孩子拆開作為不同活動，并重新構(gòu)造不同活動之間的結(jié)構(gòu)。

分解過程模型算法的基本思想的示意圖如圖7所示。即在將原活動a刪除后，增加新的活動a1和a2，同時原本與a相關(guān)的流關(guān)系也會被修改保留，其次還會根據(jù)結(jié)構(gòu)不同新增一些流關(guān)系和條件。

圖7中紅色和藍色的表示原有的流關(guān)系，在模型被分解后所對應(yīng)的位置，其中除了順序結(jié)構(gòu)中由a1和a2分別繼承原本的出入流關(guān)系，其他結(jié)構(gòu)中原有的流關(guān)系都是由a1繼承。圖7中綠色部分表示新增的流關(guān)系和條件，選擇結(jié)構(gòu)和迭代結(jié)構(gòu)類似只需要新增的流關(guān)系，區(qū)別在于流關(guān)系的方向不同。順序結(jié)構(gòu)需要新增一個條件，并且還需要增加與a1和a2的新流關(guān)系。并發(fā)結(jié)構(gòu)比較特別，需要新增兩個條件，這兩個條件分別作為a2的前驅(qū)和后繼，同時還要復(fù)制對應(yīng)于a1的前驅(qū)和后繼的原有的流關(guān)系。

對過程模型進行分解時，順序結(jié)構(gòu)和并發(fā)結(jié)構(gòu)都需要新增條件，此時根據(jù)流關(guān)系從抽象前的模型中選擇相應(yīng)的條件作為新增條件。設(shè)抽象前模型為p=(C,A;F,M0)、當(dāng)前模型newp，將a中包含的活動加入A得到A′，則順序結(jié)構(gòu)的新增條件c滿足{c|c∈p.Cand·c?A′∧c·?A′}，則并發(fā)結(jié)構(gòu)新增的前驅(qū)條件c1滿足 {c|c∈·A′-newp.A}，新增的后繼條件c2滿足 {c|c∈A′·-newp.A}。

不斷重復(fù)分解操作，直到模型中不再包含過程樹。最后輸出的模型便是一個在保持行為的情況下結(jié)構(gòu)被化簡的過程模型。具體偽代碼如算法5所示。

算法5分解過程模型算法。

輸入：抽象后的過程模型p=(C, A; F, M0)，原過程模型p′=(C, A; F, M0)；

輸出：過程模型newp=(C, A; F, M0)。

RefinePetriNet(p, p′)

1. flag = true, newC = C, newA = A, newF= F, newM0= M0

2. while flag:

3. flag = false //判斷模型是否還存在可分解的過程樹

4. foreach(a: newA) //遍歷模型中的活動

5. if a is process tree and a == ◎(a1,a2)then //該活動是否可分解

6. flag = true, newA +={a1, a2} //增加新活動

7. //根據(jù)行為增加流關(guān)系、條件，具體如圖7所示

8. get a condition set nC according to ◎, and newC += nC

9. get a flow relationship set nF according to ◎, and newF += nF

10. newF-= { e1×e2|e1×e2∈ newF and {e1, e2}∩{a}=?} //刪除與原活動相關(guān)的流關(guān)系

11. newA-= {a} //刪除原活動

12.return newp =(newC, newA; newF, newM0)

將算法1和算法5結(jié)合起來,就可以化簡具有復(fù)雜結(jié)構(gòu)的業(yè)務(wù)過程模型。

4 案例測試與實驗分析

為分析模型的化簡程度和效率，本章對基于完全前綴展開的業(yè)務(wù)過程模型結(jié)構(gòu)化簡與行為保持的方法進行了實驗分析。在本章中，首先分析一個詳細的業(yè)務(wù)過程模型化簡案例來驗證該方法。其次，通過具有一定規(guī)模的實驗數(shù)據(jù)測試了方法的效率。最后通過對比實驗，證明本文方法對TEPM模型結(jié)構(gòu)的化簡具有優(yōu)勢。本章所有實驗均在Intel(R)Core(TM)i5-6200U CPU @ 2.30 GHz 2.40 GHz且具有8 G RAM的 PC平臺上完成。

4.1 案例分析

4.1.1 案例描述

首先給出一個業(yè)務(wù)過程模型案例，如圖8所示。該業(yè)務(wù)過程是一個治療流程，模型中包含的活動和執(zhí)行條件具體有：感到不適的患者(a1)、擔(dān)架(a2)、候診室(a3)、經(jīng)評估的救護車患者(a4)、護士(a5)、經(jīng)評估的患者(a6)、等待治療的患者(a7)、接受手術(shù)治療的病人(a8)、醫(yī)生(a9)、接受治療的患者(a10)、恢復(fù)健康的患者(a11)；救護車到達(A)、預(yù)約到達(B)、急診護士評估(C)、護士評估(D)、進行急診化驗(E)、完成急診評估(F)、完成評估(G)、化驗(H)、小手術(shù)(I)、大手術(shù)(J)、醫(yī)生診斷(K)、醫(yī)生集體診斷(L)、康復(fù)(M)、出院(N)。

圖8中所示的治療過程一開始存在兩個分支：一個是患者坐救護車到醫(yī)院，另一個是患者自行到醫(yī)院掛號，之后再由醫(yī)生決定治療方案，然后進入不同的流程。由此，不同路徑的事件有差別，但仍然會共享一些服務(wù)資源，例如a5和a7。

4.1.2 過程樹生成

表2是一個將圖8中的治療過程案例抽象的例子，表中第1列代表了當(dāng)前的循環(huán)次數(shù)，第2列代表了該次循環(huán)中的流程，第3列代表需要進行重構(gòu)的活動。第3列是需要進行重構(gòu)的活動，但是并不等于該次循環(huán)只檢測出了這些活動，例如在第2次循環(huán)中，可以同時判斷出關(guān)系有×(E,F)、×(K,L)、×(G,H)、×(J,I)、×(F,E)、×(L,K)、×(H,G)、×(I,J)，但是這些關(guān)系顯然不能同時進行重構(gòu)。最終該案例被轉(zhuǎn)化為一個完整的過程樹，即→(×(→(→(A,C),×(E,F)),→(→(B,D),×(G,H))),×(→(×(K,L),N),→(×(J,I),M)))。

表2 過程模型抽象案例

4.1.3 模型化簡

表3中展示了將治療流程中的過程模型分解的案例。表中第1列表示循環(huán)次數(shù)，第2列表示該次循環(huán)中的模型，第3列表示進行重構(gòu)的活動?？梢钥闯?，得到的新模型相比原模型減少了兩個條件和12個流關(guān)系。

表3 過程模型分解案例

4.2 效率分析

在評價算法的性能之前，首先分析算法的時間復(fù)雜度。本文算法可分為抽象模型部分和分解模型部分。

抽象模型部分的復(fù)雜度由IdentifiesRelation算法、getRelationList算法、refactoringOfProcess算法以及迭代次數(shù)(過程樹深度)決定。IdentifiesRelation算法的復(fù)雜度受完全前綴展開算法影響，完全前綴展開算法的復(fù)雜度最壞情況下為O(|A|·Rξ)，|A|是模型中的活動數(shù)量，R是展開網(wǎng)中非截斷條件的數(shù)量，ξ是活動的出度和入度中的最大數(shù)，因此IdentifiesRelation算法的復(fù)雜度最壞情況下為O(|T|3+|A|·Rξ)，|T|是展開網(wǎng)中的事件數(shù)。getRelationList算法的復(fù)雜度最壞情況下為O(|T|2)，refactoringOfProcess算法的復(fù)雜度最壞情況下為O(|A|2)。

抽象模型部分的復(fù)雜度最壞情況下為O(h*(|T|3+|A|2+|A|·Rξ))，其中h*為過程模型中所包含的過程樹的最大深度。分解模型部分的復(fù)雜度為O(h*|A|2)。因此本文算法復(fù)雜度最壞為O(h*(|T|3+|A|2+|A|·Rξ))。

但通常情況下完全前綴展開算法的復(fù)雜度為O(R)，本文算法在通常情況下的時間復(fù)雜度為O(h*(|T|3+|A|2))

為了評價算法的性能，本節(jié)使用不同規(guī)模的業(yè)務(wù)過程模型模型組進行實驗，這些樣本包含不同數(shù)量、不同行為的元素。表4所示實驗數(shù)據(jù)的具體情況。其中：counts表示該組數(shù)據(jù)中的模型總數(shù)；nmin、nmax、navg分別表示該組模型中包括條件、活動和流關(guān)系在內(nèi)的最小數(shù)量、最大數(shù)量和平均數(shù)量；tmin、tmax、tavg分別表示算法在該組模型中花費的最小時間、最大時間和平均時間；WN1組數(shù)據(jù)中的模型屬于TEPM，WN2組數(shù)據(jù)中的模型屬于BSTM。

表4 實驗數(shù)據(jù)

圖9和圖10是兩組實驗樣本所對應(yīng)的時間曲線圖，其中橫軸是已化簡的模型數(shù)量，豎軸是花費的時間。這些實驗表明，算法花費的時間會隨著流程模型規(guī)模的增加而增加，但是對于大多數(shù)流程模型，算法所花費的時間平均到每個活動上都是非常短的時間(ns級，如圖11所示)。其中WN1組數(shù)據(jù)中的模型屬于TEPM，WN2組數(shù)據(jù)中的模型屬于BSTM，它們總體模型規(guī)模是相近的，但WN1的時間變化曲線更不平滑。因此，絕大多數(shù)情況下，可以認為復(fù)雜結(jié)構(gòu)所耗時間相比BSPM更加不穩(wěn)定。

4.3 對比分析

為了評價本文中算法的化簡效率和行為保持的程度，本節(jié)使用LEEMANS在文獻[26-27]中的生成過程樹方法作對比實驗，該方法使用了花模型對無法轉(zhuǎn)化的行為結(jié)構(gòu)進行了泛化。本節(jié)使用20個TEPM的案例作為原始模型，根據(jù)每個模型中包含的元素數(shù)量，將附錄表1中20個模型編號為M1～M20，將這一組模型作為PNO組實驗?zāi)Ｐ?。其中，最小模?M1)和最大模型(M2)分別包含11和50個元素。使用本文化簡算法對PNO組模型進行化簡，將化簡后的模型作為PNA組實驗?zāi)Ｐ?。使用文獻[26-27]中生成過程樹算法將PNO組模型轉(zhuǎn)化為過程樹，并根據(jù)過程樹生成相應(yīng)模型，作為PNB組實驗?zāi)Ｐ汀?/p>

三組實驗?zāi)Ｐ鸵约霸谏蒔NA和PNB兩組模型過程中產(chǎn)生的過程樹的可視圖如附錄表1所示，該表中的所有可視圖使用圖形可視化工具Graphviz(http://www.graphviz.org/)生成。觀察附錄表1中(a)列～(c)列，可以發(fā)現(xiàn)本文提出算法有效簡化了業(yè)務(wù)過程模型的復(fù)雜結(jié)構(gòu)。為客觀分析模型結(jié)構(gòu)的精簡程度，本文對比了化簡前后模型的條件數(shù)和流關(guān)系數(shù)的變化，如圖12和圖13所示?？梢园l(fā)現(xiàn)利用本文算法化簡的PNA組可以有效地減少了條件和流關(guān)系。從圖12和圖13可以看出PNB組也有效地減少條件和流關(guān)系，而且對原始模型的精簡程度更高。但實際上PNB組模型過于泛化，具體原因可見下文對模型的準(zhǔn)確率、召回率以及F1分數(shù)的分析。

表1 實驗案例

為分析本文算法對于行為保持的程度，下面將分析PNO組模型與PNA組模型、PNB組模型之間的差異，本文對模型進行仿真模擬獲取日志信息。具體地本文對三組模型中的每個模型進行1 000次仿真模擬，使每個模型都有一個對應(yīng)的路徑多重集。每個路徑多重集都會包含1 000條路徑，其中會包含大量重復(fù)路徑。去除多重集中的重復(fù)路徑可以得到路徑集合，每個模型對應(yīng)的路徑集合中的路徑數(shù)量具體如表5所示。

表5 實驗數(shù)據(jù)的路徑集的大小

路徑多重集中包含一些重復(fù)路徑，這些不同的路徑重復(fù)率可以體現(xiàn)模型不同事件的發(fā)生頻率，而路徑集去掉了重復(fù)的路徑，從表5可以看到，相比多重集的1 000條路徑，路徑集中的路徑數(shù)量被大幅度減少，特別是模型M4所對應(yīng)的路徑集只包含一條路徑，小型的路徑集有利于對模型行為進行對比分析。因此，本文同時使用路徑多重集和路徑集進行分析計算。

利用這些日志信息，將PNO組模型對應(yīng)的集合作為實際值，PNA組模型和PNB組模型對應(yīng)的集合作為預(yù)測值，就可以計算原模型與化簡后模型之間的準(zhǔn)確率、召回率以及F1分數(shù)。

本文比較了PNA組模型和PNB組模型的準(zhǔn)確率、召回率以及F1分數(shù)，如圖14～圖19所示。可以看出，PNA組模型的3種指標(biāo)值都非常高，證明PNA組模型在極大程度上還原了PNO模型的行為。而PNA組模型由于行為過于泛化，指標(biāo)值基本很低，說明了本文算法更加適應(yīng)TEPM模型，可以在保持行為(路徑集和路徑多重集的準(zhǔn)確率、召回率以及F1分數(shù)的得分都趨近于一)的條件下化簡模型。

5 結(jié)束語

本文提出一種在保持活動關(guān)系的基礎(chǔ)上化簡業(yè)務(wù)過程模型的方法。該方法采用完全前綴展開技術(shù)分析過程模型，然后快速準(zhǔn)確地提取模型的行為關(guān)系，接著根據(jù)這些行為構(gòu)造相應(yīng)行為等價過程樹。最后重組業(yè)務(wù)過程模型結(jié)構(gòu)，從而化簡了模型中的復(fù)雜結(jié)構(gòu)。該方法利用基于完全前綴展開對具有復(fù)雜結(jié)構(gòu)的業(yè)務(wù)過程模型的活動關(guān)系進行判斷，這樣可以避免“狀態(tài)空間爆炸”問題。其次，該方法可以以過程樹的形式呈現(xiàn)業(yè)務(wù)過程模型，有利于從不同角度分析模型的行為結(jié)構(gòu)。同時通過實驗驗證了化簡方法的有效性和效率。

業(yè)務(wù)過程不僅存儲控制流信息，還會包含組織維、信息維、資源維等多維信息。因此，在本文所提出的基于行為等價過程樹的業(yè)務(wù)過程模型的化簡方法的基礎(chǔ)上，如何增加流程的其他維度信息，并從不同維度化簡業(yè)務(wù)過程是下一步需要考慮的問題。