面向目標的遷移工作流遷移路徑的尋址與優化

摘 要：給出了一種面向目標的遷移工作流遷移路徑的尋址與優化算法，研究了工作流的執行主體——遷移實例在動態環境中完成給定目標的遷移路徑問題。借助ANDOR圖理論，給出了算法的基本框架。

關鍵詞：遷移工作流；面向目標；遷移實例；優化算法

中圖分類號：TP301 文獻標志碼：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

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

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

1 理論背景

遷移工作流主要理論基礎和發展進程可以歸納為遷移工作流系統框架的提出、傳統遷移工作流實現方案、自適應遷移工作流實現方案。

1.1 系統框架

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

1.2 傳統實現方案 —— 面向過程的遷移工作流

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

1.3 自適應遷移工作流實現方案——面向目標的遷移工作流

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

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

2 遷移路徑的尋址與優化

下面討論面向目標遷移工作流如何在其服務空間上進行啟發式搜索，如何確立遷移實例的遷移路徑以及如何優化遷移路徑。

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

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

關于上述遷移路徑尋址過程的說明：

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

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

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

a)當遷移工作流到達某一工作位置時出現了服務例外、遷移實例壞死、任務變為不可解，算法將在此工作位置上滯留，而不是自適應地重新選擇其他路徑繼續執行工作流。

b)由于動態環境的變化，工作流在遷移、執行過程中繼續沿原遷移路徑求解目標的費用大于選擇其他路徑的費用時，遷移工作流不會自適應地改變遷移路徑。

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

{ 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 結束語

本文針對面向目標的遷移工作流提出了一種遷移路徑的尋址與優化方案，它給出了遷移實例的遷移路徑確定方法；遷移路徑的尋址經過ANDOR圖優化，可以有效地處理壞死遷移實例，提高遷移實例的執行效率。該優化算法為面向目標遷移工作流的廣泛應用提供了優化方案，將面向目標遷移工作流的概念向實用方向推進了一步。

參考文獻：

［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].計算機學報，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.