個體效率受負載影響的任務(wù)分配問題研究.pdf

1、任務(wù)分配問題是多Agent系統(tǒng)中非常重要的一個問題。在任務(wù)分配問題中，個體執(zhí)行任務(wù)的效率是影響系統(tǒng)性能的關(guān)鍵因素。以往研究主要考慮資源環(huán)境（包括個體擁有的資源和周圍環(huán)境資源）對個體執(zhí)行任務(wù)的效率的影響。值得注意的是，心理學(xué)研究發(fā)現(xiàn)，在社會個體執(zhí)行任務(wù)的現(xiàn)實場景中（如眾包系統(tǒng)），社會個體承擔(dān)的負載會對社會個體效率產(chǎn)生影響，而以往研究通常忽略了這一點?；诖?，本文研究了社會個體效率受負載影響的任務(wù)分配問題。具體而言，本文基于心理學(xué)研究中個體

2、效率與負載之間的關(guān)系，在個體效率呈動態(tài)性環(huán)境下考慮如何分配任務(wù)以提高任務(wù)執(zhí)行效率。
　　針對該問題，本文通過理論證明“考慮到個體效率動態(tài)性的最小化最大任務(wù)完成時間的任務(wù)分配問題”是NP難的。本文采取由淺入深的研究方式，首先研究同構(gòu)任務(wù)環(huán)境（所有任務(wù)都相同）下的任務(wù)分配方法。本文提出一個貪心分配算法，并對算法性能進行分析。由于在大規(guī)模任務(wù)環(huán)境下，一次性分配方法容易使個體效率在過載情況下變得很低。因此，本文提出一種適用于大規(guī)模任務(wù)環(huán)境

3、下的分批次分配算法。實驗結(jié)果驗證了貪心分配策略在小規(guī)模任務(wù)環(huán)境下的有效性，以及分批次分配策略在大規(guī)模任務(wù)環(huán)境下的優(yōu)越性。
　　基于同構(gòu)任務(wù)環(huán)境下的研究，本文進一步研究了更加現(xiàn)實的異構(gòu)任務(wù)環(huán)境（任務(wù)之間的工作量和技能要求存在差異）下的任務(wù)分配方法。異構(gòu)任務(wù)環(huán)境下，由于任務(wù)之間的異質(zhì)性以及個體之間的異質(zhì)性，所以需要選擇技能匹配、負載合適的個體來執(zhí)行任務(wù)。因此，本文基于同構(gòu)任務(wù)環(huán)境下的研究，分別對不同任務(wù)規(guī)模下的異構(gòu)任務(wù)分配方法進行研究