基于工作流程系統(tǒng)日志生成業(yè)務(wù)流程模型
tjdlut
摘要：工作流管理系統(tǒng)利用流程模型來管理業(yè)務(wù)流程模型，通常來說，該模型采用帶有活動名稱的圖來表示。本文視活動的執(zhí)行過程為一個時間間隔，并采用一種新的算法從系統(tǒng)日志集中生成業(yè)務(wù)流程模型。該模型圖能夠生成日志中所隱含的活動執(zhí)行過程和活動和活動之間的依賴關(guān)系，并且能夠保留活動中現(xiàn)存的平行性。
關(guān)鍵詞：業(yè)務(wù)流程管理；工作流；工作流系統(tǒng)日志；流程模型
對于公司來說建立起合適的業(yè)務(wù)流程模型是非常重要的，以自動化或者半自動化方式來管理流程能夠大幅度提高業(yè)務(wù)執(zhí)行的工作效率，降低成本，使公司更快地適應(yīng)不斷變化的需求和業(yè)務(wù)的增長[1]。因此，組建和管理業(yè)務(wù)流程的技術(shù)是當(dāng)今一個非常活躍的研究領(lǐng)域。
工作流管理系統(tǒng)采用可視化信息流模型來監(jiān)視和管理事先定義好的活動和任務(wù)。商業(yè)工作流系統(tǒng)和管理平臺需要一個業(yè)務(wù)模型以執(zhí)行動作、控制生產(chǎn)，等等?，F(xiàn)今大多ERP/CRM產(chǎn)品采用嵌入工作流模型的方式來給業(yè)務(wù)流程建模。大多數(shù)企業(yè)中運行的信息系統(tǒng)中并不包含適用于該單位的業(yè)務(wù)流程模型，僅僅停留在對企業(yè)資源的操作上，因此，能夠?qū)ζ髽I(yè)業(yè)務(wù)流程建模的技術(shù)對于提高企業(yè)競爭力和提高企業(yè)在IT上的投資收益率非常重要。本文提出一種基于存在于工作流日志信息生成業(yè)務(wù)流程模型的方法。該模型采用向量圖，圖中的結(jié)點代表活動，從A結(jié)點到B結(jié)點的邊代表在A活動結(jié)束和B活動開始之間有一個流程執(zhí)行過程[2]。單獨的一個業(yè)務(wù)流程模型里，流程執(zhí)行過程所參與的邊與邊之間有一個布爾函數(shù)（0=false，1=true），該函數(shù)控制流是否通過該邊。
基于事件的模型和本模型不同的是，前者把一個活動的執(zhí)行過程看作是一個單獨的事件，而本模型將其看作是開始事件和終止時間的時間間隔，而這正是多數(shù)工作流系統(tǒng)日志中所記錄的模式。通過這種方法，由于并發(fā)活動的生命周期是相互交叉的，我們可以識別處在一個單獨流程執(zhí)行過程中所包含的并發(fā)活動，而這正是基于事件的模型所不能發(fā)現(xiàn)的。此外基于工作流系統(tǒng)日志，本模型能夠發(fā)現(xiàn)并發(fā)活動產(chǎn)生時所需的條件。
本模型定義了活動之間的因果關(guān)系以及描述了一種能夠根據(jù)日志產(chǎn)生工作流圖的算法。本模型的特點如下：
1） 完整性：在日志中所記錄的每一個流程執(zhí)行過程都依據(jù)該模型生成相應(yīng)的流程圖。
2） 正確性：日志中記錄的所有依賴關(guān)系都存在于流程圖中。
3） 保持并行性：如果在日志數(shù)據(jù)中體現(xiàn)出活動A和B是并發(fā)的，那么在生成的圖中將會有兩條路徑，其中一條包含A而不含B，另一條包含B而不包含A[3]。
通過本文提出的算法，生成的流程圖與原始的工作流圖類似，但可能會產(chǎn)生一些多余邊或者丟失一些邊，多余或丟失邊的數(shù)量依據(jù)日志的質(zhì)量和大小而定，對于如何防止以上的錯誤的發(fā)生，現(xiàn)在仍無定論，只能提高日志的質(zhì)量來保證生成流程圖最大的準(zhǔn)確性。
一個工作流模型通常使用向量圖來表示，向量圖中包含代表活動的結(jié)點和向量邊組成。在活動A和活動B之間有一個向量邊代表在A執(zhí)行后B能夠立即執(zhí)行；在這種情況下，邊上的控制函數(shù)的值是1（true）。定義B是A的后繼，A是B的前導(dǎo)。對于B是否能夠在A執(zhí)行后立即執(zhí)行取決于AàB的控制函數(shù)的值（1代表能夠執(zhí)行，0代表不執(zhí)行）[4]。在這個模型里，活動的執(zhí)行被認(rèn)為是原子性的，也就是說沒有兩個活動能夠同時執(zhí)行；一個業(yè)務(wù)流程就可以看作是串行的活動的集合。在下文中，本文將把這個模型擴展為更加精確的表達方式，其中，活動的執(zhí)行被看作是時間軸上的間隔，而這兩個間隔有可能有重疊（并發(fā)）。
首先定義工作流圖的執(zhí)行過程為一個線性化的流，這個流用一連串的活動來表示，例如A=a1,a2,……,an,該流以活動a1為起始點，以an為終點。在這個模型里，一個活動只能出現(xiàn)一次。
圖1是一個簡單的工作流模型圖和兩個有效的子流圖。在流程（a）中，從A到C和從B到D的控制函數(shù)的值為0（false）。在流程（b）中從B到C的邊上的值也是0。執(zhí)行過程Execution（A，B，C，D）是在流程（a）和流程（b）中都是一個合法的，有效的過程，但是Execution(A,C,B,D)僅僅在流程（b）中是有效的[5]。
工作流圖 流程（a） 流程（b）
圖1 工作流模型圖和兩個有效流圖
對于一個給定的工作流模型，定義以下連個條件：
[CA]在一個圖中如果[a1,ai,aj,an]并且[ai,aj,ai,an] 成立那么ai和aj稱為并發(fā)活動，也就是說兩個執(zhí)行過程中，其中一個過程里ai出現(xiàn)在aj前，在另一個過程里aj出現(xiàn)在ai前那么，ai，aj稱為并發(fā)的活動。
[NS]在所有有效的執(zhí)行過程里面，如果永遠不出現(xiàn)ai=aj+1那么ai就不是aj的后繼。
舉例來說，在流程（b）中,B和C是并發(fā)活動，而D永遠不是A的后繼。
工作流日志中包含監(jiān)視流程執(zhí)行的數(shù)據(jù)信息，每個執(zhí)行過程由執(zhí)行的活動按照時間順序組成。WFMC提出的標(biāo)準(zhǔn)的日志格式包括每個活動的起始事件、終止事件。代數(shù)表達式為{ready, started, restarted, ended normally, force finished, terminated}。很明顯，在一個執(zhí)行過程中可能會包含噪聲事件，比如一個forece finished的事件表明該活動含有噪聲，那么我們可以將其刪除掉[6]。如果一個事件是{started, restarted} 那么該事件就是起始事件；如果一個事件不是起始事件或者不是一個ready事件的話，那么該事件就是一個終止事件。
一個活動在它啟動之前，它必須處于一個ready狀態(tài)。一旦它啟動了，那么它就應(yīng)該能夠正常結(jié)束，被迫結(jié)束或者消亡。一個執(zhí)行過的活動的生命周期是從它的start狀態(tài)到它的terminate事件的時間段，活動的擴展生命周期是readyàterminate的時間段。每個事件都代表在系統(tǒng)中的一次狀態(tài)變化，比如，一個系統(tǒng)在start事件執(zhí)行之前將會一直保持ready狀態(tài)。
根據(jù)間隔模型可以將[CA]條件擴展如下：
[rCA] 對于一個給定的一系列活動事件，如果在活動ai和aj的擴展生命周期里面存在重疊，那么ai和aj就是一對并發(fā)的活動。
本章將描述如何從工作流系統(tǒng)日志生成一個業(yè)務(wù)流程圖。一個圖是由一系列執(zhí)行或稱產(chǎn)生的，活動執(zhí)行過程中時間間隔交叉現(xiàn)象導(dǎo)致活動并發(fā)的發(fā)生[7]。在描述算法之前我們給出幾個基本的定義：1）當(dāng)前點集（Current Frontier,在以下簡稱為CF），下一點集（Next Frontier，以下簡稱NF），當(dāng)前點集是最新加入圖中的點的集合，這時他們的輸出度為0。2）當(dāng)前時間（Current Time,以下簡稱為CT），下一時間（Next Time，以下簡稱NT）。
算法：
圖中第一個點是起始活動，第一個點是CF，它的終止事件的時間是CT。以下步驟一直執(zhí)行到最后一個活動的終止事件的時間為CT。
1． NT= CT后第一個完成的事件的時間
2． 將NT和CT之間處于ready狀態(tài)的活動所代表的點加入到圖中，這些點作為NF。
3． 將CF中的每一個點和NF中的每一個點相連。
4． 把CF改為NT所包含的事件和NT后第一個處于ready狀態(tài)的點之間所有完成的事件所代表的活動的點的集合[8]。把CT改為上面集合中最后處于完成狀態(tài)的活動的終止時間。
5． 循環(huán)1à4
為了解釋如上算法的含義，舉例如下：
例1（A,A’,B,C,D,C’,E,B’,F,D’,F’,G,G’,E’,H,H’）
STEP1 STEP2
1. CF1=A,CT1=A’,NT1=C’; 1.CF2=C,CT2=C’,NT2=B’;
2. NF1=[B,C,D]; 2.NF2=E;
3. 3.
4. CF2=C, CT2=C’. 4. CF3=B, CT3 = B’;
STEP3 STEP4
1. CF3=B, CT3=B’, NT3 =D’; 1. CF4=[D,F], CT4=F’, NT4= G’
2. NF3 =F; 2. NF4 =G;
3. 3. 
4. CF4=[D,F], CT4 = F’. 4. CF5=[G,E], CT5=E’.
STEP5
1. CF5=[G, E], CT5= E’, NT5 = H’;
2. NF5=H;
3.
圖2 例1的執(zhí)行圖
4. CF5=H,NT5=H’.
例2（A,A’,C,C’,F,E,E’,F’,H,H’）
圖3 例2的執(zhí)行圖
例3（A,A’,D,D’,G,G’,H,H’）
圖4 例3的執(zhí)行圖
本文提出的從工作流系統(tǒng)日志數(shù)據(jù)中生成業(yè)務(wù)流程的算法經(jīng)實際檢驗中比其他同類方法更加迅速和精確，產(chǎn)生的冗余邊和丟失邊基本控制在5%以內(nèi)，為了更好的減少誤差，可以考慮在每個邊上加上權(quán)重，用權(quán)重來表示執(zhí)行和邊之間的關(guān)系，這樣噪聲會更加少，此方法須進一步改進，最終會成為一套對如何正確完整地生成企業(yè)業(yè)務(wù)流程有很高參考價值的算法。
[1] Agrawal, R., Gunopulos, D., Leymann, F.: Mining process models from workflow logs. In: Advances in Database Technology - EDBT’98, 6th International Conference on Extending Database Technology, Valencia, Spain, March 23-27, 1998,Proceedings. Volume 1377 of Lecture Notes in Computer Science., Springer (1998)
[2] Georgakopoulos, D., Hornick, M.: An overview of workflow management: From process modeling to workflow authomation infrastructure. Distributed and Parallel Database 3 (1995) 119–153
[3] Wastell, D., White, P., Kawalek, P.: A methodology for business process re-design:experiences and issues. Journal of Strategic Information Systems 3 (1994) 23–40
[4] Cook, J.E., Wolf, A.L.: Event-based detection of concurrency. In: Sixth International
Symposium on the Foundation of Software Engineering (FSE-6). (1998) 35–45
[5]. Hollingsworth, D.: The workflow reference model. Technical Report TC00-1003 issue 1.1, workflow management coalition, UK (1995)
[6] Ellis, C., Kkeddara, K.: A workflow change is a workflow. In: W.M.P. van der Aalst, J. Desel, and A. Oberweis, editors. Business Process Management: Models,Techniques, and Empirical Studies, volume 1806 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2000, Berlin, Germany, Springer-Verlag (2002) 45–63
[7] van der Aalst, W., van Hee, K.: workflow Management: Models, Methods, and Systems. Number TC00-1003 issue 1.1. MIT press, Cambridge, MA (2002)
[8] Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workflow evolution. In: In proceedings of ER 96, Cottubus, Germany (1996) 438–455
