基于PageRank的業(yè)務過程活動重要性度量

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

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

0 引 言

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

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

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

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

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

1 業(yè)務過程模型的形式化表示

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

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

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

(2)P∩T=?；

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

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

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

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

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

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

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

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

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

圖1 Petri網(wǎng)中的控制結構

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

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

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

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

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

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

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

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

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

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

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

3.1 PageRank算法

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

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

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

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

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

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

(3)

其中：

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

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

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

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

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

(4)

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

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

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

4 實驗結果與分析

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

4.1 實驗模型選取和描述

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

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

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

圖3 工廠報建審批的業(yè)務過程

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

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

圖4 處理用戶投訴的業(yè)務過程

4.2 實驗分析

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

(5)

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

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

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

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

>AR(t3)>AR(t7)

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

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

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

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

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

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

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

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

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

5 結束語

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