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

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

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

3 (計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 南京 210046)

(huhaiyang@hdu.edu.cn)

在工作流調(diào)度中，各任務(wù)由工作流引擎調(diào)度系統(tǒng)中的資源來操作完成.由于不同的任務(wù)分配策略將對(duì)工作流管理系統(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)度各類計(jì)算資源完成任務(wù).在現(xiàn)代企業(yè)中，任務(wù)執(zhí)行者常可承擔(dān)多類角色用于完成多種任務(wù)[2]，其對(duì)完成不同類型任務(wù)常可具有不同的熟悉程度，并且不同人員之間配合協(xié)作的默契程度也存在著差異.

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2.1 問題描述和基本框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

我們的目標(biāo)是在分析執(zhí)行者任務(wù)負(fù)載均衡的基礎(chǔ)上，進(jìn)一步通過使待分配任務(wù)的執(zhí)行者與流程中各交互任務(wù)的執(zhí)行者之間總體協(xié)作相容性最大，從而提高系統(tǒng)運(yùn)行的效率.該任務(wù)分配問題可以描述成一個(gè)多目標(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)是一個(gè)整數(shù)的線性規(guī)劃問題，可以使用數(shù)學(xué)優(yōu)化工具(如CPLEX)計(jì)算得出最優(yōu)的分配方法，然而由于問題的規(guī)模，這是非常耗時(shí)的.因此，在后面我們首先給出計(jì)算執(zhí)行者間協(xié)作相容性的方法，然后提出貪心算法，求解任務(wù)分配過程的局部最優(yōu)解.

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

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

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

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

(4)

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

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

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

3 任務(wù)分配策略

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

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

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

算法1. ESWL算法.

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

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

①M(fèi)A=?；

② FOR each taskTi∈TaskDO

③exp_workload=MAX_INT;k=0；

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

④ FOR eachuj∈UDO

⑤ IF(Xij=1)

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

⑦ IF(λj

⑧exp_workloadλj；

⑨kj；

⑩ END IF

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

3.2 期望完成時(shí)間最短化策略

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

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

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

算法2. ESCT算法.

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

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

①M(fèi)A=?；

② FOR each taskTi∈TaskDO

③ FOR eachuj∈UDO

④exp_time=MAX_INT;k=0；

⑤ IF(Xij=1)

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

⑦ IF(γj

⑧exp_timeγj;kj；

⑨ END IF

⑩ END IF

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

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

我們首先根據(jù)式(4)計(jì)算出執(zhí)行者之間的協(xié)作相容性；然后在文獻(xiàn)[2]的基礎(chǔ)上，給出協(xié)作相容性最大化算法MCW的主要步驟如下：在任務(wù)分配時(shí)，遍歷所有具有執(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)計(jì)算uk與uv間協(xié)作相容性cwkv的值；

④ END FOR

⑤ END FOR

⑥ FOR eachTi∈TaskDO

⑦max_coop0;v0；

⑧ FOR eachukDO

⑨ IF(Xik=1)

⑩max_coop[k]0；

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

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

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

(5)

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

wpred(uk)=wpred(uk)+

(6)

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

下面給出面向負(fù)載均衡的、最大化整體協(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)前期望負(fù)載最小的后續(xù)執(zhí)行者uk；

⑧Aik1；

⑨ END FOR；

⑩ ELSE

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

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

為了便于闡述上述方法，現(xiàn)給出了基于圖1場(chǎng)景的一個(gè)簡(jiǎn)單例子.假設(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í)行者之間計(jì)算所得的協(xié)作相容性矩陣為表5所示：

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

基于上面前提條件，則在運(yùn)行時(shí)有如下情形：

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

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

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

4 實(shí) 驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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