基于協作相容性的工作流任務分配優化方法

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

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

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

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

(huhaiyang@hdu.edu.cn)

在工作流調度中，各任務由工作流引擎調度系統中的資源來操作完成.由于不同的任務分配策略將對工作流管理系統的性能有很大的影響[1]，因此需要制定良好的任務分配優化策略，將各任務分配給合適的資源.根據應用領域的不同，工作流系統中的資源可以是人力資源、設備儀器資源、應用程序或網絡資源等.其中人力資源在工作流系統中起著重要的作用，他們一般是指具有特定技能的任務執行者，通過相應的角色(role)彼此配合與協作，在工作流系統中調度各類計算資源完成任務.在現代企業中，任務執行者常可承擔多類角色用于完成多種任務[2]，其對完成不同類型任務常可具有不同的熟悉程度，并且不同人員之間配合協作的默契程度也存在著差異.

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

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

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

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

1 相關工作

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

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

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

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

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

2 基于協作相容性的任務均衡分配模型

2.1 問題描述和基本框架

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

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

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

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

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

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

1) 根據任務候選執行者之間相對預測負載大小(相關定義在2.2節中給出)，將候選執行者劃分為輕負載、中負載和重負載3個區間.同一區間內的候選者具有相似的負載.而在具體應用中，對候選者的相對預測負載區間數量和參數的設置，可根據工作環境的實際狀況進行靈活調整;

2) 選擇輕載區間內的候選者作為待分配任務的新候選者集合;

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

在工作流任務分配過程中，本文所做4點假設：

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

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

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

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

2.2 最優任務分配模型

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

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

定義2. 設執行者uk當前負載為wcur(uk)，若任務Ti即將分配給他，則uk的預測負載為

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

(1)

令Aik標識任務Ti是否被分配給執行者uk，cpij標識任務Ti與Tj需要交互，則工作流任務分配時執行者間發生交互時的總協作相容度可表示為

(2)

我們的目標是在分析執行者任務負載均衡的基礎上，進一步通過使待分配任務的執行者與流程中各交互任務的執行者之間總體協作相容性最大，從而提高系統運行的效率.該任務分配問題可以描述成一個多目標整數線性規劃問題：

max(CW,WL-1)，

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

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

(3)

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

Table 1 Definitions of Notations表1 相關符號與定義

2.3 執行者間協作相容性

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

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

(4)

其中,cwkv表示uk,uv的協作相容性;tavg表示uk，uv配合時執行流程的平均吞吐時間;tmin表示流程的最小完成時間;tmax表示流程的最大完成時間;0<ω<1.顯然，由式(4)所得的任務執行者之間的協作相容性取值范圍為cwkv∈[0,1].例如，假設基于圖1的一個流程日志解析得到的部分執行信息如表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，根據式(4)得：Mary和和Jack的協作相容性為0.8.同理可得,Mary和Carl的協作相容性為0.2.

3 任務分配策略

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

3.1 期望任務負載最小化策略

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

算法1. ESWL算法.

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

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

①MA=?；

② FOR each taskTi∈TaskDO

③exp_workload=MAX_INT;k=0；

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

④ FOR eachuj∈UDO

⑤ IF(Xij=1)

⑥ 計算uj的期望任務數λj；

⑦ IF(λj

⑧exp_workloadλj；

⑨kj；

⑩ END IF

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

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

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

若uk當前待完成的任務集為TAk，考慮到當uk完成TAk中任務時系統還會分配新任務，則uk完成任務的期望時間為

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

算法2. ESCT算法.

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

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

①MA=?；

② FOR each taskTi∈TaskDO

③ FOR eachuj∈UDO

④exp_time=MAX_INT;k=0；

⑤ IF(Xij=1)

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

⑦ IF(γj

⑧exp_timeγj;kj；

⑨ END IF

⑩ END IF

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

3.3 協作相容性最大化策略

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

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

算法3. MCW算法.

輸入: 執行者角色集合MX={Xik}、任務交互集合MCP={cpij}、執行者協作相容集合MCW={cwkv}；

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

① FOR eachuk∈UDO

② FOR eachuv∈UDO

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

④ END FOR

⑤ END FOR

⑥ FOR eachTi∈TaskDO

⑦max_coop0;v0；

⑧ FOR eachukDO

⑨ IF(Xik=1)

⑩max_coop[k]0；

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

3.4 聯合優化策略

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

(5)

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

wpred(uk)=wpred(uk)+

(6)

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

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

算法4. MCLB算法.

輸入: 執行者角色集合MX={Xik}、任務交互集合MCP={cpij}、執行者協作相容集合MCW={cwkv}；

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

① FOR eachuj∈UDO

③ END FOR

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

⑥ FORTi∈TaskDO

⑦ 利用ESWL算法找出當前期望負載最小的后續執行者uk；

⑧Aik1；

⑨ END FOR；

⑩ ELSE

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

3.5 基于最優模型分配的一個例子

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

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

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

Table 4 Matrix of Task Interaction表4 任務交互矩陣

設執行者之間計算所得的協作相容性矩陣為表5所示：

Table 5 Matrix of Cooperation Capability表5 協作相容性矩陣

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

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

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

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

4 實 驗

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

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

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

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

Table 6 Processing Time of Tasks

Table 7 Each Executor Has a Single Role表7 任務執行者僅具備單一角色

Table 8 Each Executor Can Have Several Roles表8 任務執行者可具備多個角色

Table 9 Tasks Have No Interactions表9 任務間無交互情形

Table 10 Tasks Have Interactions表10 任務間存在交互情形

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

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

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

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

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

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

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

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

5 結 論

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

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