基于協(xié)作相容性的工作流任務(wù)分配優(yōu)化方法

胡海洋 姬朝配 胡 華,2 葛季棟

1(杭州電子科技大學(xué)計算機學(xué)院 杭州 310018)

2(復(fù)雜系統(tǒng)建模與仿真教育部重點實驗室(杭州電子科技大學(xué)) 杭州 310018)

3 (計算機軟件新技術(shù)國家重點實驗室(南京大學(xué)) 南京 210046)

(huhaiyang@hdu.edu.cn)

在工作流調(diào)度中，各任務(wù)由工作流引擎調(diào)度系統(tǒng)中的資源來操作完成.由于不同的任務(wù)分配策略將對工作流管理系統(tǒng)的性能有很大的影響[1]，因此需要制定良好的任務(wù)分配優(yōu)化策略，將各任務(wù)分配給合適的資源.根據(jù)應(yīng)用領(lǐng)域的不同，工作流系統(tǒng)中的資源可以是人力資源、設(shè)備儀器資源、應(yīng)用程序或網(wǎng)絡(luò)資源等.其中人力資源在工作流系統(tǒng)中起著重要的作用，他們一般是指具有特定技能的任務(wù)執(zhí)行者，通過相應(yīng)的角色(role)彼此配合與協(xié)作，在工作流系統(tǒng)中調(diào)度各類計算資源完成任務(wù).在現(xiàn)代企業(yè)中，任務(wù)執(zhí)行者常可承擔(dān)多類角色用于完成多種任務(wù)[2]，其對完成不同類型任務(wù)?？删哂胁煌氖煜こ潭?，并且不同人員之間配合協(xié)作的默契程度也存在著差異.

任務(wù)執(zhí)行者完成任務(wù)的技能熟悉度、彼此間協(xié)作的默契度對整個業(yè)務(wù)過程順利、高效執(zhí)行起著重要作用.然而，現(xiàn)有的任務(wù)分配算法僅考慮候選執(zhí)行者的專業(yè)能力、興趣、經(jīng)驗、負載等，忽略了工作流中任務(wù)交互時執(zhí)行者之間的協(xié)作相容性.這樣的協(xié)作相容性可以定義為：“和其他人的凝聚力、熟悉度，和諧、配合度等[2]”.例如一個典型的醫(yī)療索賠流程(如第2節(jié)中的圖1所示)，幾個任務(wù)以確定的順序分配給幾個角色執(zhí)行.當(dāng)一個角色完成分配的任務(wù)并提交給下一個任務(wù)的執(zhí)行者執(zhí)行時，2個執(zhí)行者之間可能會存在一些交互以詢問和驗證一些信息.在這樣的任務(wù)交互過程中，執(zhí)行者之間的協(xié)作相容性影響著工作的高效性.例如有2個員工甲、乙均可完成某個任務(wù)，并且甲的個人能力強于乙，然而甲對公司里其他員工的配合并不默契，當(dāng)工作流中的任務(wù)需要員工之間進行交互時，甲的整體工作效率可能反而低于乙的整體效率.

此外，在工作流系統(tǒng)實際過程中，由于存在著多個流程實例，并且各實例到達時間有一定的隨機性，候選執(zhí)行者的工作列表中常存在多個等待處理的任務(wù).在此情形下，一個滿負載的執(zhí)行者很難及時完成所分配的工作流任務(wù).由于執(zhí)行者當(dāng)前所有的任務(wù)負載情況將對分配任務(wù)的最后完成時間有著很大的影響，因此工作流系統(tǒng)在分配任務(wù)過程中需考慮到各個任務(wù)執(zhí)行者當(dāng)前的工作負載情況，即盡可能將任務(wù)分配給輕負載(light-loaded)的執(zhí)行者，從而提高整個工作流系統(tǒng)的性能.

現(xiàn)有的一部分研究工作通過將任務(wù)執(zhí)行者的專業(yè)能力、任務(wù)成功率、興趣度、經(jīng)驗等因素轉(zhuǎn)化為模糊數(shù)[3-5]，并對各影響因素分配一個權(quán)重因子，在任務(wù)分配時選擇綜合分數(shù)最高的候選者進行分配，但沒有認識到任務(wù)間存在交互的情形下執(zhí)行者之間協(xié)作的配合度影響.而有些研究盡管考慮了任務(wù)分配時上下文環(huán)境中任務(wù)執(zhí)行者的一些社會關(guān)系、配合度等對任務(wù)執(zhí)行時間的影響[6-9]，然而卻僅局限于連續(xù)的2個任務(wù)之間的配合度，同時也沒有考慮到多實例同時到達的情況下任務(wù)執(zhí)行者工作負載方面的影響.

為了解決以上問題，本文引入了執(zhí)行者間協(xié)作相容性對任務(wù)分配影響的內(nèi)容，通過結(jié)合歷史日志的信息，對執(zhí)行者間的協(xié)作相容性及任務(wù)負載進行了分析計算.在此基礎(chǔ)上，給出了任務(wù)分配問題的優(yōu)化建模，提出了基于協(xié)作相容性與負載均衡的任務(wù)分配算法，提高了整個流程實例的執(zhí)行效率.

1 相關(guān)工作

在工作流調(diào)度中基本上任務(wù)分配策略是基于角色或組織模型[1].它僅僅考慮了資源的角色而沒有區(qū)分自動型任務(wù)和用戶型任務(wù).研究者們通過人的屬性擴展了這一概念，例如文獻[2]基于流程任務(wù)間可能存在的交互，通過一個啟發(fā)式算法，在任務(wù)分配時選擇整個實例中合作協(xié)作相容性之和最大的執(zhí)行者執(zhí)行任務(wù).文獻[3]提出了一種多準(zhǔn)則評估模型算法，根據(jù)候選者的能力、社會關(guān)系和任務(wù)屬性進行任務(wù)分配，但對社會關(guān)系如何影響候選者的能力問題沒有說明.文獻[4]中提出了一種自主工作流任務(wù)分配策略，為任務(wù)分配帶來了更多的自主權(quán).

Fig. 1 A process flow of medical insurance claim圖1 一個醫(yī)療保險索賠流程

文獻[5]在研究任務(wù)分配時考慮了更多因素(如任務(wù)重要性、任務(wù)類型、能力、負載、經(jīng)驗)，并用模糊理論討論了關(guān)于每一因素權(quán)重的大小表示該因素的影響程度;文獻[6-7]證明了基于優(yōu)化社會關(guān)系的任務(wù)團隊組建，如團隊的凝聚力等，將使工作流中的任務(wù)更加高效地執(zhí)行;文獻[8]提出了一種基于社會關(guān)系矩陣處理多實例的任務(wù)分配問題;文獻[9]采用隱Markov建模，通過基于候選者任務(wù)執(zhí)行能力和日志中挖掘的連續(xù)任務(wù)的交互關(guān)系，并通過Viterbi算法解決任務(wù)分配問題;文獻[10]提出了一種基于Q學(xué)習(xí)的任務(wù)分配算法，且在任務(wù)分配時考慮了社會關(guān)系的影響，縮短了實例的平均執(zhí)行時間.然而，以上5種方法考慮的社會關(guān)系僅僅局限于連續(xù)任務(wù)的前置執(zhí)行者，忽略了工作流中非連續(xù)任務(wù)之間存在交互時社會關(guān)系的影響，也未能充分考慮到執(zhí)行者間的負載均衡.

此外文獻[11]在任務(wù)分配時不僅考慮到當(dāng)前待分配任務(wù)的候選者，也考慮整個實例執(zhí)行中合作候選者間的依賴關(guān)系，優(yōu)先選擇歷史合作次數(shù)最多的執(zhí)行者.然而，他們都沒有考慮到候選者的負載情況.文獻[12]在任務(wù)分配時不僅考慮了任務(wù)候選者的個體屬性，而且考慮了工作流中前一任務(wù)執(zhí)行者對當(dāng)前候選者的影響，改進了傳統(tǒng)的最短處理時間、最短完成時間、平均工作負載和最短工作列表這4種任務(wù)分配算法，但同樣沒有充分考慮到工作流任務(wù)分配中的執(zhí)行者工作負載均衡問題.文獻[13-15]提出的動態(tài)任務(wù)分配策略，主要考慮了眾包(crowdsourcing)執(zhí)行環(huán)境中任務(wù)執(zhí)行候選者在任務(wù)分配時的當(dāng)前狀況，具有一定的現(xiàn)實意義.文獻[16]將機器學(xué)習(xí)算法用于工作流事件日志，在任務(wù)執(zhí)行時根據(jù)算法生成的分類器推薦一個合適的執(zhí)行者，以半自動的方法減少手動員工分配.文獻[17-19]提供了解決任務(wù)分配問題的一個基本框架，但忽略了任務(wù)候選者之間社會關(guān)系的影響，也沒有考慮到同時到達多實例時的情形.

綜上所述，在任務(wù)分配時大多數(shù)的任務(wù)分配算法僅考慮候選執(zhí)行者的個體能力屬性，沒有認識到工作流中不同任務(wù)交互時執(zhí)行者之間的協(xié)作相容性對流程性能的影響.本文提出的基于協(xié)作相容性的任務(wù)均衡分配算法，不僅考慮了執(zhí)行者當(dāng)前的工作負載，而且考慮了流程實例運行中任務(wù)交互時候選者之間的協(xié)作相容性，更好地體現(xiàn)了工作流系統(tǒng)的實際運行情況.

2 基于協(xié)作相容性的任務(wù)均衡分配模型

2.1 問題描述和基本框架

本文通過一個具體實例來闡釋相關(guān)問題.如圖1所示的一個醫(yī)療保險索賠流程[2]，該工作流程涉及索賠的受理(receiving)、材料的驗證(validating)、理算(settlement)、審批簽字(approving)和付款(payment)等任務(wù)處理過程，每個任務(wù)由不同角色執(zhí)行的同時又有不同的交互.

該流程運行時，1)客服代表(customer staff)對醫(yī)療保險索賠進行記錄并將由審查人員(reviewer)進行理賠調(diào)查或體檢；2)評估人員(evaluator)根據(jù)審查人員所提供的信息進行索賠理算(settlement)；3)經(jīng)理(manager)對收到的賠償款項進行簽字確認；4)財務(wù)人員(accountant)將相應(yīng)款項轉(zhuǎn)入客戶賬戶.

由于每一任務(wù)的角色可能處于不同的物理位置，使得任務(wù)執(zhí)行過程中協(xié)作相容性的需求較大.在圖1中，各任務(wù)上面的圓弧狀虛線，表示執(zhí)行不同任務(wù)的角色可能需要進行信息的交互.例如，收到索賠后，審查員可能需要客戶服務(wù)代表澄清關(guān)于某些缺失的索賠信息(如發(fā)生事故的確切位置或事件的時間丟失).同樣，評估員可能需要咨詢審查員關(guān)于事故信息的更多細節(jié).最后，財務(wù)會計人員可能會在付款之前咨詢審查員說明一些支付選項不明的信息(如簽字無效等).

因此，這里我們考慮的任務(wù)分配問題的場景如下：1)我們要考慮候選任務(wù)執(zhí)行者的任務(wù)負載情況，即在分配時優(yōu)選相對輕載的執(zhí)行者；2)由于整個實例中不同任務(wù)可能存在交互的情況，不同執(zhí)行者合作時所需的時間開銷不同，因此任務(wù)分配時還需考慮執(zhí)行者之間的協(xié)作相容性.任務(wù)執(zhí)行者之間的協(xié)作相容性越高，交互時所需的時間越少.由于執(zhí)行者可具備多種角色，即具有執(zhí)行多種任務(wù)的能力，若任務(wù)分配時僅考慮優(yōu)化協(xié)作相容性(我們假設(shè)一個執(zhí)行者與自身的協(xié)作相容度最大)，會導(dǎo)致多個任務(wù)分配給同一個執(zhí)行者，這樣大大增加該執(zhí)行者的工作負載，因此，這2個優(yōu)化目標(biāo)之間存在一定的沖突.為了解決這個問題，我們提出了一個基于協(xié)作相容性的任務(wù)均衡分配基本框架(如圖2所示).

Fig. 2 Framework for tasks allocation based on cooperation capability圖2 基于協(xié)作相容性的任務(wù)均衡分配基本框架

基于該框架，任務(wù)分配的確定過程如下：

1) 根據(jù)任務(wù)候選執(zhí)行者之間相對預(yù)測負載大小(相關(guān)定義在2.2節(jié)中給出)，將候選執(zhí)行者劃分為輕負載、中負載和重負載3個區(qū)間.同一區(qū)間內(nèi)的候選者具有相似的負載.而在具體應(yīng)用中，對候選者的相對預(yù)測負載區(qū)間數(shù)量和參數(shù)的設(shè)置，可根據(jù)工作環(huán)境的實際狀況進行靈活調(diào)整;

2) 選擇輕載區(qū)間內(nèi)的候選者作為待分配任務(wù)的新候選者集合;

3) 根據(jù)具體任務(wù)之間的交互情形，從每一個任務(wù)的新候選者集合中，選擇一個具有能力執(zhí)行該任務(wù)且同時能最大化交互任務(wù)中執(zhí)行者之間的協(xié)作相容性.

在工作流任務(wù)分配過程中，本文所做4點假設(shè)：

1) 工作流中所有任務(wù)候選者之間的協(xié)作相容性獨立于具體的任務(wù)，且執(zhí)行者之間的協(xié)作相容性具有對稱性.

2) 執(zhí)行者間的協(xié)作相容性與交互時所需時間成正比，即2個任務(wù)執(zhí)行者間的協(xié)作相容性越好，任務(wù)執(zhí)行時交流信息花費的時間越小.

3) 工作流運行過程中執(zhí)行者總負載包括2部分：任務(wù)執(zhí)行負載、與其他執(zhí)行者交互所需的負載.其中，任務(wù)執(zhí)行負載是當(dāng)前預(yù)分配任務(wù)及執(zhí)行者的工作列表中所有等待執(zhí)行任務(wù)的負載.

4) 執(zhí)行者對其工作列表中的任務(wù)進行處理時采用“先進先出”方式.

2.2 最優(yōu)任務(wù)分配模型

根據(jù)圖2中的基本框架，本節(jié)將給出具體的計算模型；為了方便描述和分析，表1給出了本文所使用的一些基本符號與定義.

我們用執(zhí)行者完成其工作隊列中所有任務(wù)所需的時間來表示他的工作負載.

定義2. 設(shè)執(zhí)行者uk當(dāng)前負載為wcur(uk)，若任務(wù)Ti即將分配給他，則uk的預(yù)測負載為

定義3. 設(shè)待分配的任務(wù)Ti的候選執(zhí)行者集合為CEi={uk}，且執(zhí)行uk的預(yù)測負載為wpred(uk)，則將候選執(zhí)行者的負載進行歸一化處理后可得到uk的相對預(yù)測負載為

(1)

令A(yù)ik標(biāo)識任務(wù)Ti是否被分配給執(zhí)行者uk，cpij標(biāo)識任務(wù)Ti與Tj需要交互，則工作流任務(wù)分配時執(zhí)行者間發(fā)生交互時的總協(xié)作相容度可表示為

(2)

我們的目標(biāo)是在分析執(zhí)行者任務(wù)負載均衡的基礎(chǔ)上，進一步通過使待分配任務(wù)的執(zhí)行者與流程中各交互任務(wù)的執(zhí)行者之間總體協(xié)作相容性最大，從而提高系統(tǒng)運行的效率.該任務(wù)分配問題可以描述成一個多目標(biāo)整數(shù)線性規(guī)劃問題：

max(CW,WL-1)，

Aik≤Xik，1≤i≤n，1≤k≤m,

Xik∈0,1，1≤i≤n，1≤k≤m，

(3)

盡管式(3)是一個整數(shù)的線性規(guī)劃問題，可以使用數(shù)學(xué)優(yōu)化工具(如CPLEX)計算得出最優(yōu)的分配方法，然而由于問題的規(guī)模，這是非常耗時的.因此，在后面我們首先給出計算執(zhí)行者間協(xié)作相容性的方法，然后提出貪心算法，求解任務(wù)分配過程的局部最優(yōu)解.

Table 1 Definitions of Notations表1 相關(guān)符號與定義

2.3 執(zhí)行者間協(xié)作相容性

當(dāng)工作流中的任務(wù)之間需要交互時，任務(wù)執(zhí)行者間的高協(xié)作相容性可以加快他們信息的交流，提高任務(wù)執(zhí)行的速度.一些電子商務(wù)網(wǎng)站如Epinions.com，Slashdot.org等通過詢問用戶記錄成員之間的協(xié)作相容性來建立員工之間的信任網(wǎng)絡(luò)或黑名單.然而，由于員工之間的協(xié)作相容性屬于個人隱私，從而使得這種通過訪問的方式來記錄彼此間的協(xié)作相容性是非常不合適的.

根據(jù)任務(wù)執(zhí)行者合作的多樣性，本文主要通過工作流日志里執(zhí)行者間協(xié)作完成流程的時間來度量他們的協(xié)作相容性，主要思想如下：對于發(fā)生交互的任意2個任務(wù)，計算進行協(xié)作的2個執(zhí)行者之間平均吞吐時間與最小執(zhí)行時間的差值，相對于2個任務(wù)中最多與最少的執(zhí)行時間的差值比值，則該比值越小，協(xié)作相容性越大.協(xié)作相容性計算為

(4)

其中,cwkv表示uk,uv的協(xié)作相容性;tavg表示uk，uv配合時執(zhí)行流程的平均吞吐時間;tmin表示流程的最小完成時間;tmax表示流程的最大完成時間;0<ω<1.顯然，由式(4)所得的任務(wù)執(zhí)行者之間的協(xié)作相容性取值范圍為cwkv∈[0,1].例如，假設(shè)基于圖1的一個流程日志解析得到的部分執(zhí)行信息如表2所示：

Table 2 Parts of Log Information表2 部分日志信息

由表2可得，流程的平均吞吐時間為tavg=(10+12+11)3=11 min，Mary和Jack配合時的流程平均完成時間為(10+11)2=10.5 min；流程的最大完成時間為12 min，最小完成時間為10 min；取ω=0.8，根據(jù)式(4)得：Mary和和Jack的協(xié)作相容性為0.8.同理可得,Mary和Carl的協(xié)作相容性為0.2.

3 任務(wù)分配策略

為了闡述本文所給算法的適用場合和相關(guān)特點，我們首先給出3種單目標(biāo)的貪心算法，分別針對候選執(zhí)行者的期望任務(wù)負載(expected workload)最小化、流程中所有任務(wù)完成的期望完成時間(expected completed time)最短以及基于預(yù)測負載的協(xié)作相容性最大化;然后在此基礎(chǔ)上提出了聯(lián)合優(yōu)化執(zhí)行者負載均衡及執(zhí)行者間協(xié)作相容性的相關(guān)算法.在后面的實驗中，我們將從不同的角度分析對比這4種算法.

3.1 期望任務(wù)負載最小化策略

下面給出期望工作負載最小化算法ESWL的執(zhí)行過程：

算法1. ESWL算法.

輸入: 執(zhí)行者角色集合MX={Xik}；

輸出: 任務(wù)分配策略集MA={Aik}.

①MA=?；

② FOR each taskTi∈TaskDO

③exp_workload=MAX_INT;k=0；

戰(zhàn)時生活書店出版發(fā)行的文學(xué)期刊中有不少關(guān)于馬列論文藝的重要論文，其觀點精辟，為隨后社會主義文學(xué)的發(fā)展有著重要的指導(dǎo)意義。這些論文大多集中在《文陣》上刊發(fā)，可概括為以下兩大類。

④ FOR eachuj∈UDO

⑤ IF(Xij=1)

⑥ 計算uj的期望任務(wù)數(shù)λj；

⑦ IF(λj

⑧exp_workloadλj；

⑨kj；

⑩ END IF

ESWL算法對流程中的每一個待分配任務(wù)，需要遍歷所有的候選者，因此，其時間復(fù)雜度為O(mn)，其中n是流程中任務(wù)的個數(shù)，m是所有執(zhí)行者數(shù).

3.2 期望完成時間最短化策略

對于流程的期望完成時間最短算法ESCT，其主要思想是：在任務(wù)分配時，遍歷所有具有執(zhí)行該任務(wù)能力的候選者，考察當(dāng)前的執(zhí)行者完成及其所攜帶的工作列表，計算新任務(wù)完成的期望時間，期望時間最短的執(zhí)行者將被挑選出，并將該任務(wù)分配給它.由于執(zhí)行者uk可承擔(dān)的任務(wù)集為Taskk={Ti|Xik=1,i=1,2,…,n}，則uk完成任務(wù)的平均時間為

若uk當(dāng)前待完成的任務(wù)集為TAk，考慮到當(dāng)uk完成TAk中任務(wù)時系統(tǒng)還會分配新任務(wù)，則uk完成任務(wù)的期望時間為

下面給出期望完成時間最短化算法ESCT的執(zhí)行過程：

算法2. ESCT算法.

輸入: 執(zhí)行者角色集合MX={Xik}；

輸出：任務(wù)分配策略集MA={Aik}.

①MA=?；

② FOR each taskTi∈TaskDO

③ FOR eachuj∈UDO

④exp_time=MAX_INT;k=0；

⑤ IF(Xij=1)

⑥ 計算uj完成任務(wù)的期望時間γj；

⑦ IF(γj

⑧exp_timeγj;kj；

⑨ END IF

⑩ END IF

同樣地，該算法對流程中的每一個任務(wù)，也需遍歷所有的候選者.因此，時間復(fù)雜度為O(nm)，其中n是流程中任務(wù)的個數(shù)，m是所有候選者的個數(shù).

3.3 協(xié)作相容性最大化策略

我們首先根據(jù)式(4)計算出執(zhí)行者之間的協(xié)作相容性；然后在文獻[2]的基礎(chǔ)上，給出協(xié)作相容性最大化算法MCW的主要步驟如下：在任務(wù)分配時，遍歷所有具有執(zhí)行該任務(wù)能力的候選者，考察當(dāng)前的執(zhí)行者與所有交互任務(wù)的執(zhí)行者協(xié)作相容性，從中選擇協(xié)作相容性最大的執(zhí)行者分配該任務(wù).

下面給出協(xié)作相容性最大化算法MCW的算法偽碼：

算法3. MCW算法.

輸入: 執(zhí)行者角色集合MX={Xik}、任務(wù)交互集合MCP={cpij}、執(zhí)行者協(xié)作相容集合MCW={cwkv}；

輸出: 任務(wù)分配策略集MA={Aik}.

① FOR eachuk∈UDO

② FOR eachuv∈UDO

③ 由式(4)計算uk與uv間協(xié)作相容性cwkv的值；

④ END FOR

⑤ END FOR

⑥ FOR eachTi∈TaskDO

⑦max_coop0;v0；

⑧ FOR eachukDO

⑨ IF(Xik=1)

⑩max_coop[k]0；

如上所述，該算法對流程中的每一待分配任務(wù)，需要遍歷所有的候選者及任務(wù)集合，用以找到與所有交互任務(wù)執(zhí)行者之間的協(xié)作相容性.因此，時間復(fù)雜度是O(mn2).

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

我們將考慮在執(zhí)行者負載相對均衡的基礎(chǔ)上，且使得執(zhí)行者間整體協(xié)作相容性最優(yōu)的任務(wù)分配算法.在設(shè)計這樣的分配算法MCLB時，需要考慮到流程中存在任務(wù)交互的情形，因此，算法需要3個輸入集合：任務(wù)交互集合MCP={cpij}、執(zhí)行者協(xié)作相容集合MCW={cwkv}及執(zhí)行者角色集合MX={Xik}.在任務(wù)分配過程中，我們目標(biāo)是在保持執(zhí)行者間工作負載相對均衡的基礎(chǔ)上，最大化整個流程中交互任務(wù)間的執(zhí)行者協(xié)作相容性.為了實現(xiàn)這個目標(biāo)，我們首先通過一個映射函數(shù)，將執(zhí)行者之間的協(xié)作相容性值映射為任務(wù)交互時花費的時間，即對2個執(zhí)行者而言，若他們的協(xié)作相容性越高，則彼此交互所需的時間越少.設(shè)2個執(zhí)行者uk和uv分別執(zhí)行任務(wù)Ti和Tj，他們之間協(xié)作相容性為cwkv，則他們交互時間開銷可表示為

(5)

其中，β是協(xié)作相容性對時間映射的比例因子.對于任一執(zhí)行者uk，若考慮將任務(wù)Ti分配給他，則任務(wù)Ti完成的預(yù)測時間為

wpred(uk)=wpred(uk)+

(6)

由于在任務(wù)分配過程中，當(dāng)分配Ti時，可能存在著其他任務(wù)尚未被分配給任何執(zhí)行者，因此，利用式(6)計算Ti分配策略時，我們僅考慮Ti與那些已分配好執(zhí)行者的任務(wù)間的交互情形.

下面給出面向負載均衡的、最大化整體協(xié)作相容性的任務(wù)分配算法MCLB偽碼：

算法4. MCLB算法.

輸入: 執(zhí)行者角色集合MX={Xik}、任務(wù)交互集合MCP={cpij}、執(zhí)行者協(xié)作相容集合MCW={cwkv}；

輸出: 任務(wù)分配策略集MA={Aik}.

① FOR eachuj∈UDO

③ END FOR

⑤ IF(!IsExistCoop(MCP))*判斷是工作流程是否需要任務(wù)交互*

⑥ FORTi∈TaskDO

⑦ 利用ESWL算法找出當(dāng)前期望負載最小的后續(xù)執(zhí)行者uk；

⑧Aik1；

⑨ END FOR；

⑩ ELSE

函數(shù)IsExistCoop(MCP)判斷輸入的流程中是否存在任務(wù)交互.若流程中不存在任務(wù)交互時，時間復(fù)雜度為O(nm)；當(dāng)任務(wù)間存在交互時，該算法在任務(wù)分配時，對每一待分配任務(wù)，在遍歷相對輕載的候選者集合時，還需在該可能候選者的基礎(chǔ)上遍歷其他所有可能交互的任務(wù).因此，算法的時間復(fù)雜度是O(m2n2)，其中n是任務(wù)的個數(shù)，m是所有候選者的個數(shù).

3.5 基于最優(yōu)模型分配的一個例子

為了便于闡述上述方法，現(xiàn)給出了基于圖1場景的一個簡單例子.假設(shè)圖1中每一任務(wù)的角色、執(zhí)行者如表3所示：

Table 3 Task Roles and Candidates表3 任務(wù)角色及候選者信息

其中，基于圖1的任務(wù)交互矩陣如表4所示：

Table 4 Matrix of Task Interaction表4 任務(wù)交互矩陣

設(shè)執(zhí)行者之間計算所得的協(xié)作相容性矩陣為表5所示：

Table 5 Matrix of Cooperation Capability表5 協(xié)作相容性矩陣

基于上面前提條件，則在運行時有如下情形：

1) 初始時所有候選者的工作列表為空，即任務(wù)候選者的待執(zhí)行任務(wù)的負載為0；當(dāng)?shù)竭_第1個流程實例時，流程中所有任務(wù)的待候選者均為空閑(即都在輕載集合中).這時，通過最優(yōu)分配模型，得到總體最大化協(xié)作相容性的任務(wù)分配情況如下：{receiving:Mary,validating:Jack,settlement:Beth,approving:Tony,payment:Clare}.總體協(xié)作相容性為:4.4.

2) 假設(shè)在某一時刻新的流程實例到達時，所有任務(wù)的候選者工作列表中都有等待完成的任務(wù)，即一定的工作負載，且通過估算執(zhí)行者的預(yù)測負載及相對預(yù)測負載值，劃分的新候選集合如下：WL={Mary,Susan,Carl,Clare,Lin}；WM={John,Beth,Tony};WH={Jack,Sam}.

在任務(wù)分配時，首選我們考慮的是負載，將對應(yīng)的輕載集合作為新任務(wù)的候選執(zhí)行者集合.因此，首先從WL集合中搜索具備執(zhí)行該任務(wù)角色的候選者，直到對應(yīng)輕載集合搜索完為止，若未發(fā)現(xiàn)具備承擔(dān)該任務(wù)角色的執(zhí)行者，再依次搜索WM與WH.例如在分配任務(wù)receiving時，由于該任務(wù)的2個候選執(zhí)行者均在WL集合中，因此，候選執(zhí)行者集合就為WL中的Mary,Susan.而在搜索任務(wù)validating的候選者集合時，WL中有一個可能的候選者Carl，則任務(wù)validating的候選執(zhí)行者集{Carl}.通過以上候選執(zhí)行者集合的確定，然后針對分配的可能情況，選擇任務(wù)交互時執(zhí)行者間協(xié)作相容性最大的進行相應(yīng)分配，結(jié)果如下：{receiving;Susan,validating:Carl,settlement:Beth,approving:Tony,payment:Clare}，總體協(xié)作相容性為3.9.

4 實 驗

本節(jié)對ESWL，ESCT，MCW，MCLB這4種算法進行實驗比較來分析各個方法的特點與性能.仿真采用的工作流順序模型如圖3所示:

Fig. 3 Workflow model圖3 工作流模型

在實驗中，我們根據(jù)相對預(yù)測負載值設(shè)置輕負載、中負載、重負載區(qū)間，即WL=[0，0.34)，WM=[0.34，0.67),WH=[0.67，1).首先使用ESWL算法，產(chǎn)生相應(yīng)的工作流日志.根據(jù)所產(chǎn)生的工作流日志信息，計算任務(wù)執(zhí)行者之間的協(xié)作相容性和執(zhí)行者任務(wù)平均完成時間，將協(xié)作相容性值存入?yún)f(xié)作相容性矩陣；在工作流實例不同到達概率的情況下，使用不同的任務(wù)分配算法和相應(yīng)能力配置進行仿真實驗.對每一實例到達的概率，使用每種算法進行100次的仿真，并使用相同的實例隊列和迭代次數(shù)在其他算法進行仿真，采取平均100次的仿真結(jié)果作為最終的結(jié)果進行分析.實驗中工作流實例到達的概率服從二項分布.

各任務(wù)的處理時間設(shè)置如表6所示.在實驗中，執(zhí)行者可承擔(dān)的角色設(shè)置為2種情況：任務(wù)執(zhí)行者僅具備單一角色、任務(wù)執(zhí)行者可具備多個角色的情況(如表7、表8所示)；流程中任務(wù)間的交互情形又分為2種情況：任務(wù)間存在交互、任務(wù)間不存在任何交互(如表9、表10所示).通過結(jié)合執(zhí)行者能力、負載以及任務(wù)交互的特點，仿真實驗了所有4種可能情況下的結(jié)果.

Table 6 Processing Time of Tasks

Table 7 Each Executor Has a Single Role表7 任務(wù)執(zhí)行者僅具備單一角色

Table 8 Each Executor Can Have Several Roles表8 任務(wù)執(zhí)行者可具備多個角色

Table 9 Tasks Have No Interactions表9 任務(wù)間無交互情形

Table 10 Tasks Have Interactions表10 任務(wù)間存在交互情形

任務(wù)無交互情況下是在表7和表8配置下，結(jié)合表9進行仿真實驗.實驗結(jié)果如圖4所示.通過觀察圖4(a)可以看出，4種算法下工作流實例完成時間幾乎相同.這是由于在一個任務(wù)執(zhí)行者僅具備單一角色且無任務(wù)交互時，其他3種算法的本質(zhì)上是一樣的，都是基于最小負載進行任務(wù)分配的，能夠達到任務(wù)的均衡分配.MCW算法的任務(wù)執(zhí)行者是隨機分配的，沒有考慮候選執(zhí)行者實際的負載情形.通過觀察圖4(b)，MCLB算法和ESCT算法完成時間幾乎相同，ESWL和MCW算法略差且具有交叉性.這是由于在一個任務(wù)執(zhí)行者可具備多個角色下，ESWL算法僅以期望任務(wù)負載作為任務(wù)分配的立足點，并不能正確地反映候選者的實際任務(wù)負載.仿真的結(jié)果表明，在沒有任務(wù)交互的情況下，MCLB算法仍然取得了較好的性能.

Fig. 4 Completed time of workflow instances with no task interactions圖4 無任務(wù)交互情況下工作流實例的完成時間

我們現(xiàn)在考慮在工作流實例中任務(wù)有交互情況下，實驗結(jié)果如圖5所示.通過觀察圖5可以看出，在2種場景下，MCLB算法的結(jié)果都是最好的，MCW算法最差.這是由于存在任務(wù)交互時，MCLB算法不僅考慮了任務(wù)的負載，還考慮了交互任務(wù)執(zhí)行者的協(xié)作相容性，一定程度上縮短了任務(wù)交互時的花費時間.而ESCT算法僅考慮了期望完成時間，ESWL算法僅僅考慮期望任務(wù)負載.盡管MCW算法考慮了任務(wù)候選者與前置所有任務(wù)候選者的協(xié)作相容性，但卻忽略了多實例同時到達的場景，也即忽略了任務(wù)負載的影響.同時，從圖5(a)和圖5(b)的結(jié)果對比中可以發(fā)現(xiàn)，MCLB算法在后一種場景下的效果，要比前一種場景下的優(yōu)勢更大，這是由于實驗中任務(wù)候選者增多時任務(wù)選擇性變得更多.

Fig. 5 Completed time of workflow instances having task interactions圖5 存在任務(wù)交互情況下工作流實例的完成時間

下面我們考察任務(wù)執(zhí)行者之間的協(xié)作相容性對工作流實例處理時間的影響.當(dāng)工作流實例中的各任務(wù)間無交互情形時，4種任務(wù)分配算法中工作流實例的平均處理時間總是大小相等，即約為54 min;而當(dāng)工作流任務(wù)存在交互情形時(如圖6所示)，4種任務(wù)分配算法的執(zhí)行時間是不同的.使用MCW算法和MCLB算法時，工作流實例的平均處理時間總是優(yōu)于其他2種算法.其中，圖6(a)中，MCLB算法下工作流實例的平均處理時間比ESCT算法約少2 min，比ESWL算法約少3 min.圖6(b)中，MCLB算法比ESCT算法約少2.5 min，比ESWL算法約少1.3 min.相比之下，MCW算法比ESCT算法約少5 min，比ESWL算法約少6 min.MCW算法下的平均處理時間最小的原因在于，它總是能夠使當(dāng)前任務(wù)執(zhí)行者的協(xié)作相容性最大，尤其在任務(wù)執(zhí)行者具備多個角色時，會將連續(xù)的多個交互任務(wù)分配給同一執(zhí)行者.同時，通過將圖6(a)和圖6(b)的結(jié)果對比可以發(fā)現(xiàn)，在任務(wù)執(zhí)行者可具備多個角色的情況下，使用ESCT算法得到的效率比ESWL算法要差.這是由于ESCT算法不能根據(jù)一個任務(wù)執(zhí)行者可具備多個角色這一特點進行靈活地分配，造成前面任務(wù)候選者的選擇嚴(yán)重影響后面其他任務(wù)的候選者選擇情況.

我們現(xiàn)在分析在4種任務(wù)分配算法下任務(wù)執(zhí)行者的負載均衡，其中執(zhí)行者的總負載為所分配任務(wù)的總執(zhí)行時間加上實際運行中交互時的花費時間.圖7中給出了相關(guān)的實驗結(jié)果.從圖7(a)結(jié)果可以看出，當(dāng)任務(wù)執(zhí)行者僅具備單一角色時，MCLB算法能夠使任務(wù)所有候選者的總負載相對均衡，而其他3種算法下任務(wù)候選者的負載情況相差較大.例如任務(wù)T3的候選者u5,u6，MCLB算法下u5比u6多3.15%，ESWL算法下多13.26%，ESCT算法下多23.74%，而MCW算法下u5比u6少68.04%.從圖7(b)結(jié)果可以看出，一個任務(wù)執(zhí)行者可具備多個角色時，MCLB算法同樣能夠均衡全局任務(wù)執(zhí)行者的負載，而其他3種算法下任務(wù)的執(zhí)行者負載不能保持相對均衡.例如T4的所有候選者有u7，u8，T5的所有候選者有u8，u9，u10.盡管u8可以同時執(zhí)行2個任務(wù)，但MCLB算法下2個任務(wù)所有候選執(zhí)行者的負載相對于其他算法，仍然具有較好的均衡效果.

Fig. 6 Average processing time of a workflow instance having task interactions圖6 存在任務(wù)交互情形時工作流實例的平均處理時間

Fig. 7 Workload for each executor when 20 instances having task interactions arrived per hour圖7 每小時到達20個實例時任務(wù)交互情況下執(zhí)行者的工作負載

5 結(jié) 論

本文研究了基于協(xié)作相容性的工作流任務(wù)分配問題及算法.通過對工作流中任務(wù)之間的交互與否以及執(zhí)行者之間的協(xié)作相容性對工作流性能的影響進行建模，并在考慮負載均衡的基礎(chǔ)上，通過將交互任務(wù)的執(zhí)行者協(xié)作相容性整體最大化以實現(xiàn)最終的任務(wù)分配，減少了流程實例的平均吞吐時間，提高了工作流的整體性能.通過實驗得出，基于協(xié)作相容性的任務(wù)均衡分配方法對工作流中是否存在交互任務(wù)的情況均有良好的執(zhí)行效率.

由于執(zhí)行者之間協(xié)作相容性大小涉及的因素可能有很多，因此本文計算協(xié)作相容性的方法有待進一步細化.同時，由于具體的工作流流程有順序、選擇、并行結(jié)構(gòu)，而本文只關(guān)注了順序結(jié)構(gòu).因此，未來的研究包括3個方面：1)通過考慮更多的因素，進一步完善協(xié)作相容性的計算方法；2)考慮工作流中具有選擇、并行結(jié)構(gòu)時任務(wù)執(zhí)行者間協(xié)作相容性的影響；3)考慮任務(wù)間存在轉(zhuǎn)換概率時的協(xié)作相容性概率期望值.