任務(wù)分配問題

1、組合問題中的分支限界法組合問題中的分支限界法 任務(wù)分配問題任務(wù)分配問題 主講人：郭嘉明主講人：郭嘉明 張旋張旋 任務(wù)分配問題任務(wù)分配問題 任務(wù)分配問題要求把任務(wù)分配問題要求把n項(xiàng)任務(wù)分配給項(xiàng)任務(wù)分配給n個(gè)人，個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖所示是一個(gè)任務(wù)分配的最小的最優(yōu)分配方案。如圖所示是一個(gè)任務(wù)分配的成本矩陣。成本矩陣。 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d圖圖 任務(wù)分配問題的成本矩陣任務(wù)分配問題的成

2、本矩陣求最優(yōu)分配成本的上界和下界求最優(yōu)分配成本的上界和下界考慮任意一個(gè)可行解，例如矩陣中的對(duì)角線是一個(gè)合法的選考慮任意一個(gè)可行解，例如矩陣中的對(duì)角線是一個(gè)合法的選擇，表示將任務(wù)擇，表示將任務(wù)1分配給人員分配給人員a、任務(wù)、任務(wù)2分配給人員分配給人員b、任務(wù)、任務(wù)3分配給人員分配給人員c、任務(wù)、任務(wù)4分配給人員分配給人員d，其成本是，其成本是9+4+1+4=18；或者應(yīng)用貪心法求得一個(gè)近似解：將任務(wù)或者應(yīng)用貪心法求得一個(gè)近似解：將任務(wù)2分配給人員分配給人員a、任、任務(wù)務(wù)3分配給人員分配給人員b、任務(wù)、任務(wù)1分配給人員分配給人員c、任務(wù)、任務(wù)4分配給人員分配給人員d，其成本是其成本是2+3+5+4

3、=14。顯然，。顯然，14是一個(gè)更好的上界。為了是一個(gè)更好的上界。為了獲得下界，考慮人員獲得下界，考慮人員a執(zhí)行所有任務(wù)的最小代價(jià)是執(zhí)行所有任務(wù)的最小代價(jià)是2，人員，人員b執(zhí)行所有任務(wù)的最小代價(jià)是執(zhí)行所有任務(wù)的最小代價(jià)是3，人員，人員c執(zhí)行所有任務(wù)的最小代執(zhí)行所有任務(wù)的最小代價(jià)是價(jià)是1，人員，人員d執(zhí)行所有任務(wù)的最小代價(jià)是執(zhí)行所有任務(wù)的最小代價(jià)是4。因此，將每一。因此，將每一行的最小元素加起來就得到解的下界，其成本是行的最小元素加起來就得到解的下界，其成本是2+3+1+4=10。需要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選。需要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選擇（擇（3和和1來自于矩陣的同一列），

4、它僅僅給出了一個(gè)參考下來自于矩陣的同一列），它僅僅給出了一個(gè)參考下界，這樣，最優(yōu)值一定是界，這樣，最優(yōu)值一定是10, 14之間的某個(gè)值。之間的某個(gè)值。設(shè)當(dāng)前已對(duì)人員設(shè)當(dāng)前已對(duì)人員1i分配了任務(wù)，并且獲得了成本分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：則限界函數(shù)可以定義為： nikkvlb1行的最小值第（2）在結(jié)點(diǎn)2，將任務(wù)1分配給人員a，獲得的成本為9，目標(biāo)函數(shù)值為9 + (3+1+4)=17，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，將任務(wù)2分配給人員a，獲得的成本為2，目標(biāo)函數(shù)值為2 + (3+1+4)=10，將結(jié)點(diǎn)3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，將任務(wù)3分配給人

5、員a，獲得的成本為7，目標(biāo)函數(shù)值為7 + (3+1+4)=15，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，將任務(wù)4分配給人員a，獲得的成本為8，目標(biāo)函數(shù)值為8 + (3+1+4)=16，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)5丟棄； 應(yīng)用分支限界法求解圖所示任務(wù)分配問題，對(duì)解空間樹的搜索如圖所示，具體的搜索過程如下：（1）在根結(jié)點(diǎn)1，沒有分配任務(wù)，根據(jù)限界函數(shù)估算目標(biāo)函數(shù)值為2+3+1+4=10； （3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索；（4）在結(jié)點(diǎn)6，將任務(wù)1分配給人員b，獲得的成本為2+6=8，目標(biāo)函數(shù)值為8+(1+4)13，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，將任務(wù)

6、3分配給人員b，獲得的成本為2+3=5，目標(biāo)函數(shù)值為5+(1+4)10，將結(jié)點(diǎn)7加入表PT中；在結(jié)點(diǎn)8。將任務(wù)4分配給人員b，獲得的成本為2+7=9，目標(biāo)函數(shù)值為9+(1+4)14，將結(jié)點(diǎn)8加入表PT中； （5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)7優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)9，將任務(wù)1分配給人員c，獲得的成本為5+5=10，目標(biāo)函數(shù)值為10+4=14，將結(jié)點(diǎn)9加入表PT中；在結(jié)點(diǎn)10，將任務(wù)4分配給人員c，獲得的成本為5+8=13，目標(biāo)函數(shù)值為13+4=17，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)10丟棄；（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)11，將任務(wù)3分配給人

7、員c，獲得的成本為8+1=9，目標(biāo)函數(shù)值為9+4=13，將結(jié)點(diǎn)11加入表PT中；在結(jié)點(diǎn)12，將任務(wù)4分配給人員c，獲得的成本為8+8=16，目標(biāo)函數(shù)值為16+4=20，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)12丟棄；（9）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索；（10）在結(jié)點(diǎn)13，將任務(wù)4分配給人員d，獲得的成本為9+4=13，目標(biāo)函數(shù)值為13，由于結(jié)點(diǎn)13是葉子結(jié)點(diǎn)，同時(shí)結(jié)點(diǎn)13的目標(biāo)函數(shù)值是表PT中的極小值，所以，結(jié)點(diǎn)13對(duì)應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員

8、b人員人員c人員人員d圖圖 任務(wù)分配問題的成本矩陣任務(wù)分配問題的成本矩陣4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=13圖圖9 分支限界法求解任務(wù)分配問題示例分支限界法求解任務(wù)分配問題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)23567891213111 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個(gè)表為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個(gè)表ST，在表，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最

9、小值結(jié)點(diǎn)中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表存儲(chǔ)到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)為的數(shù)據(jù)結(jié)構(gòu)為(人員人員i- -1分配的分配的任務(wù)任務(wù),lb)(e) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為2a 1b 3c 4d圖圖 任務(wù)分配問題最優(yōu)解的確定任務(wù)分配問題最優(yōu)解的確定(0,10)(2,13) (2,10) (2,14)(0,10)(2,13) (2,14) (3,14)(0,10) (2,10) (2,14) (3,14) (1,13)(0,10) (2,10) (2,13) (0,10) (2,10) (2,13) (1,13)(a) 擴(kuò)展根結(jié)點(diǎn)后的狀

10、態(tài)擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)后的狀態(tài) PTSTPTST PT (c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)7后的狀態(tài)后的狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6后的狀態(tài)后的狀態(tài)(2,14) (3,14) (3,13)PTSTPTST ST 回溯過程是：(3,13)(1,13)(2,13)(0,10) 。算法算法任務(wù)分配問題任務(wù)分配問題 1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT初始化為空；初始化為空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n)

11、 5.2.1 如果人員如果人員k分配任務(wù)分配任務(wù)xk不發(fā)生沖突，則不發(fā)生沖突，則 5.2.1.1 根據(jù)式根據(jù)式9.4計(jì)算目標(biāo)函數(shù)值計(jì)算目標(biāo)函數(shù)值lb; 5.2.1.2 若若lb=up，則將，則將i,lb存儲(chǔ)在表存儲(chǔ)在表PT中；中； 5.2.2 xk=xk+1; 5.3 如果如果k= =n且葉子結(jié)點(diǎn)的且葉子結(jié)點(diǎn)的lb值在表值在表PT中最小，中最小， 則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解；則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解； 5.4 否則，如果否則，如果k= =n且表且表PT中的葉子結(jié)點(diǎn)的中的葉子結(jié)點(diǎn)的lb值不是最小，則值不是最小，則 5.4.1 up=表表PT中的葉子結(jié)點(diǎn)最小的中的葉子結(jié)點(diǎn)最小的lb值值; 5

12、.4.2 將表將表PT中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)刪除；中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)刪除； 5.5 i=表表PT中中l(wèi)b最小的結(jié)點(diǎn)的最小的結(jié)點(diǎn)的xk值；值； 5.6 k=表表PT中中l(wèi)b最小的結(jié)點(diǎn)的最小的結(jié)點(diǎn)的k值；值；k+; #include #include #include int n; /工人和任務(wù)的數(shù)目 int c10001000; unsigned int mincost = 100000; /設(shè)置的初始值,大于可能的費(fèi)用 int task1000,temp1000,worker1000; void main() void Plan(int k,unsigned int cost);int i

13、,j; printf(please input tasks and workers:);scanf(%d%d,&n,&n);printf(輸入每個(gè)工人完成各個(gè)工作的費(fèi)用:n); for(i=0;in;i+) /設(shè)置每個(gè)任務(wù)由不同工人承擔(dān)時(shí)的費(fèi)用及全局?jǐn)?shù)組的初值 /*taski:值為0表示任務(wù)i未分配,值為j表示任務(wù)i分配給工人j; workerk:值為0表示工人k未分配任務(wù),值為1表示工人k已分配任務(wù);*/ workeri = 0; taski = 0; tempi = 0; for(j=0;jn;j+) scanf(%d,&cij); Plan(0,0); /從任務(wù)0開始分配printf(最小總費(fèi)用:%dn,mincost);for(i=0;i=n & costmincost) mincost = cost; for(i=0;in;i+) tempi = taski; /工人i完成任務(wù)tempi else for(i=0;in;i+) /分配任務(wù)k if(workeri