崔 璐，毋 濤

(西安工程大學 計算機科學學院，陜西 西安 710600)

0 引 言

工作流就是業(yè)務(wù)流程的自動化[1]，在此過程中，多個參與者之間按照一定的過程規(guī)則自動進行文檔、信息或任務(wù)傳遞，以實現(xiàn)預期的業(yè)務(wù)目標，這也是過程、事件、資源的有機結(jié)合。隨著工作流技術(shù)的發(fā)展，工作流管理系統(tǒng)被應用于各種領(lǐng)域，工作流管理系統(tǒng)的性能也成為人們關(guān)注的焦點。不同的任務(wù)分配策略對工作流管理系統(tǒng)的性能有很大的影響，因此需要制定良好的任務(wù)分配策略，選擇工作流引擎調(diào)度系統(tǒng)中合適的資源來操作任務(wù)。工作流系統(tǒng)中的資源，根據(jù)適用領(lǐng)域的區(qū)別，可分為設(shè)備資源、人力資源、應用程序或者網(wǎng)絡(luò)資源等[2]，其中人力資源一般指擁有一定經(jīng)驗或?qū)I(yè)知識的任務(wù)執(zhí)行者。實際中隨著業(yè)務(wù)流程規(guī)模的增大，往往存在多個流程實例同時到達的情景，當工作流系統(tǒng)頻繁地把任務(wù)分配給能力值或經(jīng)驗值高的執(zhí)行者，此類執(zhí)行者任務(wù)列表中待處理任務(wù)會不斷增多，負載過重，反而不能及時處理完所分配的任務(wù)。且執(zhí)行時間相近但重要性不同的任務(wù)，對執(zhí)行者的負載影響也不同。當任務(wù)列表中有多個重要任務(wù)時，執(zhí)行者通常會優(yōu)先執(zhí)行重要任務(wù)而無暇顧及不太重要的任務(wù)。這些都是業(yè)務(wù)流程執(zhí)行中的重要影響因素，當工作流整體負載不均衡時，會導致工作流系統(tǒng)響應時間過長、資源利用率不高、工作流環(huán)境穩(wěn)定性遭到破壞等問題。

文獻[3]提出了一種新的以優(yōu)化執(zhí)行時間和處理成本為目標的工作流調(diào)度算法，旨在隱式評估適合VM執(zhí)行的實例范圍，以避免會導致截止時間違規(guī)的過高投入。文獻[4]利用三角模糊數(shù)將執(zhí)行者的專業(yè)技能、成員協(xié)作度、任務(wù)完成質(zhì)量這類定義模糊的影響因素進行量化處理，再對各個影響因素分配合適的權(quán)重因子，最后選取綜合分數(shù)高的候選者分配任務(wù)。但這些研究都沒有考慮在工作流的實際應用中，當實例密集到達時執(zhí)行者負載對流程的影響。文獻[5]給出結(jié)合協(xié)作相容與負載均衡的多目標聯(lián)合優(yōu)化任務(wù)分配算法，提高流程執(zhí)行效率，卻缺少任務(wù)重要性對任務(wù)負載的影響分析。文獻[6]從任務(wù)和用戶的屬性出發(fā)，提出一種兼顧用戶經(jīng)驗值和任務(wù)負載的任務(wù)分配算法，并針對任務(wù)的重要程度給任務(wù)負載加影響因子，但是執(zhí)行者根據(jù)主觀定義任務(wù)的重要程度，不能客觀反映任務(wù)重要性差異與流程執(zhí)行時間長短的關(guān)系。文獻[7]針對網(wǎng)格環(huán)境下工作流調(diào)度問題，提出了一種基于遺傳算法和蟻群算法相結(jié)合的混合機制，優(yōu)化模型的最大完成時間和成本。將蟻群這種自適應算法應用于工作流調(diào)度中，提升流程的實用性與效率。綜上所述，為了提高流程的性能，該文提出基于蟻群算法的兼顧關(guān)鍵任務(wù)和工作負載的任務(wù)分配算法，不僅考慮了執(zhí)行者的當前工作負載，還考慮了關(guān)鍵任務(wù)重要性對工作負載的影響。

1 任務(wù)分配策略與模型

1.1 主要思想

任務(wù)分配的目標，是根據(jù)執(zhí)行者們的預測負載所在分區(qū)和任務(wù)列表中待執(zhí)行的關(guān)鍵任務(wù)數(shù)量，來選擇負載相對較小的執(zhí)行者執(zhí)行任務(wù)，以平衡實例密集時執(zhí)行者的負載壓力，同時讓關(guān)鍵任務(wù)減少等待時間，盡可能并行。該文先通過執(zhí)行者的負載狀況，將執(zhí)行者動態(tài)分成輕、中、重三個負載分區(qū)，然后將輕負載分區(qū)中的執(zhí)行者作為候選集合，然后從集合中選擇待執(zhí)行關(guān)鍵任務(wù)最少的執(zhí)行者，對其進行任務(wù)分配。

1.2 關(guān)鍵任務(wù)的量化

1.2.1 關(guān)鍵任務(wù)確定

工作流的應用中，企業(yè)通常關(guān)心的是：(1)在實現(xiàn)業(yè)務(wù)預期目標的前提下，完成整個工作流最少需要多少時間？(2)哪些任務(wù)是影響工作流進度的關(guān)鍵？

可以采用帶權(quán)值的有向無環(huán)圖DAG來表示工作流[8]，由于流程中存在并行路徑，所以完成流程的最短時間是從開始點到完成點的持續(xù)時間最長路徑的長度。有向無環(huán)圖中，路徑長度最長的路徑叫做關(guān)鍵路徑[9]。關(guān)鍵路徑上的活動叫做關(guān)鍵活動，因此可以依據(jù)有向無環(huán)圖的關(guān)鍵活動，得到工作流中影響流程進度的關(guān)鍵任務(wù)。

以圖1所示的簡單的領(lǐng)料流程為例，求取關(guān)鍵任務(wù)。

圖1 簡單的領(lǐng)料流程

圖2 圖1流程圖對應的有向無環(huán)圖

這樣就把問題轉(zhuǎn)換為求圖2所示帶權(quán)值的有向無環(huán)圖G的關(guān)鍵路徑CP(critical path)。當關(guān)鍵任務(wù)執(zhí)行時間延長或縮短時，關(guān)鍵路徑的執(zhí)行時間即流程的總執(zhí)行時間也相應延長或縮短，所以關(guān)鍵任務(wù)的分配方式與執(zhí)行效率對提高流程效率起到了重要作用。在計算關(guān)鍵路徑時，可以參考流程日志中的歷史流程數(shù)據(jù)獲得每個任務(wù)的平均執(zhí)行時間作為標準。

1.2.2 關(guān)鍵任務(wù)量化

(1)

其中，MAX(Ecp(ui))是當前執(zhí)行者中關(guān)鍵任務(wù)量最大值，MIN(Ecp(ui))是當前執(zhí)行者中關(guān)鍵任務(wù)量最小值。Ecp(ui)值越大，執(zhí)行者ui的相對關(guān)鍵任務(wù)量越大，在執(zhí)行者負載相近時，獲得任務(wù)的概率越小。

1.3 負載量化

任務(wù)執(zhí)行者的當前工作負載是完成自己工作列表中所有任務(wù)所需要的時間。分配任務(wù)時該文假設(shè)同一任務(wù)的可選執(zhí)行者執(zhí)行本任務(wù)的能力相似，即執(zhí)行同樣任務(wù)，不同執(zhí)行者的時間相同。則可以定義執(zhí)行者ui的當前工作負載為Wcur(ui)：

(2)

其中，TAk是任務(wù)執(zhí)行者ui的當前任務(wù)列表集合，列表中每個任務(wù)Tk的數(shù)量為nk，完成時間為ωk。設(shè)執(zhí)行者ui的當前工作負載為Wcur(ui)，若現(xiàn)將任務(wù)Tk分配給ui，則ui的預測負載Wpred(ui)為：

Wpred(ui)=Wcur(ui)+ωk

(3)

(4)

據(jù)此，設(shè)共有n個執(zhí)行者，完成工作流中所有任務(wù)的總負載Wtotal為：

(5)

(6)

依據(jù)該文的主要思想，結(jié)合關(guān)鍵任務(wù)與負載的分配模型為：

(7)

即流程中任務(wù)分配的執(zhí)行者相對關(guān)鍵任務(wù)量與總負載都盡可能少。

2 基于蟻群算法的任務(wù)分配策略

蟻群算法(ant colony system)是一種用來尋找優(yōu)化路徑的概率型算法,由Marco Dorigo于1992年在他的博士論文中提出[10]。算法模擬螞蟻的覓食行為，在螞蟻尋找食物的過程中不斷釋放被稱為信息素的物質(zhì)，螞蟻的棲息地到食物源的路徑越短，該路徑上通過的螞蟻的數(shù)量就越多，信息素就越強，從而指引螞蟻的行為[11]。即蟻群之間通過信息素的濃度變化進行信息交流和相互協(xié)作，濃度越高的路徑選擇的概率越大[12]?；诖嗽撐奶岢鲆环N基于ACO的任務(wù)分配策略，除此之外還使用關(guān)鍵路徑算法從歷史流程數(shù)據(jù)中確定關(guān)鍵任務(wù)節(jié)點集合，在此基礎(chǔ)上考慮負載均衡通過聯(lián)合優(yōu)化策略給出初始解并計算流程總負載。

2.1 基于關(guān)鍵路徑的流程關(guān)鍵任務(wù)確定

將工作流進行形式化描述后得到帶全權(quán)值的有向無環(huán)圖G，先通過拓撲排序得到流程任務(wù)的拓撲序列topoSort[]，基于此與歷史流程數(shù)據(jù)確定流程的關(guān)鍵路徑，從而得到流程關(guān)鍵任務(wù)集合CT。

2.2 聯(lián)合優(yōu)化策略

目標是在保持執(zhí)行者負載相對平衡的基礎(chǔ)上，選擇相對關(guān)鍵任務(wù)量較小的執(zhí)行者，以減少關(guān)鍵任務(wù)堆積對執(zhí)行者與流程的影響。

CTLB算法的執(zhí)行流程為：

(3)循環(huán)(1)和(2)直至所有流程中所有任務(wù)分配完成。

2.3 ACO-CT算法

根據(jù)蟻群算法的基本原理，可以了解到算法主要依靠啟發(fā)式信息構(gòu)建和信息素濃度更新來求取可行解。本節(jié)主要分為三部分，包括算法初始化、狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則[13]。

2.3.1 算法初始化

利用ACO-CT算法進行任務(wù)分配的目的是尋找Timemin時的解。解的形式是一個執(zhí)行者編號組成的數(shù)組，每個執(zhí)行者對應流程中一個事件的分配結(jié)果，且這個結(jié)果在考慮了關(guān)鍵任務(wù)影響與負載均衡的同時保證流程執(zhí)行時間盡可能短。

初始化時，數(shù)組各元素為0，調(diào)用CTLB得到TAS為一組初始解，計算得到WL_Total。若經(jīng)過一次迭代后，得到的總負載優(yōu)于WL_Total，則更新總負載與執(zhí)行序列解。任務(wù)Tk與執(zhí)行者ui之間的信息素矩陣τ初始化為：

(8)

其中，n為工作流中執(zhí)行者的數(shù)量。并采用自適應蟻群算法MMAS對基本蟻群算法的改進，將τ(k,i)限定在[τmin,τmax]之間，以避免算法陷入局部最優(yōu)。

2.3.2 狀態(tài)轉(zhuǎn)移規(guī)則

算法采用概率選擇的方法構(gòu)建可行解，將起始任務(wù)的執(zhí)行者隨機分配給不同的螞蟻，完成該任務(wù)后，螞蟻按照狀態(tài)轉(zhuǎn)移概率對下一個任務(wù)選擇合適的執(zhí)行者，不斷重復這個過程直至執(zhí)行完所有任務(wù)。狀態(tài)轉(zhuǎn)移概率主要由信息素濃度和啟發(fā)式信息確定[14]，而本算法啟發(fā)式信息的構(gòu)建目標是引導螞蟻往列表中關(guān)鍵任務(wù)較少的執(zhí)行者移動，即相對關(guān)鍵任務(wù)量越少，執(zhí)行者被選擇的概率越大。啟發(fā)式信息構(gòu)建如下：

(9)

則算法的狀態(tài)轉(zhuǎn)移規(guī)則為：

(10)

表示螞蟻從可選執(zhí)行者列表UAk中選擇執(zhí)行者ui的概率。其中α是信息啟發(fā)式因子，β是期望啟發(fā)式因子，利用因子控制信息素和啟發(fā)式信息的相對影響程度。

2.3.3 信息素更新規(guī)則

對于信息素更新規(guī)則，選擇改進后的全局更新規(guī)則，即不再對所有螞蟻進行更新，而是對每次迭代中最優(yōu)的螞蟻進行更新[15]。當一次迭代中每個螞蟻都完成工作流的任務(wù)分配，并得到一個執(zhí)行者序列與流程總負載，選擇最優(yōu)的流程總負載與初始解的流程總負載比較，對較優(yōu)的那個信息素進行更新，更新規(guī)則如下：

(11)

其中，ρ是信息揮發(fā)因子，則1-ρ是殘留因子，WL_Totalgb是全局最優(yōu)螞蟻的工作流總負載，TASgb是最優(yōu)螞蟻的任務(wù)分配的執(zhí)行者序列。

2.3.4 ACO-CT算法執(zhí)行流程

基于以上三部分，ACO-CT的算法執(zhí)行流程可概述為:

(1)流程初始化，先建立關(guān)鍵路徑模型，得到流程的關(guān)鍵任務(wù)合集，并在此過程中得到每個任務(wù)的前驅(qū)、后繼任務(wù)集合。

(2)在步驟(1)的基礎(chǔ)上，通過CTLB聯(lián)合優(yōu)化算法得到一組初始解暫時作為最優(yōu)解TASgb，并計算初始解的流程總負載暫時作為最優(yōu)解WL_Totalgb。

(3)初始化任務(wù)與執(zhí)行者的信息素矩陣、算法迭代次數(shù)、蟻群規(guī)模、信息揮發(fā)因子、信息啟發(fā)式因子和期望啟發(fā)式因子。

(4)在一次迭代中，每只螞蟻根據(jù)公式(10)的狀態(tài)轉(zhuǎn)移概率選擇任務(wù)的執(zhí)行者，將執(zhí)行者序列保存下來，計算每個螞蟻的流程總負載，并與WL_Totalgb的值相比較，大于則舍去，小于則更新WL_Totalgb，并將該解的執(zhí)行者序列賦值給TASgb，成為新的最優(yōu)解。直到一次迭代完成。

(5)對TASgb使用公式(11)更新信息素。

(6)重復步驟(4)和(5)，直至迭代全部完成。

ACO-CT算法偽代碼如下：

輸入：Tesk set:T={{Tk}}; Executor set:U={ui};

輸出：Ant path with optimal execution sequence TASgb

(1)Initialization ant number :Ants; Number of iterations:Max_Itera,

(2)Parameters:Rho,Alpha,Beta

(3)Workflow mode and Critical task set {CT}:according to Get_TopoSort and Get_CTasks

(4)Use CTLB algorithm to generate a set of initial solutions as theTASgb,and calculate the total workload WL_Totalgbaccording to CAL_WLT

(5)FOR eachpher(k,i)=pInitaccording to formula (8)

(6)ENDFOR

(7)FOR m=1 TO Max_Itera DO

(8)FOR t=1 TO Ants DO

(9)FOR eachTk∈TDO

(10)TASt(k)=0; /*Assignment of ant t to taskTk

(11)ENDFOR

(12)FOR eachTk∈TDO

(13)IFTkis the first task in workflow

(14)Randomly chooseui∈UAkas the executor for ant t

(15)TASt(k)=ui

(16)ELSE choose an executorui∈UAkaccording to formula (10)

(17)TASt(k)=ui

(18)ENDIF

(19)ENDFOR

(20)ENDFOR

(21)FOR t=1 TO Ants DO

(22)CalculateWL_Totaltaccording to algorithm CAL_WLT

(23)IF(WL_Totalt

(24)Update the optimal ant to t

(25)TASgb←TASt

(26)WL_Totalgb←WL_Totalt

(27)ENDIF

(28)ENDFOR

(29)FOR eachTk∈TDO

(30)Update pheromone matrixpher(k,i)using the TASgbaccording to formula(11)

(31)ENDFOR

(32)ENDFOR

3 仿真實驗

本節(jié)通過仿真實驗檢驗ACO-CT算法解決任務(wù)分配問題的可行性。實驗從3方面評估算法的性能：(1)不同實例規(guī)模下3種任務(wù)分配算法的完成時間；(2)3種任務(wù)分配算法下任務(wù)執(zhí)行者的負載均衡情況；(3)ACO-CT算法的收斂性。仿真采用圖1簡單領(lǐng)料流程的工作流模型。根據(jù)歷史流程數(shù)據(jù)得到各個任務(wù)的處理時間，如圖3所示。

圖3 領(lǐng)料流程各任務(wù)時間

歷史流程數(shù)據(jù)通過算法可以得出此流程的關(guān)鍵任務(wù)集CT={T1,T2,T4,T6,T7,T8,T9,T10,T11}，實驗中，設(shè)置負載區(qū)間閾值εL、εM分別為0.34和0.67。在工作流實例不同到達概率的情況下，分別用ACO-CT、HEFT、Round_Robin算法進行仿真實驗。對每一個實例到達率，對每種算法進行50次仿真，并用同樣的實例在不同算法上仿真，實驗結(jié)果采用50次仿真的平均值進行分析。

結(jié)合領(lǐng)料的實例，平均完成時間比較如圖4所示。

圖4 不同實例規(guī)模下的工作流完成時間

從圖4可以看出，ACO-CT算法在實例規(guī)模不斷增加的情況下結(jié)果都比較好，尤其在實例規(guī)模較大時表現(xiàn)更好，這是因為ACO-CT兼顧負載均衡與關(guān)鍵任務(wù)量，一定程度上縮短了關(guān)鍵任務(wù)過多時對執(zhí)行者的影響。HEFT僅僅考慮了期望任務(wù)負載，忽略了多實例同時到達時負載不均的影響，但在實際的工作中，一般工作流系統(tǒng)應用于企業(yè)時實例規(guī)模都會較大，所以ACO-CT考慮更加全面。

現(xiàn)分析3種任務(wù)分配算法下任務(wù)執(zhí)行者的負載情況。實驗采用流程實例規(guī)模為8時，各個執(zhí)行者的任務(wù)負載情況。

圖5 實例規(guī)模為8時各個執(zhí)行者任務(wù)負載

從圖5可以看出，執(zhí)行者在多流程實例且每個執(zhí)行者都可以執(zhí)行多個任務(wù)的情況下，Round_Robin算法執(zhí)行者任務(wù)負載差距較為明顯，而ACO-CT與HEFT算法可以使執(zhí)行者負載相對平衡。HEFT算法的思路很簡單,就是將所有任務(wù)都分配能夠使它最早完成的執(zhí)行者，也可以一定程度上讓負載相對均衡，然而ACO-CT算法因為提前對可選執(zhí)行者進行負載分區(qū)，并在一定分區(qū)內(nèi)繼續(xù)考慮關(guān)鍵任務(wù)量的影響，所以不僅考慮到了執(zhí)行者之間的負載均衡，還減少了整體完成時間。

由于ACO-CT算法是一個啟發(fā)式算法，所以對算法的收斂性進行檢驗。圖6是在實例規(guī)模為10時的最優(yōu)序列完成時間。隨著迭代次數(shù)的增加，ACO-CT算法的最優(yōu)序列的完成時間逐漸減小，且本算法引入了MMAS的思想進行改進，避免了過早收斂的現(xiàn)象。

圖6 ACO-CT算法收斂性

從圖6可以看出，在迭代160次左右時，算法就收斂了，就收斂速度來看，不存在過早收斂的現(xiàn)象。

4 結(jié)束語

該文研究了基于蟻群的工作流負載平衡任務(wù)分配算法，通過對工作流中執(zhí)行者關(guān)鍵任務(wù)量對流程性能的影響以及執(zhí)行者之間負載均衡進行建模，采用蟻群算法實現(xiàn)模型，并通過實驗驗證了算法的有效性。然而，文中的關(guān)鍵任務(wù)的確認是基于歷史流程數(shù)據(jù)的，忽略了實際運行過程中任務(wù)執(zhí)行時間的動態(tài)變化，下一步將考慮動態(tài)關(guān)鍵路徑的研究；此外，對于帶環(huán)的工作流，需要進一步處理，例如等效替換等，將帶環(huán)的工作流抽象成一個任務(wù)，具體方案還需進一步研究。