基于蟻群的工作流任務分配算法研究

崔 璐，毋 濤

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

0 引 言

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

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

1 任務分配策略與模型

1.1 主要思想

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

1.2 關鍵任務的量化

1.2.1 關鍵任務確定

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

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

以圖1所示的簡單的領料流程為例，求取關鍵任務。

圖1 簡單的領料流程

圖2 圖1流程圖對應的有向無環圖

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

1.2.2 關鍵任務量化

(1)

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

1.3 負載量化

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

(2)

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

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

(3)

(4)

據此，設共有n個執行者，完成工作流中所有任務的總負載Wtotal為：

(5)

(6)

依據該文的主要思想，結合關鍵任務與負載的分配模型為：

(7)

即流程中任務分配的執行者相對關鍵任務量與總負載都盡可能少。

2 基于蟻群算法的任務分配策略

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

2.1 基于關鍵路徑的流程關鍵任務確定

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

2.2 聯合優化策略

目標是在保持執行者負載相對平衡的基礎上，選擇相對關鍵任務量較小的執行者，以減少關鍵任務堆積對執行者與流程的影響。

CTLB算法的執行流程為：

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

2.3 ACO-CT算法

根據蟻群算法的基本原理，可以了解到算法主要依靠啟發式信息構建和信息素濃度更新來求取可行解。本節主要分為三部分，包括算法初始化、狀態轉移規則和信息素更新規則[13]。

2.3.1 算法初始化

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

初始化時，數組各元素為0，調用CTLB得到TAS為一組初始解，計算得到WL_Total。若經過一次迭代后，得到的總負載優于WL_Total，則更新總負載與執行序列解。任務Tk與執行者ui之間的信息素矩陣τ初始化為：

(8)

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

2.3.2 狀態轉移規則

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

(9)

則算法的狀態轉移規則為：

(10)

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

2.3.3 信息素更新規則

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

(11)

其中，ρ是信息揮發因子，則1-ρ是殘留因子，WL_Totalgb是全局最優螞蟻的工作流總負載，TASgb是最優螞蟻的任務分配的執行者序列。

2.3.4 ACO-CT算法執行流程

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

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

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

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

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

(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 仿真實驗

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

圖3 領料流程各任務時間

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

結合領料的實例，平均完成時間比較如圖4所示。

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

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

現分析3種任務分配算法下任務執行者的負載情況。實驗采用流程實例規模為8時，各個執行者的任務負載情況。

圖5 實例規模為8時各個執行者任務負載

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

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

圖6 ACO-CT算法收斂性

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

4 結束語

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