吉宏安，馬 野，李雪紅

(海軍大連艦艇學(xué)院，遼寧 大連 116018)

0 引言

工作流的提出起源于生產(chǎn)和辦公的自動(dòng)化領(lǐng)域［1-2］，主要是通過(guò)對(duì)具有固定程序的生產(chǎn)活動(dòng)進(jìn)行分解、排序形成工作流，按步執(zhí)行，達(dá)到提高工作效率、降低生產(chǎn)成本、提高競(jìng)爭(zhēng)力的目的。工作流的出現(xiàn)大大提高了生產(chǎn)效率，但同樣也暴露出任務(wù)流程傳遞不暢、工作遺漏、不利于監(jiān)管等問(wèn)題。

在20 世紀(jì)80 年代中期計(jì)算機(jī)控制就引入了工作流的概念，目前多Agent 的工作流技術(shù)是研究的熱點(diǎn)，主要包括:基于Web 的工作流、分布式的工作流以及多Agent 技術(shù)的工作流［3-7］。但是實(shí)際運(yùn)用中仍存在以下難點(diǎn)問(wèn)題:

1)流程固定僵化，難以對(duì)分支流程進(jìn)行整體控制，存在分支流程進(jìn)展不協(xié)調(diào)，資源利用率不高的問(wèn)題;

2)流程中聚合節(jié)點(diǎn)同步失調(diào)以及死鎖［8］的問(wèn)題，解決方法繁瑣;

3)多任務(wù)并發(fā)執(zhí)行時(shí)，數(shù)據(jù)沖突不同步問(wèn)題［9-11］。

基于時(shí)間序列的多Agent 工作流模型是在多Agent 技術(shù)的基礎(chǔ)上進(jìn)行的改進(jìn)。通過(guò)把樹(shù)狀的工作流結(jié)構(gòu)進(jìn)行整體優(yōu)化，形成以時(shí)間順序排列的任務(wù)序列，解決分支流程單獨(dú)執(zhí)行難以控制協(xié)同的問(wèn)題;開(kāi)辟多任務(wù)進(jìn)程池，將優(yōu)化后的執(zhí)行序列推送到進(jìn)程池，由主Agent 控制進(jìn)程池同步或異步執(zhí)行，實(shí)現(xiàn)工作流中“與”、“或”的基本操作，從而避免聚合節(jié)點(diǎn)出現(xiàn)懸掛節(jié)點(diǎn)、同步失調(diào)以及死鎖的問(wèn)題;在解決數(shù)據(jù)沖突的問(wèn)題時(shí)，模型引入時(shí)間戳的并發(fā)控制技術(shù)，與傳統(tǒng)的多線(xiàn)程數(shù)據(jù)并發(fā)處理技術(shù)相比，該技術(shù)無(wú)需設(shè)置鎖，能夠避免產(chǎn)生死鎖的問(wèn)題而且易于實(shí)現(xiàn)，在一定程度上解決了并發(fā)沖突的問(wèn)題，保持了數(shù)據(jù)的完整性和一致性。

1 總體設(shè)計(jì)

建立基于時(shí)間序列的多Agent 工作流管理系統(tǒng)模型，有3 個(gè)關(guān)鍵性的問(wèn)題需要解決:

1)如何將樹(shù)狀的流程結(jié)構(gòu)轉(zhuǎn)換為按時(shí)間順序排列的任務(wù)序列;

2)如何通過(guò)進(jìn)程池同步或異步地執(zhí)行實(shí)現(xiàn)對(duì)工作流中“與”、“或”的基本操作;

3)如何利用時(shí)間戳技術(shù)解決多任務(wù)數(shù)據(jù)訪(fǎng)問(wèn)不同步的問(wèn)題。

圖1 基于時(shí)間序列的多Agent 工作流模型

圖1 所示為本文設(shè)計(jì)的基于時(shí)間序列的多Agent工作流管理系統(tǒng)模型，模型由用戶(hù)層、工作流的調(diào)度層和執(zhí)行層構(gòu)成。

該模型的核心是:主Agent 模塊、ILOG Agent 模塊和任務(wù)進(jìn)程池，結(jié)合這3 個(gè)模塊:

1)采用基于ILOG Agent 的流程優(yōu)化方案，由ILOG Agent 接收從主Agent 傳遞進(jìn)來(lái)的樹(shù)狀流程結(jié)構(gòu)和約束條件，通過(guò)ILOG 業(yè)務(wù)規(guī)則組件進(jìn)行優(yōu)化處理并輸出規(guī)劃方案［12］，解決將樹(shù)狀流程結(jié)構(gòu)轉(zhuǎn)換為時(shí)間順序排列的任務(wù)序列的問(wèn)題。

2)采用基于主Agent 控制的任務(wù)執(zhí)行方案，由任務(wù)進(jìn)程池向主Agent 反饋上一任務(wù)的執(zhí)行情況，主Agent 根據(jù)反饋進(jìn)行下一任務(wù)的條件判斷后，向任務(wù)進(jìn)程池發(fā)送0/1 指令，控制任務(wù)進(jìn)程的推進(jìn)或停止，實(shí)現(xiàn)了同步、異步的操作。若同步執(zhí)行則為“與”操作，若異步執(zhí)行則為“或”操作。

3)采用基于時(shí)間戳的并發(fā)控制技術(shù)，由主Agent控制時(shí)間戳的發(fā)放，執(zhí)行任務(wù)的Agent 憑時(shí)間戳訪(fǎng)問(wèn)數(shù)據(jù)項(xiàng)，并與數(shù)據(jù)項(xiàng)的時(shí)間戳進(jìn)行比較，只有符合條件的才可獲取數(shù)據(jù)，從而解決了數(shù)據(jù)訪(fǎng)問(wèn)不同步的問(wèn)題。

2 技術(shù)實(shí)現(xiàn)

2.1 基于ILOG Agent 的流程優(yōu)化方案

對(duì)流程結(jié)構(gòu)進(jìn)行處理，其難點(diǎn)在于分支任務(wù)的處理。并行分支相互之間的任務(wù)沒(méi)有優(yōu)先等級(jí)的約束關(guān)系，因此在按時(shí)間序列排列時(shí)，需要有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)對(duì)其進(jìn)行整體規(guī)劃。該規(guī)劃可按流程最優(yōu)化的方式進(jìn)行。流程優(yōu)化的原則是:不改變流程中任務(wù)優(yōu)先等級(jí)關(guān)系的前提下，通過(guò)合理調(diào)配部分可支配任務(wù)的執(zhí)行時(shí)間，使得流程對(duì)資源的消耗最小、耗時(shí)最短。

ILOG 組件是目前世界上最優(yōu)秀的約束規(guī)劃組件之一，用ILOG 業(yè)務(wù)規(guī)則對(duì)工作流程優(yōu)化，能夠根據(jù)約束規(guī)則(OSR)，通過(guò)合理調(diào)配資源、優(yōu)化計(jì)劃，達(dá)到所需的計(jì)劃目標(biāo)［13］。

圖2 某大型裝備模型

優(yōu)化過(guò)程的輸入是由用戶(hù)提供的一組約束條件和需要求解的若干問(wèn)題，經(jīng)過(guò)ILOG 組件的求解，最后得出優(yōu)化的任務(wù)序列?，F(xiàn)要拆除某大型裝備的部件M，任務(wù)由頂層部件A 開(kāi)始逐層拆除，如圖2 所示，其拆除工作的流程圖如圖3 所示，為方便描述各拆除任務(wù)用Ti表示。

圖3 部件拆除基本流程圖

上述的樹(shù)狀結(jié)構(gòu)流程，可用約束規(guī)則表述如下:

1)該拆除工作共有11 項(xiàng)拆除任務(wù)，分別為T(mén)1，T2，…，T11;

2)每個(gè)任務(wù)的執(zhí)行時(shí)間有限制，如拆除部件A的規(guī)定時(shí)間為7 天;

3)各拆除任務(wù)具有一定的先后次序，優(yōu)先等級(jí)不能改變，如優(yōu)先等級(jí)T1＞T2＞T5，T3＞T8，T4＞T10;

4)同一分支下的拆除任務(wù)必須在上一級(jí)別的拆除任務(wù)完成后才可以開(kāi)始新的拆除任務(wù);

5)需要求解的問(wèn)題是如何安排拆除次序，使得拆除過(guò)程耗時(shí)最短。

運(yùn)用ILOG 組件進(jìn)行優(yōu)化，是以約束規(guī)則作為輸入條件，結(jié)合ILOG 提供的API 接口類(lèi)用ILOG 語(yǔ)言將約束規(guī)則表述為可執(zhí)行的程序代碼，然后利用ILOG 內(nèi)置的算法進(jìn)行求解。求解時(shí)上述約束規(guī)則將轉(zhuǎn)變?yōu)橐粋€(gè)布爾表達(dá)式，它的值依賴(lài)于約束是否滿(mǎn)足，若不違反約束，表達(dá)式值為真;若不滿(mǎn)足約束，則值為假。執(zhí)行時(shí)，采用樹(shù)形搜索策略，快速檢索，并能夠控制檢索的指令和深度，一旦發(fā)現(xiàn)可行解決辦法，繼續(xù)改進(jìn)搜索方式，運(yùn)用約束傳播和縮小范圍的約束法則進(jìn)一步收縮檢索空間，從而達(dá)到求解的目的［14-15］。

經(jīng)ILOG 組件求解后，可得到圖4 所示的部件拆除規(guī)劃圖，可以看出優(yōu)化后T4并沒(méi)有和T2，T3一起執(zhí)行。

圖4 部件拆除時(shí)間序列圖

2.2 基于主Agent 控制的任務(wù)執(zhí)行方案

圖5 示意圖

在多Agent 工作流模型里，可以把各活動(dòng)環(huán)節(jié)視為具備任務(wù)執(zhí)行能力的Agent 個(gè)體，在主Agent 的控制和管理下開(kāi)展各任務(wù)活動(dòng)。如圖5 所示，以部件拆除流程中的T3分支為例，主要解決如何通過(guò)主Agent的控制任務(wù)進(jìn)程池，實(shí)現(xiàn)工作流程中的順序、與分支、或分支、與聚合、或聚合這幾種基本的流程操作。

主Agent 要實(shí)現(xiàn)對(duì)流程的全面控制，必須對(duì)控制信息有全面的掌握。圖4 中經(jīng)過(guò)優(yōu)化后的任務(wù)序列圖，并不能直接為主Agent 所用，還需進(jìn)一步解析和提取，最后形成表1 所示的流程計(jì)劃表。對(duì)歷史任務(wù)主Agent 將不再解析提取，而從圖6 所示的任務(wù)庫(kù)中直接使用。

表1 基于時(shí)間序列的任務(wù)流程計(jì)劃表

任務(wù)開(kāi)始執(zhí)行后，主Agent 根據(jù)時(shí)間表序列開(kāi)辟相應(yīng)的任務(wù)進(jìn)程池，并通知Agent 類(lèi)庫(kù)派出對(duì)應(yīng)類(lèi)別的Agent 個(gè)體進(jìn)駐進(jìn)程池。圖7 中T8和T9由于其觸發(fā)時(shí)間相同，但觸發(fā)條件不同，因此為其建立2 個(gè)任務(wù)進(jìn)程池。

圖6 任務(wù)庫(kù)設(shè)計(jì)

圖7 任務(wù)進(jìn)程池執(zhí)行示意圖

以圖5 中T3分支節(jié)點(diǎn)和T11聚合節(jié)點(diǎn)為例，其流程操作過(guò)程如下:

1)若T3為或分支，即可假設(shè)設(shè)置T8觸發(fā)條件為a3==1，T9的觸發(fā)條件為a3==0。當(dāng)T3任務(wù)執(zhí)行完成后，將向主Agent 發(fā)送圖8 所示數(shù)據(jù)包。主Agent獲取后，根據(jù)流程計(jì)劃表判斷出只有T8符合執(zhí)行條件，則向T8所在進(jìn)程池1 發(fā)送執(zhí)行指令，進(jìn)程池2 處于等待狀態(tài)。

圖8 通信數(shù)據(jù)包

2)同理，若T3為與分支，即可設(shè)置T8、T9的觸發(fā)條件為a3==1;若T3執(zhí)行結(jié)果為a3=0，則T8、T9都不執(zhí)行，此時(shí)主Agent 將T8、T9的執(zhí)行結(jié)果設(shè)置為a8=0，a9=0;結(jié)束時(shí)刻設(shè)置為當(dāng)前時(shí)刻，并繼續(xù)向下執(zhí)行，可避免死鎖問(wèn)題的發(fā)生。

3)若T11為與聚合，則設(shè)置T11的觸發(fā)條件為a8==1＆＆a9==1。

4)若T11為或聚合，則設(shè)置T11的觸發(fā)條件為a8==1||a9==1。

2.3 基于時(shí)間戳的并發(fā)控制方案

當(dāng)多個(gè)Agent 同時(shí)對(duì)數(shù)據(jù)庫(kù)進(jìn)行訪(fǎng)問(wèn)時(shí)，若不進(jìn)行有效控制，將導(dǎo)致數(shù)據(jù)更新不及時(shí)等問(wèn)題。在本模型中，采用的是基于時(shí)間戳的并發(fā)控制技術(shù)［16-17］。時(shí)間戳定義為唯一的，隨時(shí)間增長(zhǎng)的整數(shù)。其原理是:

1)當(dāng)各Agent 需要訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)時(shí)，向主Agent 發(fā)出申請(qǐng)，主Agent 根據(jù)時(shí)間的先后順序，向每個(gè)申請(qǐng)者發(fā)送一個(gè)時(shí)間戳T，各Agent 用戶(hù)根據(jù)時(shí)間戳訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)。

2)對(duì)數(shù)據(jù)項(xiàng)同樣設(shè)計(jì)時(shí)間戳，當(dāng)數(shù)據(jù)項(xiàng)發(fā)生讀操作時(shí)，記錄時(shí)間戳為Rtm，當(dāng)數(shù)據(jù)項(xiàng)為寫(xiě)操作時(shí)記錄為Wtm。

3)當(dāng)Agent 根據(jù)時(shí)間戳T 訪(fǎng)問(wèn)某數(shù)據(jù)項(xiàng)，進(jìn)行讀操作時(shí)，若T ＜Wtm，則說(shuō)明由申請(qǐng)到執(zhí)行期間，數(shù)據(jù)項(xiàng)發(fā)生了變化，那么數(shù)據(jù)項(xiàng)則拒絕該Agent 訪(fǎng)問(wèn)，其必須重新向主Agent 發(fā)送訪(fǎng)問(wèn)申請(qǐng)，獲取新的時(shí)間戳;若T ＞W(wǎng)tm，則允許數(shù)據(jù)訪(fǎng)問(wèn)，并更新Wtm=T。

4)當(dāng)Agent 根據(jù)時(shí)間戳T 訪(fǎng)問(wèn)某數(shù)據(jù)項(xiàng)，進(jìn)行寫(xiě)操作時(shí)，若T ＜Wtm 或T ＜Rtm 數(shù)據(jù)項(xiàng)都將拒絕該Agent 訪(fǎng)問(wèn);若T ＞W(wǎng)tm 或T ＞Rtm 都將允許進(jìn)行數(shù)據(jù)訪(fǎng)問(wèn)，并更新對(duì)應(yīng)的Wtm=T 或Rtm=T。

3 應(yīng)用與結(jié)論

圖9 為開(kāi)發(fā)的某裝備業(yè)務(wù)信息系統(tǒng)的任務(wù)流控制界面，主要功能是實(shí)現(xiàn)對(duì)裝備維修保障過(guò)程的流程化和規(guī)范化管理。

圖9 某裝備業(yè)務(wù)信息系統(tǒng)中工作流控制界面

其總體業(yè)務(wù)流程是以調(diào)度室為中心形成的閉環(huán)信息流。大致流程如下:調(diào)度室根據(jù)任務(wù)計(jì)劃，向系統(tǒng)下達(dá)任務(wù)指令;系統(tǒng)獲取指令后，自動(dòng)檢索任務(wù)庫(kù)中相應(yīng)的任務(wù)信息，生成業(yè)務(wù)工作流，并向各業(yè)務(wù)終端推送任務(wù)準(zhǔn)備信息。任務(wù)執(zhí)行時(shí)，由系統(tǒng)根據(jù)任務(wù)進(jìn)展自動(dòng)向業(yè)務(wù)終端發(fā)送執(zhí)行指令，推動(dòng)任務(wù)執(zhí)行，直到工作流終止。

該系統(tǒng)是運(yùn)用Java 的編程語(yǔ)言和SQL 數(shù)據(jù)庫(kù)技術(shù)進(jìn)行開(kāi)發(fā)的一款Web 應(yīng)用程序。開(kāi)發(fā)過(guò)程中，曾發(fā)現(xiàn)以下問(wèn)題:

1)維修時(shí)，系統(tǒng)從多個(gè)地方調(diào)度同一種器件，不能按照“先到先得”的原理，繼續(xù)開(kāi)展下一步工作，而是等待所有調(diào)度的完成才能執(zhí)行，不符合實(shí)際要求。

2)若超過(guò)了規(guī)定的調(diào)度時(shí)間，所有調(diào)度工作均未完成時(shí)，系統(tǒng)始終保持等待狀態(tài)，無(wú)法執(zhí)行下一步流程。

3)多用戶(hù)訪(fǎng)問(wèn)同一數(shù)據(jù)項(xiàng)時(shí)，存在數(shù)據(jù)更新不及時(shí)，導(dǎo)致各用戶(hù)獲取的數(shù)據(jù)不一致的情況。

分析研究發(fā)現(xiàn)，采用基于時(shí)間序列的多Agent 工作流模型，以主Agent 控制多進(jìn)程同步、異步推進(jìn)的方式，較好地解決了發(fā)現(xiàn)的問(wèn)題。

實(shí)際應(yīng)用表明，系統(tǒng)運(yùn)行穩(wěn)定，工作流傳遞準(zhǔn)確，達(dá)到了預(yù)期的目的。

4 結(jié)束語(yǔ)

本文在基于多Agent 進(jìn)行工作流系統(tǒng)建模的基礎(chǔ)上，加入了ILOG 組件的約束規(guī)劃處理，形成了優(yōu)化后的以時(shí)間為序列的任務(wù)列表，并根據(jù)列表將細(xì)化的Agent 個(gè)體投入到開(kāi)辟的進(jìn)程池中，由進(jìn)程池按時(shí)間序列驅(qū)動(dòng)任務(wù)的向前發(fā)展，最終實(shí)現(xiàn)了工作流的完整執(zhí)行。該模型為解決工作流分支和聚合引起的同步失調(diào)和死鎖問(wèn)題提供了新思路，對(duì)實(shí)際應(yīng)用具有一定的意義。

［1］徐超.基于Petri 網(wǎng)的工作流技術(shù)研究與應(yīng)用［D］.大連:大連理工大學(xué)，2004.

［2］錢(qián)維平，王堅(jiān).基于WF 狀態(tài)機(jī)工作流的日常工作管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.機(jī)電產(chǎn)品開(kāi)發(fā)與創(chuàng)新，2015，28(1):81-83.

［3］杜玉姣.多Agent 工作流模型的研究與實(shí)現(xiàn)［D］.西安:西安電子科技大學(xué)，2014.

［4］侯堃.基于A(yíng)gent 的工作流管理系統(tǒng)研究［D］.北京:北京工商大學(xué)，2012.

［5］劉磊.基于Petri 網(wǎng)的工作流模型化方法及其應(yīng)用研究［D］.杭州:浙江理工大學(xué)，2013.

［6］王媛媛.基于A(yíng)gent 的工作流管理系統(tǒng)研究與實(shí)現(xiàn)［D］.成都:西南交通大學(xué)，2006.

［7］武凌，王浩.基于多Agent 的工作流管理系統(tǒng)的建模與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25(8):199-202.

［8］任曉軍.一種基于多Agent 的工作流引擎及其動(dòng)態(tài)性研究［D］.青島:山東科技大學(xué)，2010.

［9］朱孟成.工作流中的并發(fā)控制技術(shù)研究［J］.電子技術(shù)與軟件工程，2015，4(4):164.

［10］柴學(xué)智，曹健.面向云計(jì)算的工作流技術(shù)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33(1):90-95.

［11］劉少偉，孔令梅，任開(kāi)軍，等.云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(11):2121-2130.

［12］姜英新，孫吉貴.約束滿(mǎn)足問(wèn)題求解及ILOG SOLVER系統(tǒng)簡(jiǎn)介［J］.吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2002，40(1):53-60.

［13］史忠植.高級(jí)人工智能［M］.第3 版.北京:科學(xué)出版社，2011:99-104.

［14］ILOG.ILOG Solver User's Manual Version 2.0［M］.Gentilly，1995.

［15］楊達(dá)玲，楊建軍，白宏斌.基于ILOG SOLVER 的Job-Shop調(diào)度算法實(shí)現(xiàn)［J］.現(xiàn)代制造工程，2006(5):22-24.

［16］顧耀林，賀曉燕.時(shí)間戳順序在分布式并發(fā)控制中的應(yīng)用［J］.信息技術(shù)，2001(11):8-9.

［17］謝應(yīng)科，王建東，祝超，等.網(wǎng)絡(luò)測(cè)量中高精度時(shí)間戳研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)研究與發(fā)展，2010，47(12):2049-2058.