微流程模型的效率改進*

施正香 ，羅文杰 ，孫建東 ，周 洋 ，楊俊剛

(1.云南電網有限責任公司 迪慶供電局，云南 迪慶 674400；2.西南林業大學 大數據與智能工程學院，云南 昆明 650224；3.云南云電同方科技有限公司，云南 昆明 650217)

0 引言

業務流程管理是組織用來構建和更新信息系統的主要技術之一[1]。其關鍵思想是業務流程用業務流程模型來建模，而信息系統的開發通過流程模型來驅動[2]。從控制流視角，業務流程模型描述了為完成某些業務目標應該執行哪些任務以及它們的執行順序；從數據視角，業務流程模型描述了應該處理的數據；從資源視角，業務流程模型描述了誰應該負責什么任務。

為了快速響應客戶需求，應該持續演化信息系統。為了支持更好地持續演化，業務流程管理要求業務流程微化[3]。相比傳統的業務流程，微流程為特定條件下不可再分解的業務流程。當微流程模型被建模后，一個關鍵問題是能否改進該模型的效率[4]。例如，原本可并發執行的兩個任務在微流程模型中被建模為順序執行。因此，該流程模型的執行效率是低效的。

改進微流程模型是指在不改變外部行為的情況下修改流程模型內部結構的過程[5-6]?，F有研究工作主要關注改進業務流程模型的可理解性、可維護性。在改進業務流程模型的可理解性方面，文獻[7]提出了一種對業務流程模型的活動進行自動標注的方法；文獻[8]提出使用動詞-賓語的樣式對業務流程模型的活動進行標注，從而提高了業務流程模型的可理解性；文獻[9]提出了一種活動標簽的樣式轉換方法，用于將名詞樣式轉換為動詞-賓語的樣式；文獻[10]提出了一種活動標簽樣式的分類方法，用于將樣式分為名詞樣式和動詞-賓語的樣式；文獻[11]提出了一種方法，用于將活動標簽樣式進一步細分。在提高業務流程模型的可維護性方面，文獻[12]提出了一種用于提高流程模型庫中流程模型可維護性的方法；文獻[13]提出了一種識別低維護性模型的方法；文獻[14]提出了11 個業務流程模型的重構操作，用于提高模型的可維護性。與上述工作相比，本文工作的最大不同在于重點關注改進微流程模型的效率。

具體而言，本文提出了一種改進微流程模型效率的方法，主要貢獻如下：(1)根據微流程模型的結構，提出了提取任務關系的算法；(2)從數據視角，提出了分析任務間數據依賴關系的算法。

1 微流程的建模

以Petri 網為形式化基礎[15]，本文采用文獻[2]提出的帶數據的工作流網(WorkFlow net with Data，DWF-net)對微流程進行建模。

定義1(工作流網)[16]工作流網是一個6 元組WF-net=(P，T；F，M，i，o)，其中：

(1)P∪T≠?∧P∩T=?，P 為庫所集，T 為任務集；

(2)F?(P×T)∪(T×P)是流關系；

(3)映射M：P→(0，1，…)表示工作流網的標識；

(4)i∈P 表示輸入庫所；

(5)o∈P 表示輸出庫所；

(6)每一個節點x?P∪T 都位于從i 到o 的一條路徑上。

定義2(微流程)微流程是一個9 元組MP=(P，T；F，D，I，O，M，i，o)，其中：

(1)WF-net=(P，T；F，M，i，o)為工作流網；

(2)D 為WF-net 操作的數據集；

(3)I：D→2T輸入函數，描述任務的輸入數據；

(4)O：D→2T輸出函數，描述任務的輸出數據。

在微流程的圖形化表示中，本文用圓圈表示庫所，用方框表示任務，用有向線段表示流關系。

以文獻[4]中的在線購物為例，圖1 使用定義了微流程模型。首先，麥基通過互聯網在線訂購商品(任務A)，任務A 的輸出是商店地址(變量m)和買家的地址(變量n)。其次，買家可以選擇自取或郵寄來提取貨物。如果買家選擇自取方式(任務B)，他根據商店地址(變量m)到商店提貨(變量o)。在收到貨物(任務C)后，買家將收到賣家的收據(變量q)。另一種情況，如果賣家選擇郵寄方式，賣家需要準備貨物(任務D)，并確保貨物將郵寄到正確的買家地址(變量n)。為此，賣家將聯系快遞員(任務E)，貨物將被包裝上買家地址(變量n)，同時生成跟蹤號(變量p)?？爝f員交付(任務F)包裹給買家(變量o 和變量p)，買家接收貨物和收據(變量q)。在貨物和收據(變量q)檢查無誤后，買方確認接收貨物(任務G)，交易成功結束。

圖1 在線購物微流程

對于圖1 所示的線購物微流程模型，從控制流視角，任務D 和任務E 是串行執行的。但是，從數據視角，由于任務D 和E 沒有任何數據依賴，故而，它們可以并行執行。

針對上述分析，從提高模型執行效率的角度，本文對圖1 所示流程模型進行改進，使得模型中沒有數據依賴的任務都并行執行。

定義3(任務發生規則)微流程9 元組MP=(P，T；F，D，I，O，M，i，o)，并具有下述的任務發生規則：

(1)對于任務t∈T，如果?p∈*t：M(p)≥1，則說明任務t 在標識M 有發生權，記為M[t＞；

(2)若M[t＞，則表示在標識M 下，任務t 可以發生，發生后得到一個新標識M′，記為M′[t＞M，?p∈P，滿足：

①若p∈*t-t*，則M′(p)=M(p)-1；

②若p∈t*-*t，則M′(p)=M(p)+1；

③其他，則M′(p)=M(p)。

(3)通常用M0表示初始標識；

(4)一個任務發生序列σ=t0，t1，…，tn-1使從初始標識M0到達標識Mn，可標記為M0→σMn。

2 效率改進的流程

圖2 直觀描述了本文所提改進流程的步驟，具體包含4 個步驟：提取任務關系、分析數據關系、更新任務關系、重構模型。

圖2 效率改進的流程圖

2.1 提取任務關系

根據微流程模型的結構，算法1 描述了如何提取任務關系。由文獻[2]、[4]、[5]可知，流程模型中任務關系可細分為3 種關系：順序(→)、選擇(#)和并行(||)。

算法1：提取任務關系算法

輸入：MP=(P，T；F，D，I，O，M，i，o)是一個微流程模型

輸出：關系矩陣RM

(1)for p∈P do

(2) for t1∈*p do

(3) for t2∈p* do

(4) 在RM 中設置t1→t2

(5)for t1∈T do

(6) for t2∈T do

(7) if t3∈T 是t1和t2的最近匯聚節點∧t1≠t3∧t2≠t3then

(8) 在RM 中設置t1# t2

(9)for t1∈T do

(10)for t2∈T do

(11) if t1和t2不是→∧t1和t2不是# then

(12) 在RM 中設置t1||t2

需要說明的是，算法1 中的*p 和p* 分別表示庫所的前集和后集，具體定義為：對于任一節點x∈X=P∪T，*x={y∈X|(y，x)∈F}，x*={y∈X|(x，y)∈F}。

令m 和n 分別表示微流程模型中庫所和任務的個數，則算法1 的最壞時間復雜度為：O(m3)。

2.2 分析數據關系

分析數據關系是指檢測兩個任務間是否存在數據依賴關系。由文獻[4]、[5]可知，數據依賴關系可細分為3 種關系：直接數據依賴(δd)、間接數據依賴(δa)和輸出數據依賴(δo)。

根據任務的輸入和輸出，算法2 描述了如何分析數據依賴。

算法2：分析數據依賴算法

輸入：MP=(P，T；F，D，I，O，M，i，o)是一個微流程模型

輸出：數據關系矩陣DM

(1)for t1∈T do

(2) for t2∈T do

(3) if O(t1)∩I(t2)≠? then

(4) 在DM 中設置t1δdt2

(5)for t1∈T do

(6) for t2∈T do

(7) if O(t2)∩I(t1)≠? then

(8) 在DM 中設置t1δat2

(9)for t1∈T do

(10)for t2∈T do

(11) if O(t1)∩O(t2)≠? then

(12) 在DM 中設置t1δot2

令n 表示微流程中任務的個數，則算法2 的最壞時間復雜度為：O(n2)。

2.3 更新任務關系

基于關系矩陣RM 和數據關系矩陣DM，算法3 描述了如何更新任務關系。其核心思想是如果兩個任務是順序關系，但沒有任何數據依賴關系，則該順序關系可以更新為并行關系，以改進流程模型的效率。

算法3：更新任務關系算法

輸入：MP=(P，T；F，D，I，O，M，i，o)是一個 微流程 模型，關系矩陣RM 和數據關系矩陣DM

輸出：更新后的關系矩陣RM

(1)for t1∈T do

(2) for t2∈T do

(3) if RM 中t1→t2∧DM中t1與t2沒有任何數據依賴關系then

(4) 在RM 中設置t1||t2

令n 表示微流程中任務的個數，則算法3 的最壞時間復雜度為：O(n2)。

2.4 重構模型

針對算法3 輸出的更新后的關系矩陣RM，算法4借鑒α 算法[17]的思想，描述了如何重構流程模型。其核心思想是如果任務間具有順序關系，則構建庫所，使得任務通過庫所相連。

算法4：重構模型算法

輸入：關系矩陣RM

輸出：WF-net=(P，T；F，M，i，o)

(1)for t1∈T do

(2) for t2∈T do

(3) if RM 中t1→t2then

(4) P=P∪{p12}

(5) F=F∪{(t1，p12)}∪{(p12，t2)}

(6)for t1∈T do

(7) if *t1==? then

(8) P=P∪{i}

(9) F=F∪{(i，t1)}

(10)if t1*==? then

(11) P=P∪{o}

(12) F=F∪{(t1，o)}

令n 表示微流程中任務的個數，則算法4 的最壞時間復雜度為：O(n2)。

3 實驗

3.1 工具

本文采用開源工具PIPE(Platform Independent Petri net Editor)對微流程進行建模。PIPE[18]是一個開源的Petri 網建模和分析工具，被學術界廣泛使用。

圖1 所示在線購物微流程在PIPE 工具的建模實現如圖3 所示。圖4 描述了改進后的在線購物微流程在PIPE 工具中的建模實現。

圖3 在線購物微流程的建模實現截圖

圖4 改進后在線購物流程建模實現截圖

3.2 實驗結果

本文的實驗數據集來源于BPM AI 過程模型庫。BPM AI 中有學術界和工業界創建的大量真實流程模型，共計400 多個。表1 給出了部分實驗結果。

表1 部分實驗結果

為了度量微流程模型的并行度，本文基于文獻[2]中的任務出度，提出了并行度CD：

其中，dout(t)表示任務t 的出度。

表1 第1 列為編號，第2 列為改進前微流程模型的節點數和并行度，第3 列為改進后微流程模型的節點數和并行度。

從表1 可知：(1)案例case-20 和case-70 改進前后并行度不變，說明這兩個流程模型中有順序關系的任務也有數據依賴關系；(2)案例case-01、case-03、case-37和case-100 改進前后并行度和節點數均增大，說明在提高這些流程模型并行度的同時，也增加了節點數；(3)案例case-35、case-70、case-82 和case-205 改進前后并行度增大，說明在提高這些流程模型并行度的同時，這些流程模型中存在有順序關系的任務沒有數據依賴關系。

4 結論

為提高微流程模型的質量，本文使用帶數據的工作流網，提出了一種改進微流程模型效率的方法。該方法通過提取任務關系、分析數據依賴、更新任務關系和重構模型4 個步驟，將流程模型中無數據依賴關系的任務間的順序關系更新為并發關系，以提高模型的效率。實驗結果表明了該方法的有效性。