面向目標(biāo)的遷移工作流遷移路徑的尋址與優(yōu)化

摘 要：給出了一種面向目標(biāo)的遷移工作流遷移路徑的尋址與優(yōu)化算法，研究了工作流的執(zhí)行主體——遷移實例在動態(tài)環(huán)境中完成給定目標(biāo)的遷移路徑問題。借助ANDOR圖理論，給出了算法的基本框架。

關(guān)鍵詞：遷移工作流；面向目標(biāo)；遷移實例；優(yōu)化算法

中圖分類號：TP301 文獻標(biāo)志碼：A

文章編號：1001-3695(2008)09-2623-02

Path search and optimization in goaloriented migrating workflow

ZHANG Jingmei1，2，ZENG Guangzhou1，HAN Fangxi1

 (1.School of Computer Science Technology， Shandong University， Jinan 250061， China；2.School of Information Management， Shandong Economic University，Jinan 250014， China)

Abstract:This paper introduced an optimal algorithm of a heuristic path search scheme for goaloriented migrating workflow. The migrating path of migrating instance——the kernel executive part in the workflow was intensively investigated under a dynamic environment in order to find an effective way complementing the given goal. With the help of ANDOR graph theory，it illustrated the preliminary algorithm.

Key words:migrating workflow; goaloriented; migrating instance; optimization

工作流管理系統(tǒng)（WfMS）作為計算機支持的協(xié)同工作（CSCW）研究的一個重要方向，已經(jīng)成為了計算機、自動化、管理、先進制造等多學(xué)科領(lǐng)域關(guān)注與研究的熱點之一^[1~4]。近年來，研究者把軟件agent，特別是移動agent引入到了工作流中，提出了基于移動計算范型的遷移工作流的概念模型^[5，6]。按照WfMC規(guī)范^[7]，工作流系統(tǒng)的執(zhí)行依賴于工作流的建模，而建模主要是基于一種面向過程的軟件工程思想，為移動agent編寫面向過程的工作流說明并驅(qū)動其工作。這種面向過程的工作流解決方案僅限于研究結(jié)構(gòu)良好的、先驗知識完備的業(yè)務(wù)流程，但系統(tǒng)可用性較低，agent在動態(tài)環(huán)境中缺乏理性思維和行為。

曾廣周工作組在遷移工作流系統(tǒng)框架的基礎(chǔ)上研究面向目標(biāo)的遷移工作流方法（GOMW）。該方法能夠充分體現(xiàn)智能理性agent對動態(tài)環(huán)境的自適應(yīng)性，由目標(biāo)出發(fā)，帶著不完備先驗知識的初始狀態(tài)出發(fā)，不斷感知當(dāng)前環(huán)境的變化，動態(tài)調(diào)整遷移工作流中業(yè)務(wù)流程的執(zhí)行者遷移實例的思維和行為，完成服務(wù)發(fā)現(xiàn)、服務(wù)選擇、遷移決策，逐步優(yōu)化目標(biāo)求解路徑直至尋找到最優(yōu)路徑繼而完成整個工作流的執(zhí)行，實現(xiàn)既定目標(biāo)。本文針對面向目標(biāo)的遷移工作流在動態(tài)環(huán)境中如何選擇最優(yōu)遷移路徑問題，基于反向推理的思想提出了優(yōu)化方案，并給出了相應(yīng)的算法。

1 理論背景

遷移工作流主要理論基礎(chǔ)和發(fā)展進程可以歸納為遷移工作流系統(tǒng)框架的提出、傳統(tǒng)遷移工作流實現(xiàn)方案、自適應(yīng)遷移工作流實現(xiàn)方案。

1.1 系統(tǒng)框架

遷移工作流系統(tǒng)基本原理框架如圖1所示，它由一個遷移工作流管理機和若干個已經(jīng)建立友好信任關(guān)系的局域網(wǎng)組成。遷移工作流管理機執(zhí)行工作流引擎，每個局域網(wǎng)均包含一個停靠站服務(wù)器和若干個與其相連的工作機網(wǎng)絡(luò)。遷移實例是業(yè)務(wù)過程的執(zhí)行主體，基于移動agent范型設(shè)計。工作位置代表一個部門或一個組織機構(gòu)，是遷移實例的運行場所，它由停靠站和工作機網(wǎng)絡(luò)兩部分組成。停靠站地址對所有遷移實例和所有其他停靠站而言都是位置透明的，與停靠站相連的工作機網(wǎng)絡(luò)為遷移實例提供工作流服務(wù)和資源服務(wù)。遷移工作流管理引擎負(fù)責(zé)創(chuàng)建和組織工作流，它既可以設(shè)置在一個龍頭企業(yè)（這時整個遷移工作流系統(tǒng)以C/S模式構(gòu)建），對整個遷移工作流管理系統(tǒng)進行集中控制；也可以分布在任一個工作位置上（這時整個遷移工作流系統(tǒng)以P2P模式構(gòu)建）。這樣，在任何一個工作位置都可以產(chǎn)生需求、確定目標(biāo)、創(chuàng)建和殺死遷移實例、組織和發(fā)起工作流，監(jiān)控遷移實例的執(zhí)行情況，更加靈活地完成既定目標(biāo)。

1.2 傳統(tǒng)實現(xiàn)方案 —— 面向過程的遷移工作流

按照WfMC規(guī)范，工作流系統(tǒng)的執(zhí)行依賴于工作流建模。建模的基本方法是自頂向下的過程分解，即將整個業(yè)務(wù)過程分解為若干個ANDOR關(guān)聯(lián)的子過程，再把每個子過程分解為若干個ANDOR關(guān)聯(lián)的活動/任務(wù)。現(xiàn)有的基于WfMC中應(yīng)用移動agent技術(shù)的研究都遵守了上述規(guī)范，即為移動agent編寫面向過程的工作流說明并驅(qū)動其工作。自頂向下的過程分解法要求工作流系統(tǒng)設(shè)計者具有關(guān)于業(yè)務(wù)過程組成、分解和執(zhí)行的全部先驗知識，適用于具有明顯結(jié)構(gòu)化特征的業(yè)務(wù)流程^[7]。對于許多非結(jié)構(gòu)化的業(yè)務(wù)過程來說，要求工作流設(shè)計者預(yù)先知道嚴(yán)格的流程邏輯是不現(xiàn)實的，另一方面，預(yù)先定義的嚴(yán)格步驟和控制邏輯也使得移動agent失去靈活性，難以應(yīng)對工作流例外。

1.3 自適應(yīng)遷移工作流實現(xiàn)方案——面向目標(biāo)的遷移工作流

基于上述對面向過程的遷移工作流存在的問題的認(rèn)識，本文將使用面向目標(biāo)的遷移工作流研究方法對遷移工作流的遷移路徑選擇進行研究。面向目標(biāo)的遷移工作流不再要求工作流設(shè)計者事先具有完備和精確的業(yè)務(wù)過程知識。另外，從工作流用戶的角度來說，說明工作流目標(biāo)往往要比描述工作流過程容易得多。

面向目標(biāo)的工作流中，任一工作位置都可以作為用戶產(chǎn)生需求，說明工作流目標(biāo)；然后采用目標(biāo)驅(qū)動方式使遷移實例工作，通過遷移實例在工作流服務(wù)空間上的啟發(fā)式搜索，完成面向目標(biāo)的服務(wù)發(fā)現(xiàn)、評價、選擇、遷移和利用。

2 遷移路徑的尋址與優(yōu)化

下面討論面向目標(biāo)遷移工作流如何在其服務(wù)空間上進行啟發(fā)式搜索，如何確立遷移實例的遷移路徑以及如何優(yōu)化遷移路徑。

目標(biāo)驅(qū)動的啟發(fā)式搜索方案采用ANDOR圖的反向推理思想^[8，9]。ANDOR圖的反向推理可以看做是一個問題規(guī)約過程，即在問題求解過程中，將一個大目標(biāo)變換成若干個子目標(biāo)，子目標(biāo)再繼續(xù)分解，直至可以直接求解。這里使用的ANDOR圖與在面向過程的遷移工作流中使用自頂向下的過程分解方案將整個業(yè)務(wù)過程分解為若干個ANDOR關(guān)聯(lián)的子過程方案的不同之處在于：前者在某個工作位置上確定目標(biāo)，產(chǎn)生遷移實例后進行目標(biāo)分解，然后搜索下一個遷移工作位置，并在遷移后的工作位置上執(zhí)行遷移實例，進行目標(biāo)的再分解，直至整個遷移實例利用反向推理過程完成整個工作流目標(biāo)；后者則是在創(chuàng)建遷移實例的工作位置上完成任務(wù)的分解工作，并在啟動工作流之前，遷移實例清楚地知道步驟的轉(zhuǎn)移邏輯以及每一步所需要的資源和服務(wù)等，僅將到哪里做和如何做的問題留給遷移過程。

假設(shè)某一工作位置產(chǎn)生需求（服務(wù)需求和資源需求），確定總體任務(wù)Ａ，若任務(wù)A在當(dāng)前工作位置全部可解，則在當(dāng)前位置運行后終止；否則，將任務(wù)A分解為單獨求解任務(wù)B，或者同時求解任務(wù)C與D（B OR C AND D）。這時，根據(jù)文獻[5]提出的遷移尋址搜索算法，得到子任務(wù)B、C、D的工作位置。根據(jù)各工作位置反饋的運算處理各子任務(wù)的運行成本和傳輸成本，計算其綜合費用。若計算得到求解B的費用低于并行求解C和 D的費用，則決定遷移的下一個工作位置，提出遷移請求，等待遷出；遷移到達下一個工作位置后，將當(dāng)前問題B作為新的目標(biāo)，循環(huán)執(zhí)行上述過程后又將目標(biāo)分解為問題E或者F與G。若決定遷移到下一個位置求解子任務(wù)E則原遷移實例等待遷出；若決定求解子任務(wù)F與G，則需要根據(jù)實際情況決定順序求解還是并行求解。若需要并行求解，還要由當(dāng)前遷移實例派生出兩個新的遷移實例，兩個遷移實例分別提出遷移請求，等待遷出。重復(fù)上述過程直至一條完整的遷移路徑在某一個工作位置上（葉節(jié)點）的問題全部可解或找不到其他工作位置可解為止，遷移實例就地被殺死或回傳至被創(chuàng)建或被派生的工作位置。

關(guān)于上述遷移路徑尋址過程的說明：

a)從宏觀上看，遷移路徑的尋址過程可以看做是在一棵遷移樹中找到一條從根節(jié)點到葉子節(jié)點的遷移路徑。

b)遷移路徑上各工作位置的遷移關(guān)系包括串行、并行、反饋三種。

在具有合作關(guān)系的各獨立機構(gòu)組成的工作流域中，各個工作位置都可以按照意愿對自己提供的服務(wù)進行增加、修改和刪除，如變更服務(wù)類型、服務(wù)數(shù)量、服務(wù)方式或服務(wù)時間等。所以上面提出的面向目標(biāo)的遷移工作流遷移路徑的尋址過程存在如下兩個問題：

a)當(dāng)遷移工作流到達某一工作位置時出現(xiàn)了服務(wù)例外、遷移實例壞死、任務(wù)變?yōu)椴豢山猓惴▽⒃诖斯ぷ魑恢蒙蠝簦皇亲赃m應(yīng)地重新選擇其他路徑繼續(xù)執(zhí)行工作流。

b)由于動態(tài)環(huán)境的變化，工作流在遷移、執(zhí)行過程中繼續(xù)沿原遷移路徑求解目標(biāo)的費用大于選擇其他路徑的費用時，遷移工作流不會自適應(yīng)地改變遷移路徑。

鑒于存在的問題，在之前研究的基礎(chǔ)上提出一種在面向目標(biāo)的遷移工作流中尋找與優(yōu)化遷移路徑的算法。

{ begin

a）At a certain workplace of task node A， the demand emerges. 

if (the task is solvable， then execute it) return

b)Create migrating instance upon fulfillment of solvable part of the task.

c）repeat

(a)\"and/or\" decomposition of the task into n th subtask groups. Arclinked \"and\" task as one group.

(b)Find the subtask workplaces or leaf nodes according to path search algorithm.

(c)Engine at the workplace makes poll request on the cost and remainder cost to complete a subtask at a given interval. Carry out the comprehensive cost， i.e.， operation cost plus migrating cost. (d)Wait to migrate instance to the minimumcost position.In case parallel subtask then create several migrating instances.

(e)Migrate instance or instances.

(f)Complete the localsolvable part and reckon the remainder costk and feed cost back at engine’s poll request.

if (the comprehensive cost of subtask < costk) then goto d)

until (task is totally solvable) or (the total cost >=threshold)

d)Kill the migrating instance or feed it back to where it is created. return }

end procedure

3 結(jié)束語

本文針對面向目標(biāo)的遷移工作流提出了一種遷移路徑的尋址與優(yōu)化方案，它給出了遷移實例的遷移路徑確定方法；遷移路徑的尋址經(jīng)過ANDOR圖優(yōu)化，可以有效地處理壞死遷移實例，提高遷移實例的執(zhí)行效率。該優(yōu)化算法為面向目標(biāo)遷移工作流的廣泛應(yīng)用提供了優(yōu)化方案，將面向目標(biāo)遷移工作流的概念向?qū)嵱梅较蛲七M了一步。

參考文獻：

［1］DIAS P， VIEIRA P， RITOSILVA A.Dynamic evolution in workflow management systems[C]//Proc of the 14th International Workshop on Database and Expert Systems Applications.Washington DC:IEEE Computer Society，2003:254-260.

［2］BOBEK A， BOHN H，GOLATOWSKI F，et al.Enabling workflow in UPnP networks[C]//Proc of the 3rd IEEE International Conference on Industrial Informatics.2005: 166171.

［3］YANG Mingkui，LIANG Hongbing，XU Bin.SWfMS:a servicebased workflow management system in grid environment[C]//Proc of the 19th International Conference on Advanced Information Networking and Applications.2005:293-297.

［4］LI Hongchen， SHI Meilin.Application of agents in workflow management system[C]//Proc of the 5th AsiaPacific Conference on Communications and the 4th Optoelectronics and Communications Conference.1999:10681072.

［5］曾廣周， 黨妍.基于移動計算范型的遷移工作流研究[J].計算機學(xué)報，2002，26(10):13431349.

［6］QIU Jian，WANG Cong，HE Yongchun.Research on application of intelligent agents in the workflow management system[C]//Proc of IEEE International Conference on Networking， Sensing and Control.2005:827-830.

［7］WfMC.Workflow terminology glossary version 3.0， WfMCTC1011[R]. 1999. 

［8］PEAR J.Heuristics:intelligent search strategies for computer problem solving[M].Massachusetts: AddisonWesley，1984.

［9］HANSEN E A，ZILBERSTEIN S. LAO*:a heuristic search algorithm that finds solutions with loops[J].Artificial Intelligence，2001，129(1-2):35-62.