任務(wù)分配問題

1、組合問題中的分支限界法組合問題中的分支限界法 任務(wù)分配問題任務(wù)分配問題 主講人：郭嘉明主講人：郭嘉明 張旋張旋 任務(wù)分配問題任務(wù)分配問題 任務(wù)分配問題要求把任務(wù)分配問題要求把n項任務(wù)分配給項任務(wù)分配給n個人，個人，每個人完成每項任務(wù)的成本不同，要求分配總成本每個人完成每項任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖所示是一個任務(wù)分配的最小的最優(yōu)分配方案。如圖所示是一個任務(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)分配成本的上界和下界考慮任意一個可行解，例如矩陣中的對角線是一個合法的選考慮任意一個可行解，例如矩陣中的對角線是一個合法的選擇，表示將任務(wù)擇，表示將任務(wù)1分配給人員分配給人員a、任務(wù)、任務(wù)2分配給人員分配給人員b、任務(wù)、任務(wù)3分配給人員分配給人員c、任務(wù)、任務(wù)4分配給人員分配給人員d，其成本是，其成本是9+4+1+4=18；或者應(yīng)用貪心法求得一個近似解：將任務(wù)或者應(yīng)用貪心法求得一個近似解：將任務(wù)2分配給人員分配給人員a、任、任務(wù)務(wù)3分配給人員分配給人員b、任務(wù)、任務(wù)1分配給人員分配給人員c、任務(wù)、任務(wù)4分配給人員分配給人員d，其成本是其成本是2+3+5+4

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

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

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

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

7、員c，獲得的成本為8+1=9，目標函數(shù)值為9+4=13，將結(jié)點11加入表PT中；在結(jié)點12，將任務(wù)4分配給人員c，獲得的成本為8+8=16，目標函數(shù)值為16+4=20，超出目標函數(shù)的界10, 14，將結(jié)點12丟棄；（9）在表PT中選取目標函數(shù)值極小的結(jié)點11優(yōu)先進行搜索；（10）在結(jié)點13，將任務(wù)4分配給人員d，獲得的成本為9+4=13，目標函數(shù)值為13，由于結(jié)點13是葉子結(jié)點，同時結(jié)點13的目標函數(shù)值是表PT中的極小值，所以，結(jié)點13對應(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é)點被丟棄，結(jié)點上方的數(shù)組表示搜索順序表示該結(jié)點被丟棄，結(jié)點上方的數(shù)組表示搜索順序)23567891213111 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表，在表PT中取出最小值結(jié)點進行擴充時，將最

9、小值結(jié)點中取出最小值結(jié)點進行擴充時，將最小值結(jié)點存儲到表存儲到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)為的數(shù)據(jù)結(jié)構(gòu)為(人員人員i- -1分配的分配的任務(wù)任務(wù),lb)(e) 擴展結(jié)點擴展結(jié)點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) 擴展根結(jié)點后的狀

10、態(tài)擴展根結(jié)點后的狀態(tài) (b) 擴展結(jié)點擴展結(jié)點3后的狀態(tài)后的狀態(tài) PTSTPTST PT (c) 擴展結(jié)點擴展結(jié)點7后的狀態(tài)后的狀態(tài) (d) 擴展結(jié)點擴展結(jié)點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ù)計算目標函數(shù)的下界根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結(jié)點表將待處理結(jié)點表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計算目標函數(shù)值計算目標函數(shù)值lb; 5.2.1.2 若若lb=up，則將，則將i,lb存儲在表存儲在表PT中；中； 5.2.2 xk=xk+1; 5.3 如果如果k= =n且葉子結(jié)點的且葉子結(jié)點的lb值在表值在表PT中最小，中最小， 則輸出該葉子結(jié)點對應(yīng)的最優(yōu)解；則輸出該葉子結(jié)點對應(yīng)的最優(yōu)解； 5.4 否則，如果否則，如果k= =n且表且表PT中的葉子結(jié)點的中的葉子結(jié)點的lb值不是最小，則值不是最小，則 5.4.1 up=表表PT中的葉子結(jié)點最小的中的葉子結(jié)點最小的lb值值; 5

12、.4.2 將表將表PT中超出目標函數(shù)界的結(jié)點刪除；中超出目標函數(shù)界的結(jié)點刪除； 5.5 i=表表PT中中l(wèi)b最小的結(jié)點的最小的結(jié)點的xk值；值； 5.6 k=表表PT中中l(wèi)b最小的結(jié)點的最小的結(jié)點的k值；值；k+; #include #include #include int n; /工人和任務(wù)的數(shù)目 int c10001000; unsigned int mincost = 100000; /設(shè)置的初始值,大于可能的費用 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(輸入每個工人完成各個工作的費用:n); for(i=0;in;i+) /設(shè)置每個任務(wù)由不同工人承擔時的費用及全局數(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(最小總費用:%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