，

(安徽理工大學(xué)，安徽 淮南 232001)

0 引 言

目前，業(yè)務(wù)流程模型管理在各個(gè)業(yè)務(wù)領(lǐng)域中發(fā)揮著重要作用，將流程模型轉(zhuǎn)化為工作流Petri網(wǎng)，能夠?qū)⒘鞒踢\(yùn)行直觀化，流程的變化也可以進(jìn)一步被研究。文獻(xiàn)[1]提出了一種從事件日志中挖掘可變的片段的方法，提出從事件日志中提取形態(tài)學(xué)片段的新算法以實(shí)現(xiàn)其組合性和靈活性。文獻(xiàn)[3]提出了一組變更模式和變更支持特性，以促進(jìn)系統(tǒng)對現(xiàn)有流程管理技術(shù)相對于變更支持的比較。文獻(xiàn)[6]探究了流程模型之間的變化傳播，并提出在一個(gè)模型中給定一個(gè)變化，之后利用對應(yīng)活動的行為輪廓決定另一個(gè)模型的變化，指出引起異常行為的變化都能通過目標(biāo)模型與源模型相比對的途徑查找得出。文獻(xiàn)[8]從變化分類角度來動態(tài)評估變化對整個(gè)流程系統(tǒng)的影響。使用 Petri 網(wǎng)對系統(tǒng)變化的研究大都集中在變化的檢測與診斷上，本文從工作流Petri網(wǎng)出發(fā)，利用可行跡及變遷間的最小后繼關(guān)系找出網(wǎng)系統(tǒng)中的變化，給出變化后的網(wǎng)系統(tǒng)。

1 基礎(chǔ)知識

定義1[2](工作流Petri網(wǎng)) 一個(gè)網(wǎng)N=S,T;F,i,o稱為工作流Petri網(wǎng)，當(dāng)且僅當(dāng)：

(1)該P(yáng)etri網(wǎng)有唯一的源庫所i:·i=φ；

(2)該P(yáng)etri網(wǎng)有唯一的終止庫所o:o·=φ；

(3)該P(yáng)etri網(wǎng)上的每一個(gè)節(jié)點(diǎn)都屬于i到o的一條路徑上,即Petri網(wǎng)是強(qiáng)連通的。

定義2[5](標(biāo)記工作流網(wǎng))N=S,T;F,i,o為一個(gè)工作流網(wǎng)，∑為事件集合，標(biāo)記函數(shù)λ:T→∑,M0為初始標(biāo)識，則LWN=N,∑,λ,M0為一個(gè)標(biāo)記工作流網(wǎng)。

定義3[7](行為輪廓) 設(shè)是一個(gè)網(wǎng)N,M0，初始標(biāo)識為M0,對任給的變遷對t1,t2∈T×T滿足下面關(guān)系;

(1)若t1?t2且t2≯t1，則稱嚴(yán)格序關(guān)系，記作t1→t2；

(2)若t1≯t2且t2≯t1，則稱排他關(guān)系，記作t1+t2；

(3)若t1?t2且t2?t1，則稱交叉序關(guān)系，記作t1||t2；

將所有關(guān)系的集合叫做網(wǎng)系統(tǒng)的行為輪廓，記作BP=→,+,||

定義4(可行跡) 一個(gè)過程模型所有活動的集合記為A，α∈A，活動α的執(zhí)行為一個(gè)事件記為ε(ε∈εi)；一個(gè)可行跡是指一個(gè)能夠發(fā)生的序列τ=ε1,…,εn，每個(gè)可行跡對應(yīng)于一個(gè)過程的執(zhí)行。

2 業(yè)務(wù)系統(tǒng)中的變化檢測與診斷

2.1 模型假設(shè)

假設(shè)：1、假設(shè)所有變遷都有不為空的標(biāo)記；2、業(yè)務(wù)系統(tǒng)N,Mi是合理的工作流網(wǎng)。

下面給出兩種變化的定義：DELETE和MOVE。

存在網(wǎng)系統(tǒng)Σ，網(wǎng)系統(tǒng)Σ′由網(wǎng)系統(tǒng)Σ經(jīng)過一系列的變化產(chǎn)生。

DELETE：在網(wǎng)系統(tǒng)Σ中，存在t∈T，在Σ′中活動t不存在，稱這種變化為刪除。

MOVE：在網(wǎng)系統(tǒng)Σ中存在t1→t2，在網(wǎng)系統(tǒng)Σ′中，有t2→t1；稱這種變化為移動；此定義針對本文示例提出，因此具有單一性。

2.2 算法分析

下面以工作流網(wǎng)為研究背景，給出了基于可行跡及最小后繼關(guān)系的系統(tǒng)變化定位算法。

算法1：工作流網(wǎng)中系統(tǒng)變化的定位算法(Changes Identification Algorithm for Workflow-Net system，簡記為CIA算法)

輸入：源模型Σ=S,T;F,M,一組行為事件跡，源模型最小后繼關(guān)系矩陣；

輸出：變化后的網(wǎng)系統(tǒng)Σ′。

步驟：

Step1：根據(jù)網(wǎng)Σ=S,T;F,M，計(jì)算最小后繼關(guān)系；

Step2：通過給出的一組可行跡集合STrace，利用行為輪廓關(guān)系，即BP=→,+,||,計(jì)算minimalk-successorrelations，簡稱為R。

Step3R1：圖1網(wǎng)系統(tǒng)對應(yīng)的最小后繼關(guān)系，表1所示；R2：可行跡的最小后繼關(guān)系。

3.1比較R1，R2尋找后繼關(guān)系不一致的變遷對ti,tj

(1)If?t∈STrace，Rti,tj∈R1,Rti,tj?R2,并且

R1ti,tj=R2ti,tj+1,ThenT′=T′-tjΣ=S′,T′;F′；

(2)IfR2ti,tj=R1tj,ti并且R2=tj,tmm≠j=R1ti,tmm≠i

ThenT′=?t∈STrace|t=ti,tj=tΣ=S′,T′;F′。

2.3 舉例說明

下面舉例分析上述算法的實(shí)施步驟：首先給出一個(gè)過程模型和其對應(yīng)的網(wǎng)系統(tǒng)。對系統(tǒng)變化進(jìn)行定位分析，檢測變化變遷，計(jì)算出存在變化的工作流網(wǎng)，畫出對應(yīng)的網(wǎng)系統(tǒng)，下面列舉DELETE和MOVE兩種變化檢測來驗(yàn)證方法的可行性。

以BPMN語言對業(yè)務(wù)流程建模，A-H代表活動，X-Y代表事件。如圖1所示：

圖1 過程模型及其對應(yīng)的網(wǎng)系統(tǒng)

針對圖1所給出的網(wǎng)系統(tǒng)，列出變遷對之間的后繼關(guān)系，不存在后繼關(guān)系的變遷對用小黑點(diǎn)表示；若變遷對行為輪廓關(guān)系為||的后繼關(guān)系為1，處于+的不存在后繼關(guān)系。具體如表1所示：

表1 圖1網(wǎng)系統(tǒng)對應(yīng)的最小后繼矩陣

接下來給出網(wǎng)系統(tǒng)的幾組跡利用可行跡及變遷之間的最小后繼關(guān)系定位變化變遷位置。下面給出網(wǎng)系統(tǒng)中的所有可行跡：[X,A,B,H],[X,A,C,D,H],[X,A,C,D,F,D,H],[X,A,C,G,H],[Y,A,B,H],[Y,A,C,D,H],[Y,A,C,D,F,D,H],Y,A,C,G,H此類變遷可以出現(xiàn)在同一條跡中，所以任何變遷對之間不存在排他序關(guān)系，又已知網(wǎng)系統(tǒng)中變遷對X,Y為排他序關(guān)系，因?yàn)槠洳煌瑫r(shí)出現(xiàn)在一條執(zhí)行跡中；又有X,A,B,C,D,G,H,X,A,B,C,D,F,D,G,H,Y,A,B,C,D,G,H,Y,A,B,C,D,F,D,G,H,以變遷B,C為例，可以同時(shí)發(fā)生但又不出現(xiàn)在單獨(dú)的可行跡中，這類變遷對之間的行為輪廓關(guān)系為||，相互之間最小后繼關(guān)系為1。

利用這組跡計(jì)算變遷之間的最小后繼關(guān)系，首先以變遷X為例，變遷X在前四條跡中都有發(fā)生權(quán),并且變遷H的發(fā)生是在變遷B,D,G發(fā)生之后發(fā)生的，因此變遷B,D,G是變遷H發(fā)生的必要條件；而變遷X,A,C發(fā)生是變遷G發(fā)生的必要條件，同時(shí)X,A,C發(fā)生是變遷D發(fā)生的必要條件，變遷B的發(fā)生需要變遷X,A同時(shí)發(fā)生，因此存在σ0=X∧σ0+6=H因此其最小后繼關(guān)系為6；同理，可以計(jì)算σ0=A∧σ0+4=H。分析給出的所有跡，變遷A,B,C,D,F,G相對于變遷X的最小后繼關(guān)系分別為1，2，2，4，3；變遷B,C,D,F,G,H相對于變遷A的最小后繼關(guān)系分別為1，1，2，3，2，5；依次類推，得出存在變化變遷網(wǎng)系統(tǒng)的后繼關(guān)系矩陣如表2：

表2 存在變化的最小后繼關(guān)系矩陣1

與表1給出的最小后繼關(guān)系表比較得變遷H相對于其它變遷活動后繼關(guān)系發(fā)生了明顯的變化，聯(lián)合網(wǎng)系統(tǒng)1變遷E未在任意一條執(zhí)行跡中出現(xiàn)，變遷E的缺失導(dǎo)致了網(wǎng)系統(tǒng)的變化，由后繼關(guān)系表可得出E為變化產(chǎn)生的位置，給出相應(yīng)的網(wǎng)系統(tǒng)如圖2所示，用虛線框來標(biāo)注此類變遷。

圖2 變化網(wǎng)系統(tǒng)1

圖3 變化網(wǎng)系統(tǒng)2

圖4 某自動售票機(jī)Petri網(wǎng)模型

在網(wǎng)系統(tǒng)1中σ0=X,σ4=E,變遷E相對于X的后繼關(guān)系為4，而在表2中，可以清晰的看到變遷E無發(fā)生權(quán)；所以變遷E的診斷最多可經(jīng)過4個(gè)變遷的發(fā)生，即K=4。

同樣地，已知一組跡：[X,A,B,H],[X,A,G,D,E,H],[X,A,G,D,F,D,E,H],[X,A,G,C,H],[Y,A,B,H],[Y,A,G,D,E,H],[Y,A,G,D,F,D,E,H],以變遷活動Y為例進(jìn)行分析，類似于上述分析由存在變遷Y的后四條跡可得：Y→H存在7后繼關(guān)系，變遷A,B,C,D,E,F,G,相對于變遷Y的最小后繼關(guān)系分別為1，2，3，3，4，4，2；B,C,D,E,F,G,H相對于A的最小后繼關(guān)系分別為1，2，2，3，3，1，6；又已知跡:[X,A,B,G,D,C,E,H], [X,A,B,G,D,F,D,C,E,H],[Y,A,B,G,D,C,E,H],[Y,A,G,D,F,D,C,E,H]；C,D,E,F,G,H相對于B的最小后繼關(guān)系為1，1，1，1，1，1；依次類推，得出變遷之間的后繼關(guān)系如表3。

表3 存在變化的最小后繼關(guān)系矩陣2

與表1最小后繼關(guān)系表作對比，可知變遷C參與的后繼關(guān)系與變遷G參與的后繼關(guān)系進(jìn)行了交換，同時(shí)由可行跡變遷之間的行為輪廓關(guān)系可知C，G之間的執(zhí)行順序發(fā)生了交換，由C→G變?yōu)镚→C,由此可以推斷出存在變化的網(wǎng)系統(tǒng)。

在變化網(wǎng)系統(tǒng)中，σ0=X∧σ0+2=G,σ0=X∧σ0+3=C，所以最多分別經(jīng)過2個(gè)3個(gè)變遷的發(fā)生能夠診斷出執(zhí)行關(guān)系發(fā)生變化的變遷G，C，即KG=2,KC=3。如圖3：

3 實(shí)例分析

在實(shí)際生活中，把業(yè)務(wù)流程轉(zhuǎn)化為Petri網(wǎng)模型，基于Petri網(wǎng)可行跡對網(wǎng)系統(tǒng)中的變化進(jìn)行檢測和診斷，能夠有效地找出問題所在，為了驗(yàn)證所提方法的有效性，下面以一個(gè)自助售票系統(tǒng)為例，現(xiàn)某游客欲通過自助售票系統(tǒng)進(jìn)行購票且為第一次購買，圖4描述了某火車自助售票機(jī)的Petri網(wǎng)系統(tǒng)，其中每個(gè)變遷的含義如表4所示：

表4 圖4變遷含義

某游客在購買火車票時(shí)可采取現(xiàn)金支付或銀行卡支付兩種支付方式，現(xiàn)某游客選擇銀行卡支付，在支付期間假設(shè)活動t38“支付完成”無法正常執(zhí)行，系統(tǒng)顯示為“支付失敗”，我們利用可行跡的方法對問題進(jìn)行檢測，已知原網(wǎng)系統(tǒng)的可行跡為[t26,t27,t28,t29,t30,t31,t32,t33,t34,t35,t36,t37,t38,t39]給出一組跡[t26,t27,t28,t29,t30,t31,t32,t33,t34,t35,t34,t35,t38]，可以看出活動t34,t35,t34,t35發(fā)生了循環(huán)，在第一次密碼錯(cuò)誤，再次輸入密碼后，系統(tǒng)仍然提示錯(cuò)誤；t34,t35重復(fù)執(zhí)行了兩次，所以導(dǎo)致了變遷t38無法正常執(zhí)行，虛線框s37,t37表示的的庫所和變遷不可見，t34,t35,t34,t35用紅色虛線框進(jìn)行標(biāo)注。如圖5所示：

圖5 某自動售票機(jī)Petri網(wǎng)檢測模型

4 結(jié) 語

基于工作流網(wǎng)系統(tǒng)中可行跡的執(zhí)行，根據(jù)變遷對之間的minimalk-successorrelations，對比源過程模型網(wǎng)系統(tǒng)，檢測并診斷變化變遷的位置，通過比對，給出存在變化變遷的網(wǎng)系統(tǒng)。未來關(guān)于系統(tǒng)變化的檢測和診斷仍有很多問題需要研究，例如如何高效地對系統(tǒng)變化進(jìn)行定位并改進(jìn)，如何降低變化所帶來的影響等。

參考文獻(xiàn):

[1] Pourmasoumi A, Kahani M, Bagheri E. Mining Variable Fragments From Process Event logs[J]. Information Systems Frontiers, 2016:1-21.

[2] Weidlich M, Mendling J, Weske M. Efficient Consistency Measurement Based on Behavioral Profiles of Process Models[J]. Software Engineering IEEE Transactions on, 2010, 37(3):410-429.

[3] Weber B, Rinderle S, Reichert M. Change Patterns and Change Support Features in Process-Aware Information Systems[J]. Data & Knowledge Engineering, 2008, 66(3):438-466.

[4] Weidlich M, Polyvyanyy A, Desai N, et al. Process Compliance Measurement Based on Behavioural Profiles[J]. Information Systems, 2011, 36(7):1009-1025.

[5] WEN LIJIE.Study on Process Mining Algorithm Based on WF Net[D].BeiJing: Tsinghua University.2007.

[6] Georg Grossmann, Shamila Mafazi, Wolfgang Mayer, et al. Change Propagation and Conflict Resolution for the Co-Evolution of Business Processes[J]. International Journal of Cooperative Information Systems, 2015, 24(01):33-40.

[7] Jensen M T. Improving Robustness and Flexibility of Tardiness and Total Flow-time job shops using robustness measures[J]. Applied Soft Computing, 2001, 1(1):35-52.

[8] Gupta C, Singh Y, Chauhan D S. A Dynamic Approach to Estimate Change Impact using Type of Change Propagation[J]. Journal of Information Processing Systems, 2010, 6(4):597-608.

[9] Kunze M, Weidlich M, Weske M. Querying process models by behavior inclusion[M]. Springer-Verlag New York, Inc. 2015.

[10] Küster J M,Gerth C,Forster A,et al.Detecting and Resolving Process Model Differences in the Absence of a Change log[C].Proceedings of the 6th International Conference on Business Process Management,Springer - Verlag,2008: 244 -260.