一種基于歷史路徑的工作流實(shí)例遷移方法

摘要:工作流變更中一個(gè)重要問題就是工作流實(shí)例的遷移問題。該文根據(jù)工作流實(shí)例執(zhí)行的歷史路徑和節(jié)點(diǎn)路由表提出了一個(gè)新的遷移策略，減少了一些不必要的回滾和遷移，并對(duì)每個(gè)節(jié)點(diǎn)都確定了相應(yīng)了遷移動(dòng)作。

關(guān)鍵字:遷移;歷史路徑;動(dòng)態(tài)動(dòng)作流

中圖分類號(hào):TP311文獻(xiàn)表示碼:A文章編號(hào):1009-3044(2009)33-9597-02

Work Flow Instance Migration Approach Based on History Route

JING Chao， HOU Xiu-ping， HAO Shuai

(College of Computer and Engineering， Changchun University of Technology， Changchun 130012， China)

Abstract: One of the most crucial issues in workflow alteration is the transfer of workflow instance. This paper puts forward a brand-new transfer strategy based on historical path and node-route table of workflow instance which avoids unnecessary rollback and transfer while confirms corresponding transfer activities.

Key words: transfer; history route; dynamic workflow

隨著工作流技術(shù)實(shí)際應(yīng)用的不斷深入，人們對(duì)其提出了更多的功能要求。在現(xiàn)實(shí)需求中，一個(gè)工作流在運(yùn)行中很有可能發(fā)生變化，這就要求工作流模型有自適應(yīng)變化的能力，并且正在運(yùn)行的工作流實(shí)例往往需要盡早地按照新的工作流過程模型繼續(xù)執(zhí)行，并保持已做工作的最大化[1]。在研究工作流動(dòng)態(tài)性的過程中，研究人員先后提出過許多方法來解決相關(guān)問題。文獻(xiàn)[2]提出了變更區(qū)域的概念，但沒有給出變更區(qū)域的自動(dòng)識(shí)別方法。文獻(xiàn)[3]基于工作流網(wǎng)的概念，提出了自動(dòng)計(jì)算變更區(qū)域的方法，保證了動(dòng)態(tài)變更區(qū)域以外的實(shí)例能夠正確遷移，然而這是一個(gè)充分不必要條件，計(jì)算過程也過于復(fù)雜。文獻(xiàn)[4]提出了繼承保留規(guī)則的方法，然而這是一個(gè)預(yù)防性的問題處理方法，僅適合與變更前后的工作流模型存在父類與子類繼承關(guān)系的情況。本文引入了執(zhí)行路徑來判斷工作流實(shí)例的執(zhí)行狀態(tài)，提出了一種基于狀態(tài)的工作流實(shí)例遷移檢測和調(diào)整算法，且由該算法自動(dòng)生成的遷移規(guī)則總能保證實(shí)例的回退工作盡可能少。

1 工作流模型定義

定義1 工作流模型定義，為一個(gè)三元組W=(ID，X，F(xiàn))，其中:ID為工作流版本號(hào)標(biāo)識(shí)。X為節(jié)點(diǎn)集合。F=N×N為控制流關(guān)系。

定義2 節(jié)點(diǎn)定義，為一個(gè)三元組N=(ID ，Name，ExecuteCode)，其中id為節(jié)點(diǎn)的序號(hào)，Name為活動(dòng)節(jié)點(diǎn)的名字。ExecuteCode為當(dāng)前節(jié)點(diǎn)要執(zhí)行的方法。

定義3 工作流實(shí)例定義，為一個(gè)三元組Istance=(ID，W，H)，其中id為工作流實(shí)例唯一標(biāo)識(shí)，W為實(shí)例運(yùn)行的工作流模型，H表示當(dāng)前工作流實(shí)例已經(jīng)執(zhí)行過的活動(dòng)節(jié)點(diǎn)的集合。

2 遷移算法設(shè)計(jì)

2.1 相關(guān)規(guī)則定義

定義4 偏序關(guān)系定義，設(shè)集合X為工作流活動(dòng)圖上節(jié)點(diǎn)集合。關(guān)系R為集合X上任務(wù)節(jié)點(diǎn)執(zhí)行的先后順序，用\"<\"表示。即R(N1，N2)=N1

定義5 節(jié)點(diǎn)操作方法定義，對(duì)于工作流模型中的節(jié)點(diǎn)N0，定義如下操作函數(shù)。

Succ(N0，W) = {N1| N0< N1，并且對(duì)于任意的節(jié)點(diǎn)N2∈X，(N0< N2∩N2< N1) = 1，N0，N1，N2∈X.其中X為工作流W中的節(jié)點(diǎn)集合}，求出節(jié)點(diǎn)X的直接后繼節(jié)點(diǎn)集合。

Prec (N0，W) = { N1| N1< N0，并且對(duì)于任意的節(jié)點(diǎn)N2∈X， (N1< N2∩N2< N0) = 1， N0，N1，N2∈X.其中X為工作流W中的節(jié)點(diǎn)集合.}，求得節(jié)點(diǎn)X的直接前驅(qū)節(jié)點(diǎn)集合。

Succ*( N0，W) = { N1| N0< N1， N0，N1∈X.其中X為工作流W中的節(jié)點(diǎn)集合}，求出節(jié)點(diǎn)X的所有后繼節(jié)點(diǎn)集合。

Prec*(N0，W) = { N1| N1

定義6 工作流實(shí)例的操作方法

RoolBack(W0，N0，id)，在工作流模型W0 中將當(dāng)前工作流實(shí)例回滾到活動(dòng)節(jié)點(diǎn)N0，并修改相應(yīng)信息(如H)。

Transfer(id，W)，把工作流實(shí)例遷移到工作流模型W上運(yùn)行。首先對(duì)當(dāng)前的工作流實(shí)例持久化，把運(yùn)行期的數(shù)據(jù)存儲(chǔ)到磁盤中，然后在新的模型中實(shí)例化一個(gè)新的工作流作流實(shí)例，反序列化原實(shí)例的數(shù)據(jù)，并把相關(guān)數(shù)據(jù)信息給新實(shí)例賦值。

Start(id)，開始執(zhí)行工作流實(shí)例

Suspend(id)，掛起當(dāng)前工作流實(shí)例

Resume(id)，重新啟動(dòng)掛起的工作流實(shí)例

2.2 工作流實(shí)例遷移算法

我們目前把所有工作的流的活動(dòng)節(jié)點(diǎn)都定義為原子節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可以是幾個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)組，該文暫時(shí)不考慮一個(gè)節(jié)點(diǎn)組修改的情況。

當(dāng)工作流模型發(fā)生變更時(shí)，該文基于歷史路徑提出了一種工作流實(shí)例遷移算法，算法思想為:根據(jù)原工作流模型和新工作流模型的節(jié)點(diǎn)集合數(shù)量來判斷新的工作流模型是增加節(jié)點(diǎn)，刪除節(jié)點(diǎn)還是替換節(jié)點(diǎn)。然后根據(jù)當(dāng)前工作流實(shí)例執(zhí)行的歷史路徑信息H，得到當(dāng)前工作流實(shí)例正在執(zhí)行的節(jié)點(diǎn)，判斷如果模型的更改對(duì)當(dāng)前實(shí)例沒有影響，當(dāng)前實(shí)例不用遷移，還在原來的模型上運(yùn)行即可。如果模型的更改對(duì)當(dāng)前實(shí)例有影響，則當(dāng)前實(shí)例根據(jù)不同的情況修改信息后，遷移到新的工作流模型上運(yùn)行。

用W0(0，X0，F(xiàn)0)和W1(1，X1，F(xiàn)1)分別表示新舊工作流過程模型，Istance(0，W0，H)表示工作流當(dāng)前實(shí)例。定義兩個(gè)節(jié)點(diǎn)變量Node Nc，Nc為變化的活動(dòng)節(jié)點(diǎn)，Nn = H.Last; Nn 為工作流實(shí)例正在執(zhí)行的當(dāng)前活動(dòng)節(jié)點(diǎn)。算法實(shí)現(xiàn)如下

如果Count(X0)>Count(X1)||(Count(X0)=Count(X1) F0 != F1) //刪除節(jié)點(diǎn)或替換節(jié)點(diǎn)

Nc = X0 – (X1∩X0);

Case : Nn ∈ Prec*( Nc) // 當(dāng)Nn 是Nc的前驅(qū)節(jié)點(diǎn)

Do{ Suspend(id);Transfer(id，W1);Resume(id)}

Case : Nn ∈ Succ*( Nc) // 當(dāng)Nn 是Nc的后繼節(jié)點(diǎn)

If(Nc∩H ==Nul ) Go Ahead;//工作流模型變化對(duì)當(dāng)前實(shí)例沒有影響，繼續(xù)運(yùn)行

Else:{ Node Pre = Prec( Nc) ∩ H//在執(zhí)行路徑上找到Nc 的前驅(qū)節(jié)點(diǎn)

Do{ Suspend(id);RoolBack(W0，Pre， id); Transfer(id，W1);Resume(id)}

Default: Go Ahead ;

如果Count(X0)

Nc = X1- X0;

Case : Nn ∈ Prec*( Nc) // 當(dāng)Nn 是Nc的前驅(qū)節(jié)點(diǎn)

Do{ Suspend(id);Transfer(id，W1); Resume(id); }

Case : Nn ∈ Succ*( Nc) // 當(dāng)Nn 是Nc的后繼節(jié)點(diǎn)

Node Pre = Prec( Nc) ∩ H//在執(zhí)行路徑上找到Nc 的前驅(qū)節(jié)點(diǎn)

If(Pre ==Null ) Go Ahead;

Else : Do {Suspend(id); RoolBack(W0，Pre， id);Transfer(id，W1);Resume(id);}

其它: Go Ahead // 算法結(jié)束

3 應(yīng)用實(shí)例

對(duì)于一個(gè)手機(jī)生產(chǎn)的流程，手機(jī)出來的產(chǎn)品有兩種，一種是普通手機(jī)，這種手機(jī)只有普通的操作系統(tǒng)，支持手機(jī)的正常操作功能。第二種手機(jī)添加了電子書閱讀功能。這兩種手機(jī)產(chǎn)品都是合理的。則整個(gè)手機(jī)生產(chǎn)的過程處理流程簡化為工作流模型如圖1所示。其中N1.裝配機(jī)器外殼N2.裝配操作系統(tǒng)N3.增加電子書軟件(可選裝配)N4.組裝機(jī)器。

由于市場需求的需要，客戶需要有手機(jī)同時(shí)具備電子書和Mp3功能，只具有單一閱讀電子書功能的產(chǎn)品將停產(chǎn)。則流程中增加了Mp3播放一個(gè)流程項(xiàng)。新的過程流程變更為工作流模型如圖2所示，其中N1.裝配機(jī)器外殼N2.裝配操作系統(tǒng)N3.增加電子書軟件(可選裝配)N4.增加Mp3軟件(可選裝配)N5.組裝機(jī)器。

原工作流模型和新的工作流模型分別表示為W0(0， X0，F(xiàn)0) ，W1(0，X1，F(xiàn)1)

根據(jù)Count(X1) >Count(X0)，可以判斷出新的工作流模型是在原模型上增加節(jié)點(diǎn)。可以得到變化節(jié)點(diǎn)Nc = N4(增加Mp3軟件)，變化節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)集合Prec*(Nc)={N1，N2，N3}。變化節(jié)點(diǎn)的后繼結(jié)點(diǎn)結(jié)合Succ*(Nc)={N5}，對(duì)于實(shí)例Instance(0，W0，H)中的H信息，找到H中的最后一個(gè)活動(dòng)節(jié)點(diǎn)N0， N0即為當(dāng)前工作流實(shí)例正在執(zhí)行的活動(dòng)節(jié)點(diǎn)。

1) 當(dāng)H={啟動(dòng)，N1}時(shí)，N0=N，實(shí)例不用遷移，繼續(xù)運(yùn)行。

2) 當(dāng)H={啟動(dòng)，N1，N2}時(shí)，N0=N2，實(shí)例不用遷移，繼續(xù)運(yùn)行。

3) 當(dāng)H={啟動(dòng)，N1，N2，N3}時(shí)，N0=N3，實(shí)例不用遷移，繼續(xù)運(yùn)行。

4) 當(dāng)H={啟動(dòng)，N1，N2，N5}時(shí)，N0=N5，模型變更對(duì)工作流實(shí)例沒有影響，實(shí)例不用遷移，繼續(xù)運(yùn)行。實(shí)例結(jié)束后運(yùn)行的路徑為{啟動(dòng)，N1，N2，N5，結(jié)束}

5) 當(dāng)H={啟動(dòng)，N1，N2，N3，N5}時(shí)，N0=N5，模型更改對(duì)工作流實(shí)例有影響，先將運(yùn)行中的工作流實(shí)例回滾到N3節(jié)點(diǎn)，遷移到新的工作流模型中再繼續(xù)執(zhí)行。這時(shí)實(shí)例結(jié)束后運(yùn)行的路徑為{啟動(dòng)，N1，N2，N3，N4，N5，結(jié)束}

該文基于工作流實(shí)例歷史路徑的信息提出來一個(gè)工作流實(shí)例的遷移方法，該方法可以有效的避免不必要的回滾和遷移，提高了工作流實(shí)例的運(yùn)行效率。該文的研究僅僅把工作流改變節(jié)點(diǎn)抽象為原子節(jié)點(diǎn)來研究的，對(duì)于節(jié)點(diǎn)組的遷移算法情況，將是該文以后研究的方向和重點(diǎn)。

參考文獻(xiàn):

[1] 魏登萍，姜新文.工作流演進(jìn)變化中遷移策略的自動(dòng)生成[J].計(jì)算機(jī)應(yīng)用，2006，26(4):995-997.

[2] ELLISC，KEDDARAK，ROZENBERGG.Dynamic change within workflow systems[C]//Proceedings of ACM Conference on Organizational Computing Systems.New York:ACM Press 1995:10-21.

[3] VAN NDE RAALST W M P.Exterminating the dynamic change bug: a concrete approach to support workflow change[J].Information Systems Frontiers，2001，3(3):297-317.

[4] VAN NDE RAALST W M P，BASTENT T.Inheritance of workflow: an approach to tackling problems related to changes[J].The oretical Computer Science，2002，270(1/2):125-203.