基于工作流程系統(tǒng)日志生成業(yè)務(wù)流程模型

tjdlut

摘要：工作流管理系統(tǒng)利用流程模型來管理業(yè)務(wù)流程模型，通常來說，該模型采用帶有活動(dòng)名稱的圖來表示。本文視活動(dòng)的執(zhí)行過程為一個(gè)時(shí)間間隔，并采用一種新的算法從系統(tǒng)日志集中生成業(yè)務(wù)流程模型。該模型圖能夠生成日志中所隱含的活動(dòng)執(zhí)行過程和活動(dòng)和活動(dòng)之間的依賴關(guān)系，并且能夠保留活動(dòng)中現(xiàn)存的平行性。

關(guān)鍵詞：業(yè)務(wù)流程管理；工作流；工作流系統(tǒng)日志；流程模型

正文

1引言

對于公司來說建立起合適的業(yè)務(wù)流程模型是非常重要的，以自動(dòng)化或者半自動(dòng)化方式來管理流程能夠大幅度提高業(yè)務(wù)執(zhí)行的工作效率，降低成本，使公司更快地適應(yīng)不斷變化的需求和業(yè)務(wù)的增長^[1]。因此，組建和管理業(yè)務(wù)流程的技術(shù)是當(dāng)今一個(gè)非?；钴S的研究領(lǐng)域。

工作流管理系統(tǒng)采用可視化信息流模型來監(jiān)視和管理事先定義好的活動(dòng)和任務(wù)。商業(yè)工作流系統(tǒng)和管理平臺(tái)需要一個(gè)業(yè)務(wù)模型以執(zhí)行動(dòng)作、控制生產(chǎn)，等等。現(xiàn)今大多ERP/CRM產(chǎn)品采用嵌入工作流模型的方式來給業(yè)務(wù)流程建模。大多數(shù)企業(yè)中運(yùn)行的信息系統(tǒng)中并不包含適用于該單位的業(yè)務(wù)流程模型，僅僅停留在對企業(yè)資源的操作上，因此，能夠?qū)ζ髽I(yè)業(yè)務(wù)流程建模的技術(shù)對于提高企業(yè)競爭力和提高企業(yè)在IT上的投資收益率非常重要。本文提出一種基于存在于工作流日志信息生成業(yè)務(wù)流程模型的方法。該模型采用向量圖，圖中的結(jié)點(diǎn)代表活動(dòng)，從A結(jié)點(diǎn)到B結(jié)點(diǎn)的邊代表在A活動(dòng)結(jié)束和B活動(dòng)開始之間有一個(gè)流程執(zhí)行過程^[2]。單獨(dú)的一個(gè)業(yè)務(wù)流程模型里，流程執(zhí)行過程所參與的邊與邊之間有一個(gè)布爾函數(shù)（0=false，1=true），該函數(shù)控制流是否通過該邊。

2 模型特點(diǎn)

基于事件的模型和本模型不同的是，前者把一個(gè)活動(dòng)的執(zhí)行過程看作是一個(gè)單獨(dú)的事件，而本模型將其看作是開始事件和終止時(shí)間的時(shí)間間隔，而這正是多數(shù)工作流系統(tǒng)日志中所記錄的模式。通過這種方法，由于并發(fā)活動(dòng)的生命周期是相互交叉的，我們可以識別處在一個(gè)單獨(dú)流程執(zhí)行過程中所包含的并發(fā)活動(dòng)，而這正是基于事件的模型所不能發(fā)現(xiàn)的。此外基于工作流系統(tǒng)日志，本模型能夠發(fā)現(xiàn)并發(fā)活動(dòng)產(chǎn)生時(shí)所需的條件。

本模型定義了活動(dòng)之間的因果關(guān)系以及描述了一種能夠根據(jù)日志產(chǎn)生工作流圖的算法。本模型的特點(diǎn)如下：

1）  完整性：在日志中所記錄的每一個(gè)流程執(zhí)行過程都依據(jù)該模型生成相應(yīng)的流程圖。

2）  正確性：日志中記錄的所有依賴關(guān)系都存在于流程圖中。

3）  保持并行性：如果在日志數(shù)據(jù)中體現(xiàn)出活動(dòng)A和B是并發(fā)的，那么在生成的圖中將會(huì)有兩條路徑，其中一條包含A而不含B，另一條包含B而不包含A^[3]。

通過本文提出的算法，生成的流程圖與原始的工作流圖類似，但可能會(huì)產(chǎn)生一些多余邊或者丟失一些邊，多余或丟失邊的數(shù)量依據(jù)日志的質(zhì)量和大小而定，對于如何防止以上的錯(cuò)誤的發(fā)生，現(xiàn)在仍無定論，只能提高日志的質(zhì)量來保證生成流程圖最大的準(zhǔn)確性。

3 模型架構(gòu)

一個(gè)工作流模型通常使用向量圖來表示，向量圖中包含代表活動(dòng)的結(jié)點(diǎn)和向量邊組成。在活動(dòng)A和活動(dòng)B之間有一個(gè)向量邊代表在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]。在這個(gè)模型里，活動(dòng)的執(zhí)行被認(rèn)為是原子性的，也就是說沒有兩個(gè)活動(dòng)能夠同時(shí)執(zhí)行；一個(gè)業(yè)務(wù)流程就可以看作是串行的活動(dòng)的集合。在下文中，本文將把這個(gè)模型擴(kuò)展為更加精確的表達(dá)方式，其中，活動(dòng)的執(zhí)行被看作是時(shí)間軸上的間隔，而這兩個(gè)間隔有可能有重疊（并發(fā)）。

首先定義工作流圖的執(zhí)行過程為一個(gè)線性化的流，這個(gè)流用一連串的活動(dòng)來表示，例如A=a1,a2,……,an,該流以活動(dòng)a1為起始點(diǎn)，以an為終點(diǎn)。在這個(gè)模型里，一個(gè)活動(dòng)只能出現(xiàn)一次。

圖1是一個(gè)簡單的工作流模型圖和兩個(gè)有效的子流圖。在流程（a）中，從A到C和從B到D的控制函數(shù)的值為0（false）。在流程（b）中從B到C的邊上的值也是0。執(zhí)行過程Execution（A，B，C，D）是在流程（a）和流程（b）中都是一個(gè)合法的，有效的過程，但是Execution(A,C,B,D)僅僅在流程（b）中是有效的^[5]。

工作流圖                          流程（a）                          流程（b）

圖1 工作流模型圖和兩個(gè)有效流圖

對于一個(gè)給定的工作流模型，定義以下連個(gè)條件：

[CA]在一個(gè)圖中如果[a1,ai,aj,an]并且[ai,aj,ai,an] 成立那么ai和aj稱為并發(fā)活動(dòng)，也就是說兩個(gè)執(zhí)行過程中，其中一個(gè)過程里ai出現(xiàn)在aj前，在另一個(gè)過程里aj出現(xiàn)在ai前那么，ai，aj稱為并發(fā)的活動(dòng)。

[NS]在所有有效的執(zhí)行過程里面，如果永遠(yuǎn)不出現(xiàn)ai=aj+1那么ai就不是aj的后繼。

舉例來說，在流程（b）中,B和C是并發(fā)活動(dòng)，而D永遠(yuǎn)不是A的后繼。

4 日志結(jié)構(gòu)和間隔模型

工作流日志中包含監(jiān)視流程執(zhí)行的數(shù)據(jù)信息，每個(gè)執(zhí)行過程由執(zhí)行的活動(dòng)按照時(shí)間順序組成。WFMC提出的標(biāo)準(zhǔn)的日志格式包括每個(gè)活動(dòng)的起始事件、終止事件。代數(shù)表達(dá)式為{ready, started, restarted, ended normally, force finished, terminated}。很明顯，在一個(gè)執(zhí)行過程中可能會(huì)包含噪聲事件，比如一個(gè)forece finished的事件表明該活動(dòng)含有噪聲，那么我們可以將其刪除掉^[6]。如果一個(gè)事件是{started, restarted} 那么該事件就是起始事件；如果一個(gè)事件不是起始事件或者不是一個(gè)ready事件的話，那么該事件就是一個(gè)終止事件。

一個(gè)活動(dòng)在它啟動(dòng)之前，它必須處于一個(gè)ready狀態(tài)。一旦它啟動(dòng)了，那么它就應(yīng)該能夠正常結(jié)束，被迫結(jié)束或者消亡。一個(gè)執(zhí)行過的活動(dòng)的生命周期是從它的start狀態(tài)到它的terminate事件的時(shí)間段，活動(dòng)的擴(kuò)展生命周期是readyàterminate的時(shí)間段。每個(gè)事件都代表在系統(tǒng)中的一次狀態(tài)變化，比如，一個(gè)系統(tǒng)在start事件執(zhí)行之前將會(huì)一直保持ready狀態(tài)。

根據(jù)間隔模型可以將[CA]條件擴(kuò)展如下：

[rCA] 對于一個(gè)給定的一系列活動(dòng)事件，如果在活動(dòng)ai和aj的擴(kuò)展生命周期里面存在重疊，那么ai和aj就是一對并發(fā)的活動(dòng)。

5 生成業(yè)務(wù)流程圖

   本章將描述如何從工作流系統(tǒng)日志生成一個(gè)業(yè)務(wù)流程圖。一個(gè)圖是由一系列執(zhí)行或稱產(chǎn)生的，活動(dòng)執(zhí)行過程中時(shí)間間隔交叉現(xiàn)象導(dǎo)致活動(dòng)并發(fā)的發(fā)生^[7]。在描述算法之前我們給出幾個(gè)基本的定義：1）當(dāng)前點(diǎn)集（Current Frontier,在以下簡稱為CF），下一點(diǎn)集（Next Frontier，以下簡稱NF），當(dāng)前點(diǎn)集是最新加入圖中的點(diǎn)的集合，這時(shí)他們的輸出度為0。2）當(dāng)前時(shí)間（Current Time,以下簡稱為CT），下一時(shí)間（Next Time，以下簡稱NT）。

算法：

圖中第一個(gè)點(diǎn)是起始活動(dòng)，第一個(gè)點(diǎn)是CF，它的終止事件的時(shí)間是CT。以下步驟一直執(zhí)行到最后一個(gè)活動(dòng)的終止事件的時(shí)間為CT。

1．  NT= CT后第一個(gè)完成的事件的時(shí)間

2．  將NT和CT之間處于ready狀態(tài)的活動(dòng)所代表的點(diǎn)加入到圖中，這些點(diǎn)作為NF。

3．  將CF中的每一個(gè)點(diǎn)和NF中的每一個(gè)點(diǎn)相連。

4．  把CF改為NT所包含的事件和NT后第一個(gè)處于ready狀態(tài)的點(diǎn)之間所有完成的事件所代表的活動(dòng)的點(diǎn)的集合^[8]。把CT改為上面集合中最后處于完成狀態(tài)的活動(dòng)的終止時(shí)間。

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í)行圖

6結(jié)論

本文提出的從工作流系統(tǒng)日志數(shù)據(jù)中生成業(yè)務(wù)流程的算法經(jīng)實(shí)際檢驗(yàn)中比其他同類方法更加迅速和精確，產(chǎn)生的冗余邊和丟失邊基本控制在5%以內(nèi)，為了更好的減少誤差，可以考慮在每個(gè)邊上加上權(quán)重，用權(quán)重來表示執(zhí)行和邊之間的關(guān)系，這樣噪聲會(huì)更加少，此方法須進(jìn)一步改進(jìn)，最終會(huì)成為一套對如何正確完整地生成企業(yè)業(yè)務(wù)流程有很高參考價(jià)值的算法。

參考文獻(xiàn)

[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