基于PageRank的業務過程活動重要性度量

高 濤，周 彪，孔 會，艾合買提尼牙孜，郁 湧,3

(1.云南經濟管理學院 教育學院，云南 昆明 650033；2.云南大學 軟件學院，云南 昆明 650504；3.云南省軟件工程重點實驗室，云南 昆明 650504)

0 引 言

在當今激烈競爭的環境下，企業要想能夠很好地生存、發展并擴大其競爭優勢，就迫切需要用系統的方法和工具對其業務過程進行分析、優化和管理，因而業務過程管理得到了學術界和工業界的普遍重視。業務過程管理是致力創新企業業務過程管理、分析、控制與改進的系統化和理論化方法，目的是為了使企業能夠不斷改進產品質量和提升其服務水平[1]。

業務過程管理就是從企業的業務過程出發來對其業務過程進行全方位的管理和分析，并能夠支持企業對業務過程的不斷持續改進，從而在理論上和實踐上都具有廣闊的研究空間和應用范圍[2]。業務過程管理自從開始受到國內學者和相關研究人員的關注[3-4]以來，已在多方面、多角度取得了一系列的研究成果：

在協同業務過程的建模方法和正確性分析方面，文獻[5-6]提出自頂向下建模方法，并在此基礎上從契約中生成對應組織的相關業務過程；文獻[7]采用自底向上建模方法來定義企業自身的業務過程，并用它來構建具有協同功效的協同業務過程；文獻[8-9]根據正確性約束對業務過程內部結構進行修改以自動構建滿足正確性約束的業務過程；文獻[10]結合Petri網和過程挖掘來提出一種針對協同業務過程的修正方法；文獻[11]基于模型檢測技術提出一種需求一致性檢測方法，實現需求一致性自動驗證；文獻[12]在兼顧同步和異步交互的基礎上，用簡單路徑來刻畫協同業務過程的行為。

在業務過程時間預測方面，文獻[13]使用了一種機器學習算法對業務過程進行剩余執行時間的預測；文獻[14]根據發現的業務流程特征之間相關性來對業務過程剩余時間進行預測；文獻[15]考慮事件的附加屬性以改進時間預測質量；文獻[16]提出一種結合回歸與聯合概率矩陣分解的時間預測方法；文獻[17]提出一種基于依賴關聯度的噪聲日志過濾方法，通過軌跡可達性分析去除日志中的噪聲；文獻[18]構建一個嵌套的預測模型和使用嵌套模型樹回歸算法進行完成時間的預測；文獻[19]提出基于控制流分析技術來預測運行過程實例剩余時間的白盒方法；文獻[20]提出了基于貝葉斯網絡的稱為CRAFFT的活動預測方法。

雖然業務過程管理已經在多方面、多角度取得了很多的研究成果，但是，業務過程管理的管理對象多種多樣，運行過程比較復雜。業務過程管理需要使用各種方法、技術和軟件工具來設計、執行、控制和分析可執行的過程以及過程中涉及的人員、組織、應用、文檔或其他信息資源[1]。為了能夠很好地對業務過程中的資源和人員進行合理的配置和調配，使其能夠高效準確地運行，這就需要對業務過程中的活動之間的關系和活動的重要性進行分析和度量，從而根據活動的重要性來合理分配資源。為此，該文在基于Petri網表示的業務過程基礎上，對業務過程中活動之間的依賴關系進行分析和度量，并借鑒PageRank算法的思想來提出一種業務過程活動重要性度量的指標和方法。

1 業務過程模型的形式化表示

業務過程指一個或一系列連續有規律的行為以確定的方式發生或執行，產生特定結果。Davenport和Short將業務過程定義為“以達成特殊業務成果目標的一系列有邏輯相關性的任務”和“企業過程是一系列結構化的、可測量的活動的集合，并為特定市場或特定顧客產生特定輸出”[21]。在業務過程管理的相關方面，研究人員通常使用Petri網來對業務過程進行直觀的描述，從而以便于人們之間的溝通和理解。Petri網是德國科學家Petri博士于1962年在其博士論文《用自動機通信》中提出的一種網狀結構的理論模型[22]，Petri網和業務過程模型的表示如下：

定義1 Petri網[23]。Petri網是一個四元組∑=(P,T;F,M)，其中：

(1)P∪T≠?，P為庫所集，T為變遷集；

(2)P∩T=?；

(3)F?(P×T)∪(T×P)，F是有向弧集，表示∑上的流關系；

(4)映射M：P→{0,1,2,…}稱為Petri網的一個標識。通常用M0表示Petri網的初始標識。

定義2 前集[23]。設∑為一個Petri網，若x∈P∪T，·x={y∈P∪T|(y,x)∈F}，則稱·x為x的前集。

定義3 后集[23]。設∑為一個Petri網，若x∈P∪T，x·={y∈P∪T|(x,y)∈F}，則稱x·為x的后集。

定義4 工作流網[24]。Petri網WF-net=(P，T；F，M)是工作流網，當且僅當：

(1)存在一個源庫所i∈P，使得·i=?；

(2)存在一個匯聚庫所o∈P，使得o·=?；

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

工作流網是荷蘭業務過程領域專家Aalst教授在Petri網的基礎上提出來的一種業務過程的建模工具，目前已經成為組織內業務過程管理和控制流建模的首選模型之一，因此，該文就用工作流網來表示業務過程。在工作流網中，庫所集P={p1,p2,…,pn}表示業務過程中的n個不同狀態、階段或者條件等；變遷集T={t1,t2,…,tm}表示業務過程中m個不同的活動，有向弧集F表示業務過程中的控制結構關系。在業務過程中，存在4種基本的控制結構，即：順序、并行、選擇和循環，其表示方式如圖1所示。

圖1 Petri網中的控制結構

2 業務過程中活動之間依賴關系分析和度量

業務過程是以達成特殊業務成果為目標的一系列有邏輯相關性和有規律的活動的集合，因此，業務過程中的活動之間會存在一定的依賴關系。本部分在基于Petri網表示的業務過程基礎上，通過分析業務過程中活動之間的相關性來進行依賴關系的分析和度量。

定義5 依賴關系。對于一個業務過程WF-net=(P，T；F，M)中的兩個活動ti,tj∈T，如果滿足活動tj的執行要以活動ti的后集為前提，即ti·∩·tj≠?，則稱活動tj直接依賴于活動ti，表示為tj→ti；否則稱活動tj不直接依賴于活動ti。

如果活動tj直接依賴于活動ti，則活動tj稱為依賴的活動，活動ti稱為被依賴的活動。業務過程中活動之間的直接依賴關系和依賴程度由業務過程中活動之間的控制結構和活動的使能條件來共同決定。

比如，在圖2(1)的順序結構中，活動t2的前集是活動t1的后集，因此，活動t2直接依賴于活動t1，并且活動t1沒有執行的情況下，活動t2就得不到執行，因此，可以認為活動t2完全依賴于活動t1。在圖2(2)中，活動t5的前集是活動t3和活動t4的共同后集，活動t5直接依賴于活動t3或者活動t4，只要活動t3或者活動t4有一個執行，活動t5就可以執行，因此活動t5只是部分依賴于活動t3或者活動t4；但是活動t3和活動t4是并行結構，它們的執行是同步的，而它們之間沒有直接依賴關系。同理可以看出，在圖2(3)中，活動t8部分依賴于活動t6和活動t7；在圖2(4)中，活動t10和活動t9之間具有循環結構，活動t10完全依賴于活動t9，而活動t9只是部分依賴于活動t10。

圖2 不同控制結構中的直接依賴關系

從圖2的示例可以看出，業務過程中不同活動之間的直接依賴關系的強弱是不一樣的，可以把活動之間的直接依賴關系的強弱稱為依賴關聯度，它度量了當一個活動失效或者發生改變后對后繼活動產生的影響程度。依賴關聯度由所依賴活動的前集庫所數和能夠為其提供資源的活動數來確定，當能夠提供資源的活動數越多時，對相應活動的依賴關聯度就越??；反之，則越大。為此，在業務過程中，可以把活動之間的依賴關聯度表示為：

定義6 依賴關聯度。對于一個業務過程WF-net=(P，T；F，M)中的兩個活動ti,tj∈T，如果活動tj直接依賴于活動ti，即ti·∩·tj≠?，則活動tj對活動ti的依賴關聯度Dtj→ti的取值為：

其中，|·tj|表示活動tj的前集·tj中所含庫所的數量，而|·x|、|{ti}∩·x|分別表示·x、{ti}∩·x中所含活動的數量。業務過程中所有活動之間的依賴關聯度可以用一個m×m的鄰接矩陣DL=(Dij)m×m表示，稱為活動之間依賴關聯度鄰接矩陣，其中：

從活動之間依賴關聯度的計算公式(1)容易看出，活動tj對活動ti的依賴關聯度Dtj→ti的取值范圍為[0，1]。當活動tj對活動ti沒有直接依賴關系時，其依賴關聯度取值為0；活動tj對活動ti具有完全的依賴關系時，其依賴關聯度取值為1。

3 基于PageRank的業務過程活動重要性度量

3.1 PageRank算法

PageRank算法[25]是搜索引擎中用于網頁排序的經典算法，其目的就是通過計算頁面鏈接的數量和質量來確定和標識網站的重要性并進行網頁排名。該算法是基于“從優質網頁鏈接而來的網頁必定還是優質網頁”這樣的思想和回歸關系，也就是：當某個網頁pj有一個連接指向網頁pi，就認為pi獲得了pj對它貢獻的分值，該值的多少取決于網絡pj本身的重要程度，即網頁pj的重要性越大，網頁pi獲得的貢獻值就越高。由于網絡中網頁之間連接關系具有相互指向性，因此，網站中各個網頁的重要性計算就是一個不斷迭代的過程，最終網頁可以根據重要性的得分值來進行檢索和排序。在PageRank算法中，它把網頁之間的鏈接關系看成一個有向圖，然后根據網頁之間的相互鏈接結構來實現的，算法的表達式為：

其中，p1，p2，…，pn表示網頁；M(pi)表示待研究網頁pi的網頁鏈入數；L(pj)表示網頁pj的網頁鏈出數；n表示網絡中的所有網頁數量；PageRank(pi)表示網頁pi的PageRank值，所有網頁的PageRank值構成網絡的PageRank向量；q為阻尼系數，用來表示任意時刻用戶在瀏覽某個網頁之后還會繼續瀏覽它之后的網頁的概率。通常情況下，阻尼系數的取值為0.85。

根據公式(2)可知，如果指向某個網頁pi的鏈接數目越大，鏈接源對應的網頁的重要性越高，則該網頁pi就越重要，從而計算出來的PageRank值也就越大。

3.2 基于PageRank算法的活動重要性度量

在業務過程中，根據活動之間的直接依賴關系和依賴關聯度鄰接矩陣，可以構建對應的加權網絡有向圖。在此有向圖中，節點就是業務過程中的活動，而節點之間邊的方向和權重由活動之間的直接依賴關系和依賴關聯度來確定。因此，可以將PageRank算法的思想引入到業務過程的活動重要性度量中，從而提出一種業務過程活動重要性評估的指標和方法。

對于業務過程WF-net=(P，T；F，M)中的活動ti∈T來說，如果活動tj直接依賴于活動ti，則活動tj的重要性對活動ti的重要性取值有貢獻；活動tj的重要性越大，活動ti獲得的貢獻值就越高。同時，在業務過程中，不同直接依賴關系的活動之間的關聯度并不完全相同，依賴關聯度的大小對活動之間的貢獻值也會有所差異，依賴關聯度越大，則對應的貢獻值也就越高。因此，根據業務過程的特點，在考慮活動之間依賴關聯度的情況下，一個活動的重要性由依賴于它的活動的重要性及其它們之間的依賴關聯度來共同決定，用公式表示為：

(3)

其中：

(1)AR(ti)表示活動ti的重要性取值；

(2)(ti·)·表示依賴于活動ti的所有活動的集合；

(4)m表示業務過程中的所有活動的數量；

(5)q為阻尼系數，表示業務過程中活動重要性依賴于其他活動的程度，阻尼系數越大，活動重要性的依賴程度就越大。

在業務過程中，由于活動之間具有順序和循環等交互關系，活動之間的依賴關系具有傳遞性，這使得活動的重要性計算是一個迭代過程。因此，在計算活動的重要性過程中可以用向量Si=(AR(t1,i),AR(t2,i),…,AR(tm,i))來表示第i次迭代獲得的活動重要性取值，向量Si和活動取值AR(t1,i)中的下標i表示迭代的輪次。迭代過程中，可以用概率轉移矩陣Q來記錄一個活動到達另一個活動的概率，概率轉移矩陣Q由活動之間依賴關聯度來確定，表示為：

(4)

由于各個活動重要性取值的計算存在迭代性，為此，可以為業務過程中所有活動設置一個初始得分，即：

S0=(AR(t1,0),AR(t2,0),…,AR(tm,0))=

然后用活動的重要性計算公式(3)來更新所有活動的重要性取值，不斷迭代，直到活動重要性向量Si=(AR(t1,i),AR(t2,i),…,AR(tm,i))的取值收斂為止，這樣就可以快速地求出業務過程中每個活動的重要性。

4 實驗結果與分析

實驗部分將利用該文提出的依賴關系分析和重要性度量方法對現實的業務過程模型中活動之間的依賴關系和活動的重要性進行分析和度量，并根據實驗結果來分析該算法的合理性和有效性。

4.1 實驗模型選取和描述

本實驗所選取的兩個業務過程模型，一個是電子政務中工廠報建審批業務過程[26]，另一個是公司處理用戶投訴的業務過程[27]，這些業務過程模型都包括順序、并行、選擇和循環等結構，具有一定的代表性。

在工廠報建審批業務過程中，申報人首先需要根據自己的情況來如實填寫和提交申報材料，然后再進行政策法規方面的預審；如果預審通過，那么相關的申報材料就必須在30天之內完成環保部門的審批；否則原來的預審結論就會失效，必須重新進行預審。工廠報建審批業務過程用Petri網表示，如圖3所示，業務過程中各個活動表示為：

t1：填寫和提交申請材料；t2：預審批；t3：規劃審批；t4：環保審批；t5：活動超時處理；t6：數據超時處理；t7：綜合審批；c1、c2、c3為連接符。

圖3 工廠報建審批的業務過程

在處理用戶投訴的業務過程中，當公司接到客戶投訴時，首先需要對客戶的投訴信息進行登記，然后同步處理向客戶寄出調查表和對投訴進行評估這兩個活動；如果客戶能夠在14天之內返回調查表，則任務調查表和后續的活動就會被執行，否則，將會被拋棄。對于返回的調查表，公司會根據評估的結果來確定是否需要對該投訴進行處理。在處理用戶的投訴業務過程中，都是通過任務檢查進程進行檢查，然后進行歸檔，從而結束整個過程。處理用戶投訴的業務過程用Petri網表示，如圖4所示，業務過程中各個活動表示為：

t1：登記；t2：寄出調查表；t3：投訴評估；t4：過期處理；t5：調查表處理；t6：投訴不需要處理；t7：投訴需要處理；t8：處理投訴；t9：檢查處理結果；t10：檢查不合格；t11：檢查合格；t12：歸檔。

圖4 處理用戶投訴的業務過程

4.2 實驗分析

本節利用提出的依賴關系分析和重要性度量方法對選取的兩個業務過程模型中活動之間的依賴關系和活動的重要性進行分析。在進行活動重要性度量時，本實驗中的阻尼系數q按照通常的取值為0.85。同時，由于基于PageRank的業務過程中活動的重要性度量得到的重要性取值一般都比較小，為了使結果具有可區分度，本實驗中對每個活動的重要性取值都除以對應業務過程中活動重要性取值的最大值來進行歸一化處理，即：

(5)

在對業務過程進行依賴關系分析和重要性度量之后，可以根據活動之間依賴關系和重要性度量的結果構建對應的加權網絡有向圖來進行表示，其中節點為不同的活動，節點之間的邊表示活動之間的直接依賴關系，邊的方向為直接依賴關系的方向，邊上的權重為活動之間的依賴關聯度。這樣，工廠報建審批和處理用戶投訴的業務過程對應的依賴關聯度和活動重要性取值的網絡有向圖分別如圖5和圖6所示，其中活動下方的值為活動的重要性取值。

圖5 工廠報建審批業務過程的依賴關系和活動重要性

從圖5的結果可以看出，在工廠報建審批的業務過程中，各個活動的重要性大小關系為：

AR(t5)>AR(t4)>AR(t1)=AR(t6)>AR(t2)

>AR(t3)>AR(t7)

(注：由于c1、c2、c3為連接符，沒有比較重要性的必要，因此就做省略處理。)

其中，活動t5(活動超時處理)和活動t4(環保審批)重要性取值較大，而活動t7(綜合審批)的重要性取值較小。這樣的結果與工廠報建審批的實際情況是一致的，因為在具體業務中活動超時處理和環保審批階段的工作都比較重要，應該重視或者分配更多的資源；而綜合審批階段由于是報建審批業務中的收尾環節，因此重要性相對會弱一些。

圖6 處理用戶投訴的業務過程的依賴關系和活動重要性

圖6所示的處理用戶投訴的業務過程中，各個活動的重要性大小關系為：

AR(t7)=AR(t10)>AR(t1)>AR(t8)>AR(t2)

=AR(t3)=AR(t9)>AR(t4)=AR(t5)

>AR(t6)=AR(t11)>AR(t12)

根據重要性大小關系可以看出，活動t7(投訴需要處理)和活動t10(檢查不合格)的重要性取值最大，活動t12(歸檔)的重要性取值最??；在其他活動中，活動t2與活動t3、活動t4與活動t5之間是并行關系，因此它們之間的重要性取值相同；此外，從重要性取值可以看出活動t1(登記)和活動t8(處理投訴)比活動t2(寄出調查表)重要；活動t3(投訴評估)與活動t9(檢查處理結果)同樣重要；活動t4(過期處理)比活動t6(投訴不需要處理)等。這些活動重要性取值的結果與處理用戶投訴過程的實際情況具有很大的吻合性與一致性。

總之，在業務過程活動依賴關系分析和度量的基礎上，借鑒PageRank的思想來提出的活動之間重要性度量方法，在對工廠報建審批業務過程和處理用戶投訴業務過程中活動重要性度量和排名分析方面獲得的結果比較符合現實業務過程的情況，說明提出的算法具有一定的合理性和有效性。

5 結束語

業務過程管理是企業用來對其業務過程進行管理、分析、控制與改進的系統化和理論化方法，業務過程管理的最終目標在于通過進行業務過程的管理來不斷提高和改進所生產產品的質量，并提升其自身的服務水平。近年來，雖然業務過程管理已經在多方面、多角度取得了一系列的研究成果，但是，針對業務過程中活動的重要性度量方面的研究，尚屬鮮見。然而，合理分析業務過程中活動之間的依賴關系并給出活動的重要性度量和排名，是進行活動的資源和人員合理的配置和調配的關鍵之一。為此，在基于Petri網表示的業務過程基礎上，提出了一種業務過程中活動之間的依賴關系分析和活動重要性度量的方法。主要工作如下：(1)根據業務過程中活動之間的控制結構和活動的使能條件來對活動之間的直接依賴關系進行分析；(2)基于活動之間的直接依賴關系和依賴關聯度取值來構建活動之間的加權網絡有向圖，并將PageRank的思想引入到業務過程的活動重要性度量中，提出一種業務過程活動重要性評估的方法；(3)以現實中的工廠報建審批業務過程和公司處理用戶投訴的業務過程為案例進行分析和研究，根據實驗結果來分析該算法的合理性和有效性。結果表明，在業務過程中活動的依賴關系分析的基礎上，結合PageRank算法來提出的活動重要性度量和排名的方法，具有較好的表現效果。