多影響因素的加權(quán)任務(wù)分配范文

本站小編為你精心準(zhǔn)備了多影響因素的加權(quán)任務(wù)分配參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

《計(jì)算機(jī)與數(shù)字工程雜志》2014年第七期

1任務(wù)分配策略研究

1.1分配策略的形式化表示定義1在工作流定義中有一項(xiàng)任務(wù)Jnew被分配給一個(gè)抽象的角色，而這個(gè)角色包含了多個(gè)員工。每一個(gè)候選員工都已經(jīng)存在一個(gè)任務(wù)列表，任務(wù)分配問(wèn)題就是根據(jù)任務(wù)屬性及候選人狀態(tài)把任務(wù)分配給最適合的候選人。定義2參與員工狀態(tài)有效性。在參與員工執(zhí)行工作過(guò)程中，經(jīng)常會(huì)因?yàn)槿绯霾睢⑿菁俚仍蚨鵁o(wú)法工作。對(duì)于給定的參與員工Ui∈U。

1.2基于多影響因素的加權(quán)任務(wù)分配策略通過(guò)對(duì)實(shí)際流程中的任務(wù)分配進(jìn)行分析，發(fā)現(xiàn)最影響任務(wù)的執(zhí)行效率的是任務(wù)分配不均導(dǎo)致的任務(wù)間等待，負(fù)載均衡在任務(wù)實(shí)際分配當(dāng)中是至關(guān)重要的，所以將本分配算法設(shè)計(jì)為兩階段：第一階段根據(jù)參與者的狀態(tài)有效性和負(fù)載狀況劃分資源候選者集合，第二階段從資源候選者集合中按照綜合匹配度進(jìn)行執(zhí)行者集合劃分，將任務(wù)分配給評(píng)估分?jǐn)?shù)最高的執(zhí)行者集合。在計(jì)時(shí)器規(guī)定的時(shí)間內(nèi)，如果沒(méi)有員工執(zhí)行此項(xiàng)任務(wù)，則工作流引擎會(huì)從之前的評(píng)估結(jié)果中篩掉目前執(zhí)行者集合，然后再次對(duì)任務(wù)進(jìn)行分配。資源執(zhí)行者集合的確定過(guò)程如下：對(duì)一項(xiàng)特定的工作項(xiàng)任務(wù)Jnew，計(jì)算其相對(duì)預(yù)測(cè)負(fù)載偏差值，將參與員工劃分成不同的負(fù)載區(qū)間，每一區(qū)間內(nèi)的參與員工被認(rèn)為具有相似的任務(wù)負(fù)載。參與員工的相對(duì)預(yù)測(cè)負(fù)載偏差區(qū)間數(shù)量的選擇，可以根據(jù)具體的企業(yè)需求靈活的調(diào)整。預(yù)測(cè)負(fù)載偏差區(qū)間的設(shè)定方法如下：設(shè)N為相對(duì)預(yù)測(cè)負(fù)載偏差區(qū)間數(shù)，R［N＋1］為相對(duì)預(yù)測(cè)負(fù)載偏差數(shù)組。其中，R［0］＝－1，R［N］＝＋1，區(qū)間的上下界可以根據(jù)工作流要求確定。Sk為屬于第k個(gè)區(qū)間中的候選者集合，k越大預(yù)測(cè)負(fù)載越重，k＝1，2，…，N。對(duì)于參與者Ui，如果N［k－1］β（Ui，Jj）＜N［k］，則Ui被劃分到k區(qū)間。當(dāng)區(qū)間數(shù)過(guò)小的時(shí)候，負(fù)載均衡的程度將會(huì)變得很低，也失去了負(fù)載均衡的意義；當(dāng)區(qū)間數(shù)過(guò)大接近員工數(shù)時(shí)，對(duì)于后面的綜合評(píng)估就沒(méi)有意義了，所以相對(duì)預(yù)測(cè)負(fù)載偏差區(qū)間數(shù)不宜過(guò)小，也不宜過(guò)大。選擇相對(duì)負(fù)載較輕的區(qū)間為資源候選集合，對(duì)集合中的每一個(gè)員工的執(zhí)行能力、感興趣度和成本進(jìn)行綜合的評(píng)估，本文提出了一個(gè)帶有權(quán)值的綜合評(píng)估分?jǐn)?shù)計(jì)算方法，根據(jù)確定的評(píng)估值，對(duì)確定的資源候選集合進(jìn)行排序，并再次進(jìn)行區(qū)間劃分，設(shè)定方法如下：設(shè)M為評(píng)估值區(qū)間數(shù)，P［M＋1］評(píng)估值區(qū)間數(shù)組，對(duì)評(píng)估值最高的數(shù)值偏差在a之內(nèi)的，放入P［0］，偏差為a～2a的放入P［1］，依次類(lèi)推，直到M數(shù)組執(zhí)行完畢。M和a值可設(shè)定，評(píng)估值區(qū)間數(shù)M的選擇也可以根據(jù)企業(yè)的需求靈活的調(diào)整；這樣排名最靠前的候選集合就是任務(wù)的最合適執(zhí)行者集合。

1.3算法實(shí)現(xiàn)1）啟動(dòng)計(jì)時(shí)器，初始化參數(shù)，置T＝1；2）獲取要執(zhí)行的任務(wù)Jnew，確定相對(duì)預(yù)測(cè)負(fù)載偏差區(qū)間數(shù)N、評(píng)估值區(qū)間數(shù)M和偏差值a及各影響因素權(quán)值w1、w2、w3；3）根據(jù)流程定義找到符合條件能夠承擔(dān)任務(wù)的所有參與者集合S（其中要求參與者的狀態(tài)有效性availability（Ui）＞0）；4）計(jì)算每個(gè)參與者Ui的預(yù)測(cè)負(fù)載PreWol（Ui），以及任務(wù)Jnew的平均預(yù)測(cè)負(fù)載TaskPreWol（Jj）。

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

與當(dāng)前的基于多準(zhǔn)則的任務(wù)分配策略相比，本策略增加了狀態(tài)有效性和成本兩個(gè)影響因素，能夠在算法執(zhí)行前篩除狀態(tài)無(wú)效用戶(hù)，避免了由無(wú)效用戶(hù)執(zhí)行任務(wù)導(dǎo)致流程掛起的情況，可以提高流程執(zhí)行效率，對(duì)于成本因素的計(jì)算使得該策略更加具有普適性。為了評(píng)價(jià)本文提出的任務(wù)分配算法的負(fù)載性能，我們將算法進(jìn)行仿真實(shí)驗(yàn)。各個(gè)員工對(duì)分配任務(wù)得到的處理順序是先進(jìn)先出的處理原則，不進(jìn)行任何的優(yōu)先調(diào)度，由于采用這種原則，本實(shí)驗(yàn)不考慮計(jì)時(shí)器進(jìn)行再次分配的情況。在測(cè)試期間測(cè)試100個(gè)工作流實(shí)例的運(yùn)行情況，將三個(gè)并行任務(wù)T1、T2和T3分配給四個(gè)員工（U1，U2，U3，U4），設(shè)所有參與者狀態(tài)有效性均為1，評(píng)估因素影響權(quán)值為w1＝0．6，w2＝0．2，w3＝0．2。表2給出了參與員工執(zhí)行三類(lèi)任務(wù)的影響因素評(píng)估值，表3給出了員工完成任務(wù)所需時(shí)間。根據(jù)上述測(cè)試環(huán)境，對(duì)Round－Robin以及基于多影響因素的加權(quán)任務(wù)分配算法進(jìn)行負(fù)載分析，負(fù)載結(jié)果如圖1～圖3所示。從圖1與圖2中可看出，當(dāng)執(zhí)行任務(wù)數(shù)較多時(shí)，Round－Robin算法的負(fù)載不均衡，執(zhí)行能力強(qiáng)、速度快的U1和U2負(fù)載較輕，而執(zhí)行能力一般的U3和U4則負(fù)載較大；基于多影響因素的加權(quán)任務(wù)分配算法則做到了負(fù)載均衡，隨著任務(wù)數(shù)的增加曲線(xiàn)也成線(xiàn)性增長(zhǎng)，負(fù)載均衡趨勢(shì)不會(huì)改變。而且，在任務(wù)的總執(zhí)行時(shí)間上，本文的算法相對(duì)于Round－Robin算法也有了一定程度的降低，如圖3所示。從圖中可以看出，當(dāng)任務(wù)數(shù)大于60后，多因素加權(quán)算法的總執(zhí)行時(shí)間相對(duì)較少。綜合進(jìn)行評(píng)估，基于多影響因素的加權(quán)任務(wù)分配算法在提高流程執(zhí)行效率方面有很大幫助。

3結(jié)語(yǔ)

實(shí)現(xiàn)任務(wù)的自動(dòng)優(yōu)選分配是提高工作流系統(tǒng)運(yùn)行效率的關(guān)鍵步驟，本文在前人研究的基礎(chǔ)上提出了基于多影響因素的加權(quán)任務(wù)分配策略，該策略綜合考慮了參與者狀態(tài)有效性、負(fù)載、參與者能力、興趣度以及成本因素，設(shè)計(jì)并實(shí)現(xiàn)了基于多影響因素的加權(quán)任務(wù)分配算法。通過(guò)實(shí)驗(yàn)結(jié)果可以看出，該算法可有效降低任務(wù)平均等待時(shí)間和人員負(fù)載，提高了任務(wù)平均處理效率。同時(shí)，由于各影響因素權(quán)重可按需調(diào)節(jié)，該策略能很好地適應(yīng)不同領(lǐng)域業(yè)務(wù)對(duì)任務(wù)分配的不同需求，解決工作流在任務(wù)分配上的靈活性問(wèn)題，更加具有普適性。

作者：尚福華孫勝男陳效果單位：東北石油大學(xué)計(jì)算機(jī)信息技術(shù)學(xué)院東方地球物理勘探有限公司