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

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

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

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