基于關鍵路徑的工作流瓶頸挖掘與優化

杜明達,林榮恒,鄒 華

(北京郵電大學 網絡與交換國家重點實驗室,北京 100876)

1 引 言

當今世界,信息化已經成為經濟社會發展的總體趨勢,越來越多的工作通過計算機和網絡的參與得以展開和完成,我們將工作流程中的邏輯和規則抽象化并建模成為工作流,文檔、信息和任務等以數據的形式,按照預先設定的規則在工作流中的不同節點之間傳遞,驅動工作流的執行[1].根據BPMN(Business Process Model and Notation)1的定義,一個工作流是由若干事件(event)、活動(activity)、網關(gateway)和連接對象(connecting objects)等組成的.事件主要包括開始事件和結束事件,代表一個流程的開始和結束,活動代表需要完成的任務,活動之間通過連接對象進行連接.在比較復雜的工作流中,往往存在分支,即一個事件結束后可能有多個備選事件,根據預先設定的條件觸發下一個事件,分支的分流與合并用網關表示.

在實際的生產生活中,當一個工作流經過部署并執行一段時間后,我們往往更關心流程實際執行的效率及可能存在的瓶頸.如果能夠通過對工作流的執行日志和歷史數據等的挖掘找到流程執行的瓶頸,并對其進行有針對性的優化,對于提高該工作流的執行效率和整個生產生活的效率都有積極的意義.考慮到工作流是從開始事件為起點,沿著某條路徑依次完成路徑上的任務,最終以結束事件為終點,同時我們可以從流程的執行日志和歷史數據中挖掘出工作流中每一個任務的執行時間,為了實現對工作流的執行瓶頸挖掘和定位,本文將給出一種將工作流的流程圖轉化為帶權值的有向無環圖,并計算該有向無環圖的關鍵路徑的方法,并針對瓶頸提出相應的解決方案.

本文的章節安排如下:第2章將介紹在工作流程分析與優化上其他人的相關工作,第3章給出對本文工作流瓶頸的形式化定義和問題建模,第4章提出檢測工作流瓶頸的模型及解決算法,第5章以一個實際的例子進行實驗對模型及算法進行可行性驗證,第6章是結論.

2 相關工作

工作流程可以用三種方式定義模型:第一種是圖像表示法,采用流程圖的方式進行工作流的表示,從而可以快速地構建工作流程并直觀進行展示;第二種是數學表示法[2],采用形式化語義對工作流程進行嚴格準確的概念定義,這種方式的出現為使用數學分析工作流程、提取知識和推理提供了可能;第三種是業務流程語言[3],它結合了前兩種方式,以明確的語義來定義更加復雜的形式化模型,并用圖形化的方式表示其結構,這種建模方式迅速成為主流并出現了很多規范,業務流程建模語言(BPML)[注]2 OASIS, Business process execution language (WS-BPEL 2.0), wsbpel-v2.0-OS, OASIS, http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.html,2011.就是其中的代表.工作流程的優化的目標和方向,主要分為幾個方面:1)縮短交付時間和成本,提高產品質量,增強用戶滿意度[4];2)降低成本和流程時間[5];3)提高設計的“最優性”,由于流程的質量由許多常常互相沖突的標準來定義,故需要達到這些標準的整體最優[6].

為了實現流程的優化,根據工作流程定義的方式及工作流程所在的場景,不同的人給出了不同的解決方案.文獻[7]提出了采用圖元(metagraph)的數據接口來表示工作流;從而為科學地分析工作流、更有效地設計組織流程提供解決方法;文獻[8]提出使用活動圖對工作流進行建模,進而轉化為Petri圖,使用Petri網分析工作流模型;文獻[9]提出一種將帶有時間信息的有向網絡圖所表示的工作流模型抓華為時序約束工作流網絡的模型映射方法;文獻[10]提出一個對工作流循環范式進行規范分析的框架.近年來,人們越來越關注對工作流執行產生的事件日志的挖掘,文獻[11]采用ProM框架實現對流程的決策挖掘,檢測影響流程路由選擇的數據依賴;文獻[12]給出了將ProM框架應用于流程日志挖掘應用于道路及水利基礎設施建設及維護的例子;文獻[13,14]分別在醫療保健和廣告市場中對工作流程的日志進行挖掘和分析.

在流程分析和流程優化技術上,文獻[15]基于工作流可以視為圖形的事實,將圖形內核應用于工作流的分析工作中,如工作流發現、工作流推薦、工作流模式提取等.文獻[16]實現了一個基于電子表格的業務流程分析工具;文獻[17]提出一個同時優化流程結構和流程執行策略的數學規劃模型.George Tsakalidis團隊提出了以演化計算技術為基礎的流程優化框架[18],后來在框架中引入兩個計算單元[19],分別用于補貨流程設計及計算與評估流程屬性,同時引入算法檢查每個候選解決方案的可行性.

3 問題定義

本章將給出關于流程瓶頸的定義,并對解決問題進行定義和建模.

3.1 流程瓶頸定義

對于流程的執行瓶頸,我們定義如下:流程中每個活動都有對應的執行時間,每個流程也對應一個總的執行時間,如果存在某個活動,當該活動的執行時間縮短或延長時,流程的總執行時間也相應縮短或延長,我們則稱該活動為流程的執行瓶頸.對于存在多條執行分支及多個任務活動的流程,可以具有多個執行瓶頸.我們將多個在邏輯上具有連續性的執行瓶頸構成的執行路徑稱為流程的關鍵路徑.顯然對于關鍵路徑上的活動,都是我們可以考慮優化的目標活動.

以圖1所示的流程圖為例,在流程中一共存在三條執行路徑:

P1:estart→e1→g1→e2→e3→g2→e4→g3→g4→e8→eend

P2:estart→e1→g1→e2→e3→g2→e5→g3→g4→e8→eend

P3:estart→e1→g1→e6→e7→g4→e8→eend

圖1 一個簡單的流程圖Fig.1 A simple flow chart

對于三條執行路徑,直觀上會認為P1,P2的執行時間要高于P3所需要的執行時間.然而我們需要通過計算每一條路徑的平均執行時間才能得到最終的結果.當e6、e7的總執行時間過大時,可以導致P3的總執行時間要高于其他兩條執行路徑.

當實際生活中給定的流程更加復雜,節點更多,分支更多時,我們在設計初期往往很難把握哪些節點的存在導致了整個流程的執行時間變長.

我們可以采用反證法證明,在具有多條執行分支的流程中,總的執行時間最長的執行路徑就是流程的關鍵路徑.假設存在一條執行時間不是最長的執行路徑,它也是流程的關鍵路徑,根據前文中流程關鍵路徑的定義,該路徑上的所有活動都要滿足“當該活動的執行時間縮短/延長時,流程的總執行時間也相應縮短或延長”.對于該路徑上的活動,如果該活動也在執行時間最長的路徑上存在,顯然滿足定義.對于不在執行時間最長的路徑上存在的活動,當活動的執行時間變短時,該執行路徑的總執行時間也將相應變短,然而流程的總執行時間與流程中最長的執行路徑的執行時間相關,此時該活動并不影響最長的執行路徑的執行時間,故流程的總執行時間并不會相應變短,不滿足條件.因此,一個流程中執行時間最長的執行路徑就是流程的關鍵路徑.

對于流程的每一個執行實例,我們可以輕易地從流程的執行日志中計算出該實例上每一個活動的執行時間,因此,對于一個給定的流程,我們可以統計多個執行實例中每個活動的執行情況,得到一個平均的執行時間,這個時間代表了一般情況下該活動的執行時間.

故我們要解決的問題可以轉化為,對于任意一個給定的具有多條執行分支的流程,我們要找到多條路徑中總執行時間最長的路徑,該路徑就是流程的關鍵路徑,該路徑上的每一個活動都是流程的執行瓶頸,通過對這些執行瓶頸的分析和優化,我們有希望提高這些執行瓶頸的執行效率,從而提高整個流程的執行效率.

3.2 問題定義

根據上一小節中我們對流程瓶頸的定義,我們結合BPMN中對工作流程的定義,以形式化的方式對問題進行定義,以求更清晰和準備地描述問題,為下一章模型的提出和算法的設計做鋪墊.

我們定義工作流程為S=(E,A,R,C).

其中E= {estart,,e1,e2,…,e|E|-2,eend}為事件集合,特別地,estart,表示開始事件,eend表示結束事件.

A= {a1,a2,…,a|A|} 為活動集合.

R= {ri:ea×eb→ai|aa,ab∈E,ai∈A} 為E集合與A集合的映射關系集合,表示了事件和活動之間的對應關系,一個活動連接了兩個事件.

C= {c1,c2,…,c|A|} 為活動消耗時間的集合,每一個活動ai對應一個ci.在工作流中,活動ai所連接的兩個事件的起始時間的差值,即為該活動的耗時ci.

根據流程瓶頸定義,對于一個工作流程S,我們需要計算找到A的一個最小子集AC,滿足:

1)連通性:estart經過所有Ac后能到達eend;

2)唯一性:去掉AC中的任意元素ai, 1)無法成立;

3)在滿足連通性和唯一性的條件下,AC的總耗時為最大.

我們希望可以找到這樣的子集AC,并通過優化AC,使得AC的總耗時變小.

4 解決方案

在上一章中我們得到了流程瓶頸的定義,在本章中我們提出將工作流的流程圖轉化為帶權值的有向無環圖,并計算該有向無環圖的關鍵路徑的方法,涉及到對流程圖的模型定義,對關鍵路徑的計算的算法.大致的流程如圖2 所示.

圖2 基于關鍵路徑的工作流瓶頸挖掘與優化的總體流程Fig.2 Overall process of workflow bottleneck mining and optimization based on critical path

其中流程日志清洗部分,將目標流程的日志從流程日志中分離出來,剔除異常數據,并計算每一個流程實例中每個活動的執行時間,進而算出該活動的平均執行時間,代表流程中該任務的執行時間.流程模型抽象部分,將采用帶權值的有向無環圖對流程進行建模.流程瓶頸計算部分,提出基于關鍵路徑的流程瓶頸挖掘方法,對流程瓶頸進行計算.流程瓶頸優化部分,根據流程瓶頸計算結果,結合業務流程的具體場景,給出可能的優化方案.

4.1 模型定義

進一步的,我們將網關從流程圖中去掉,則圖1所示的流程圖最終對應的有向無環圖如圖3所示.

圖3 圖1流程圖對應的有向無環圖Fig.3 Directed acyclic graph of flow chart in Fig.1

問題轉化為求該帶權值的有向無環圖G的關鍵路徑CP(Critical Path).

關鍵路徑CP是G中從起點到終點的最長路徑,由于在流程中有些活動可以并行執行,故CP的權值之和代表了執行完該工作流程的最長時間,路徑上的每條邊所代表的活動即為工作流程的執行瓶頸,縮短CP上任一邊代表的活動的執行時間,都可以縮短整個工作流程的總執行時間,提高工作流程的執行效率.

在圖1 所示的流程圖中,我們通過計算可以得到:

P1的執行時間為C1=c1+c2+c3+c4+c6+c11

P2的執行時間為C2=c1+c2+c3+c5+c7+c11

P3的執行時間為C3=c1+c8+c9+c10+c11

故最長路徑為maximum(C1,C2,C3).

4.2 基于關鍵路徑的流程瓶頸挖掘方法

本節將具體描述基于關鍵路徑的流程瓶頸挖掘方法.我們將流程圖形式化描述得到帶權值的有向無環圖G后,基于計算關鍵路徑的方法對該有向無環圖進行計算,從而得到流程的瓶頸.該方法包括了以下兩個過程.

過程1.通過拓撲排序找出圖中所有節點的合法執行順序.

輸入:有向無環圖G的V集合、E集合

輸出:圖G各節點的拓撲排序序列topologicalSort數組

1 初始化一個數組inDegree[]用于存儲每個節點的入度,初始值均為0

2 對于E中的每一條邊e={vi,vj}:

3 更新inDegree[j]的值為inDegree[j] + 1

4 初始化一個空的數組topologicalSort[]表示拓撲排序的結果

5 當節點集合V中還有節點未加入數組topologicalSort中時:

6 遍歷集合V中未加入數組topologicalSort且入度為0的節點v:

7 將v加入數組topoligicalSort末尾

8 遍歷集合E中的每一條e={vj,vi}:

9 更新inDegree[j]的值為inDegree[j] - 1

10 返回結果數組topologicalSort

過程2.根據拓撲排序結果計算每個節點的最早開始時間和最晚開始時間,最早開始時間與最晚開始時間相等的節點即為關鍵路徑上的節點.

輸入:有向無環圖G的V集合、E集合、C集合,topologicalSort數組

輸出:關鍵路徑的節點集合CP

1 定義數組EST[]表示節點的最早開始時間

2 定義數組LST[]表示節點的最晚開始時間

3 按順序遍歷topologicalSort數組中的每一個節點vi:

4 若是第一個節點,更新EST[i]的值為0

5 若不是第一個節點,遍歷集合E中所有以vi為目標節點的邊ea={vj,vi}:

6 計算(C[a] +EST[j])的值

7 將所有(C[a] +EST[j])的值計算完畢后取最大值即為EST[i]的值

8 按逆序遍歷topologicalSort數組中的每一個節點vi:

9 若是最后一個節點,更新LST[i]的值為EST[i]

10 若不是最后一個節點,遍歷集合E中所有以vi為開始節點的邊ea={vi,vj}

11 計算(LST[j] -C[a])的值

12 將所有(LST[j] -C[a])的值計算完畢后取最小值即為LST[i]的值

13 初始化一個空的集合CP表示關鍵路徑上的節點

14 遍歷集合V中的每一個節點vi:

15 如果EST[i]與LST[i]相等,將vi加入集合CP中

16 返回結果集合CP

經過過程1與過程2的計算,最終我們得到了有向無環圖G中最早開始時間與最晚開始時間的相等的節點的集合,該集合所能組成的路徑即為原流程的流程瓶頸.

5 實驗與結果分析

本章將分兩部分進行,第一部分是對基于關鍵路徑的流程瓶頸挖掘方法進行正確性的驗證,第二部分我們將該方法應用與一個具體的流程中,通過對流程數據的挖掘和分析找出流程瓶頸并進行優化,驗證方法的可行性.

5.1 方法的正確性驗證

如圖4所示,我們選取了一個具有100個節點的有向無環圖進行基于關鍵路徑的流程瓶頸挖掘方法的驗證,其中實心的節點構成的路徑為預期的流程的關鍵路徑,通過計算我們得到的實際關鍵路徑為:

1→2→3→4→6→7→14→15→16→17→18→23→24→26→28→27→29→30→31→32→37→36→38→41→42→43→44→64→63→62→66→69→70→77→78→79→80→82→83→90→91→92→93→94→95→96→97→98→99→100.符合預期.

5.2 方法在具體流程實例中的應用

我們以某公司的物資申請流程為例,流程的起點為各科室發起物資申請,根據物資的內容分為大宗物資和小件物資,大宗物資需要制定采購計劃并提交院務辦審核,審核通過后提交財務審核,之后由采購科進行采購及后續的核對和驗收,之后入庫并進行物資發放.若是小件物資的申請,則直接查詢庫存,庫存充足則直接發放物資,庫存不足則發起采購并提交財務科審核,之后的流程與大宗物資采購的流程一致.

圖4 一個具有100個節點的有向無環圖Fig.4 A directed acyclic graph with 100 nodes

該物資采購的流程及對應的有向無環圖如圖5,圖6所示.

圖5 物資采購流程圖Fig.5 A material procurement flow chart

我們選取該流程實際執行之后得到的日志,統計后得到如圖7所示的數據.

圖6 物資采購流程的有向無環圖Fig.6 Directed acyclic graph of material procurement flow chart

經過計算后得到的關鍵路徑為:

v1→v2→v3→v4→v5→v6→v7→v8→v11→v12→v13→v14

該流程的總耗時約為27.30小時.

我們將關鍵路徑上的各個節點與流程圖對應之后可發現,造成流程執行瓶頸的路徑是大宗物資的采購流程.進一步分析各個節點的執行時間可以發現,大部分大宗物資在“采購”任務上的執行時間均高于執行時間,而在其后的“財務科進行核對”及“采購科進行采購驗收”也花費了較多的時間.我們考慮到在從“審批立項”之后財務科進行“財務審核”開始到采購科“采購驗收”的子流程,各個任務之間均存在較強的關聯度.在對采購項目進行財務審核需要對各采購物資的采購細節進行審核,在采購結束后進行核對時還說需要針對采購細節進行核對,最終采購科進行采購驗收時仍舊需要核對各采購細節.由于在“采購”任務上花費了大量的時間,我們可以在“財務審核”之后添加一個與“采購”并行執行的任務—“制定核驗標準”,根據之前財務審核中對各種采購細節的審核,由財務科制定與本次采購相關的“核驗標準”,之后的核對任務急采購驗收任務可以根據該核驗標準進行核對和驗收,從而提高流程在“核對”任務和“采購驗收”任務上的執行效率.

圖7 物資采購流程各任務耗時情況Fig.7 Time cost of tasks in material procurement flow chart

經過優化后的流程如圖8所示.

圖8 優化后的物資采購流程圖Fig.8 Material procurement flow chart after optimization

如之前的分析所示,在“財務審核”任務執行之后,分成了兩條并行的分支,在采購科進行采購的過程中,財務科執行“制定核驗標準”,之后這兩條分支匯聚.

優化后的流程對應的有向無環圖如圖9所示.

圖9 優化后的物資采購流程的有向無環圖Fig.9 Directed acyclic graph after optimization

我們選取改進后的流程執行一段時間后得到的日志,統計計算后得到如圖10所示的數據.

經過計算后得到的關鍵路徑為:

v1→v2→v3→v4→v5→v6→v7→v8→v11→v12→v13→v14

該流程的總耗時約為24.62小時.

圖10 優化后物資采購流程各任務耗時情況Fig.10 Time cost of tasks after optimization

5.3 實驗結果分析

與優化前的流程相比,我們可以看到,優化后的流程雖然關鍵路徑不變,但是流程總體的總耗時較優化前有所縮短.

我們將流程優化前后各個任務的平均耗時數據進行對比,得到圖11.

圖11 物資采購流程優化前后各任務瓶頸耗時對比Fig.11 Contrast of time cost before and after optimization

可以看到,優化后,關鍵路徑不變,關鍵路徑上e7,e8的耗時明顯下降,即“核對->采購驗收->入庫”的效率明顯提高,其中“核對->采購驗收”的平均耗時從2.62小時降到1.32小時,效率提高49.6%,“采購驗收->入庫”的平均耗時從1.81小時降到了0.72小時,效率提高了60.2%;整個流程增加了e16,e17兩個任務,由于不在關鍵路徑上,并不會對流程的整體執行效率起決定作用.流程的總執行時間從27.30小時降到24.62小時,效率提高了9.8%.

6 結論與不足

本文提出了工作流中關于流程瓶頸的定義,并提出將工作流的流程圖轉化為帶權值的有向無環圖,通過計算該有向無環圖的關鍵路徑得到工作流的流程瓶頸的方法,同時以某公司物資采購的流程為例,進行流程瓶頸的挖掘并根據結果給出優化方案.對于拓撲復雜,具有較多的分支的工作流程,該方法可以較快較直觀地計算出流程的瓶頸,因此可以應用與相似的工作流程.

然而該方法不能很好地處理帶環的工作流,對于帶環的工作流,該計算可能陷入某種循環中.故對于帶環的工作流,我們還需要進一步的處理,例如采用等效替換等,將工作流中的環進行抽象,用一個任務進行等效替換,對于該問題的具體方案,還有待進一步研究.