算法設計及分析 王紅梅 第二版 第9章 分支限界法

1、教學重點教學重點分支限界法的設計思想，各種經(jīng)典問題的限界函數(shù)分支限界法的設計思想，各種經(jīng)典問題的限界函數(shù)教學難點教學難點各種經(jīng)典問題的限界函數(shù)以及限界算法各種經(jīng)典問題的限界函數(shù)以及限界算法教學內容及目教學內容及目標標知識點知識點教學要求教學要求了解了解理解理解掌握掌握熟練掌握熟練掌握分支限界法的設計思想分支限界法的設計思想分支限界法的時空性能分支限界法的時空性能TSP問題問題多段圖的最短路徑問題多段圖的最短路徑問題0/1背包問題背包問題任務分配問題任務分配問題批處理作業(yè)調度問題批處理作業(yè)調度問題學習目標第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖圖問題中的分支限界法問題中的

2、分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法回溯法回溯法：按深度優(yōu)先策略遍歷問題的解空間：按深度優(yōu)先策略遍歷問題的解空間樹，應用約束條件、目標函數(shù)等剪枝函數(shù)實樹，應用約束條件、目標函數(shù)等剪枝函數(shù)實行剪枝行剪枝分支限界法分支限界法：按廣度優(yōu)先策略遍歷問題的解：按廣度優(yōu)先策略遍歷問題的解空間樹，在遍歷過程中，對已經(jīng)處理的每一空間樹，在遍歷過程中，對已經(jīng)處理的每一個結點根據(jù)限界函數(shù)估算目標函數(shù)的可能取個結點根據(jù)限界函數(shù)估算目標函數(shù)的可能取值，從中選取使目標函數(shù)取得極值的結點優(yōu)值，從中選取使目標函數(shù)取得極值的結點優(yōu)先進行廣度優(yōu)先搜索，從而不斷調整搜索方先進行廣度優(yōu)先搜索，從而不斷調整

3、搜索方向，盡快找到問題的解。向，盡快找到問題的解。 9.1 概概 述述 9.1 概概 述述 9.1.1 分支限界法的設計思想分支限界法的設計思想9.1.2 分支限界法的時間性能分支限界法的時間性能分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想物品物品重量重量(w)價值價值(v)價值價值/重量重量(v/w)144010274263525543124分支限界法的設計思想分支限界法的設計思想)()(11iiwvwWvub分支限界法的設計思想分支限界法的設計思想w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11無效解無效解w=4

4、, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12無效解無效解w=9, v=65ub=65234567891PT表圖9.1 0/1背包問題分支限界法的設計思想分支限界法的設計思想n在表在表PT中選取目標函數(shù)值取得中選取目標函數(shù)值取得極大的結點極大的結點2 優(yōu)先進行搜索；優(yōu)先進行搜索； 分支限界法的設計思想分支限界法的設計思想在表在表PT中選取目標函數(shù)值取得極大的結點中選取目標函數(shù)值取得極大的結點5 優(yōu)先進行搜索優(yōu)先進行搜索分支限界法的設計思想分支限界法的設計思想在表在表PT 中選取目標函數(shù)值取得極大的結點中選取目標函數(shù)值取得極大的結點6 優(yōu)先進行搜索優(yōu)先進行

5、搜索分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想(c) 擴展結點擴展結點5后后 (d) 擴展結點擴展結點6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.2 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴展根結點后擴展根結點后 (b) 擴展結點擴展結點2后后(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)3792567分支限界法

6、的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的一般過程分支限界法的一般過程 1根據(jù)限界函數(shù)計算目標函數(shù)的根據(jù)限界函數(shù)計算目標函數(shù)的 down，up； 2將待處理結點表將待處理結點表PT 初始化為空；初始化為空； 3. 對根結點的每個孩子結點對根結點的每個孩子結點x執(zhí)行下列操作執(zhí)行下列操作 3.1 估算結點估算結點x的目標函數(shù)值的目標函數(shù)值value; 3.2 若（若（value=down）,則將結點則將結點x加入表加入表PT中；中； 4循環(huán)直到某個葉子結點的目標函數(shù)值在表循環(huán)直到某個葉子結點的目標函數(shù)值在表PT中最大中最大4.1 i=表表PT中值最大的結點；

7、中值最大的結點；4.2 對結點對結點i的每個孩子結點的每個孩子結點x執(zhí)行下列操作執(zhí)行下列操作4.2.1 估算結點估算結點x的目標函數(shù)值的目標函數(shù)值value；4.2.2 若若(value=down)，則將結點，則將結點x加入表加入表PT中；中；4.2.3 若（結點若（結點x是葉子結點且是葉子結點且value值在表值在表PT中最大），則將結點中最大），則將結點x對對應的解輸出，算法結束；應的解輸出，算法結束；4.2.4 若若(結點結點x是葉子結點但是葉子結點但value值在表值在表PT中不是最大中不是最大),則令則令down=value，并且將表，并且將表PT中所有小于中所有小于value的結點

8、刪除；的結點刪除；分支限界法的設計思想分支限界法的設計思想),()(211kxxxx),(),(211kxxxboundxbound),(),()(21211kxxxboundxxboundxbound分支限界法的設計思想分支限界法的設計思想),(21kxxxX),(),()(21211kxxxboundxxboundxbound分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想分支限界法的設計思想(c) 擴展結點擴展結點5后后 (d) 擴展結點擴展結點6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65

9、圖圖9.3 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴展根結點后擴展根結點后 (b) 擴展結點擴展結點2后后(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)3792567分支限界法的設計思想分支限界法的設計思想9.1 概概 述述 9.1.1 分支限界法的設計思想分支限界法的設計思想9.1.2 分支限界法的時間性能分支限界法的時間性能9.1.2 分支限界法的時間性能分支限

10、界法的時間性能 9.1.2 分支限界法的時間性能分支限界法的時間性能 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.2 圖問題中的分支限界法圖問題中的分支限界法 9.2.1 TSP問題問題 9.2.2 多段圖的最短路徑問題多段圖的最短路徑問題9.2.1 TSP問題問題 TSP TSP問題是指旅行家要旅行問題是指旅行家要旅行n個城市，要求各個城個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。的路程最短。27156

11、3134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一個無向圖一個無向圖 (b) 無向圖的代價矩陣無向圖的代價矩陣圖圖9.4 無向圖及其代價矩陣無向圖及其代價矩陣9.2 TSP問題問題271563134253984n 部分解的目標函數(shù)值的計算方法部分解的目標函數(shù)值的計算方法n假設當前已確定的路徑為假設當前已確定的路徑為U=(r1,r2,rk), 則：則： 例如圖例如圖10.4所示無向圖，如果部分解包含頂點所示無向圖，如果部分解包含頂點U=(1, 4)，則該，則該部分解的下界是部分解的下界是: lb=(2*5+(1+3)+(3+6)+

12、(1+2)+(2+3)/2=16UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個元素素行不在路徑上的最小元分支限界法求解分支限界法求解TSP問題示例問題示例271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 1111,(2 )/ 2jkiiijiikrUlbc rrrr行不在路徑上的最小元素行最小的兩個元素分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點2優(yōu)先進行搜索

13、優(yōu)先進行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點3優(yōu)先進行搜索優(yōu)先進行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點11優(yōu)先進行搜索優(yōu)先進行搜索n處理結點處理結點11的孩子。結點的孩子。結點12，C1C3C5C2 ，路徑長度為1+2+9，目標函數(shù)值:lb=(2*12+(3+3)+(3+4)/2=19 超出目標函數(shù)的界，將結點12丟棄n

14、在結點在結點13， C1C3 C5C4 ，路徑長度為1+2+3 目標函數(shù)值：lb=(2*6+(3+4)+(3+6)/2=14,將結點13加入表PT中在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點13優(yōu)先進行搜索優(yōu)先進行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點10優(yōu)先進行搜索優(yōu)先進行搜索n處理結點處理結點13的孩子。結點的孩子。結點14， C1C3 C5C4C2 ，路徑長度為1+2+3+7，目標函數(shù)值:lb=(2*13+(3+3)/2=16由于結點14為葉子結點，得到一

15、個可行解其路徑長度為16 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP問題示例問題示例分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點16優(yōu)先進行搜索優(yōu)先進行搜索n處理結點處理結點10的孩子。結點的孩子。結點15，C1C3 C4C2，長，長度度12。 目標函數(shù):lb=(2*12+(3+3)+(2+3)/2=18 超出目標函數(shù)的界，將結點15丟棄n結點結點16， C1C3 C4C5 ，長度，長度8 目標函數(shù):lb=(2*8+(3+2)+(3+6)/2=15 將結

16、點16加入表PT中n處理結點處理結點16的孩子。結點的孩子。結點17,C1C3C4C5C2,長度長度17，目標函數(shù):lb =(2*17+(3+3)/2=20,超目標函數(shù)的界，結點17丟棄表表PT中目標函數(shù)值均為中目標函數(shù)值均為16，且已找到葉子結點，且已找到葉子結點14的長度是的長度是16，故這是最優(yōu)解，搜索過程結束。故這是最優(yōu)解，搜索過程結束。 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb

17、=1491152lb=1954lb=141142lb=16142lb=1845lb=151152lb=201分支限界法求解分支限界法求解TSP問題示例問題示例C2C1C3C5C4C3C5C4C2C4C5C4C2C2 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (g) 擴展結點擴展結點16后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為135421圖圖9.6 TSP問題最優(yōu)解的確定問題最優(yōu)解的確定(1, 2)14 (1, 3)14 (1, 4)16(a) 擴展根結點后的狀態(tài)擴展根結點后的狀態(tài) (b) 擴展結點擴展結點2后的狀態(tài)后的狀態(tài)(c) 擴展結點擴展結點3后的狀態(tài)后的

18、狀態(tài)(d) 擴展結點擴展結點11后的狀態(tài)后的狀態(tài)(e) 擴展結點擴展結點13后的狀態(tài)后的狀態(tài)(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5)14(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)

19、16(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(f) 擴展結點擴展結點10后的狀態(tài)后的狀態(tài)算法算法9.1TSP問題問題輸入：圖輸入：圖G（V，E）輸出：最短哈密爾頓回路輸出：最短哈密爾頓回路 1根據(jù)限界函數(shù)計算目標函數(shù)的下界根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2計算根結點的目標函數(shù)值

20、并加入待處理結點表計算根結點的目標函數(shù)值并加入待處理結點表PT； 3循環(huán)直到某個葉子結點的目標函數(shù)值在表循環(huán)直到某個葉子結點的目標函數(shù)值在表PT中取得極小值中取得極小值 3.1 i=表表PT中具有最小值的結點；中具有最小值的結點； 3.2 對結點對結點i的每個孩子結點的每個孩子結點x執(zhí)行下列操作：執(zhí)行下列操作：3.2.1 估算結點估算結點x的目標函數(shù)值的目標函數(shù)值lb;3.2.2 若（若（lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊段的最短邊第第 應用分支限界法求解圖9.7所示多段圖的最短路徑問題，其搜索空間如圖9.8所示，具體的搜索過程如下（加黑表示該路徑

21、上已經(jīng)確定的邊）：（1）在根結點1，計算目標函數(shù)的值為14，將根結點加入表PT；（2）處理根結點每個孩子結點。結點2，第1段選擇邊，目標函數(shù)值為lb=4+8+5+3=20，超出目標函數(shù)的界，將結點2丟棄；在結點3，第1段選擇邊，目標函數(shù)值為lb=2+7+5+3=17，將結點3加入表PT；在結點4，第1段選擇邊，目標函數(shù)值為lb=3+4+5+3=15，將結點4加入表PT中；（3）在表PT中選取目標函數(shù)值極小的結點4優(yōu)先進行搜索；1203456789492387884756866537（4）在結點5，第2段選擇邊，目標函數(shù)值為lb=3+4+6+3=16，將結點5加入表PT中；在結點6，第2段選擇邊

22、，目標函數(shù)值為lb=3+7+5+3=18，將結點6加入表PT；（5）在表PT中選取目標函數(shù)值極小的結點5優(yōu)先進行搜索；（6）處理結點5的每個孩子結點。結點7，已確定路徑是0357，可直接確定第4段的邊，目標函數(shù)值為lb=3+4+8+7=22，超界丟棄；在結點8，已確定路徑是0358，可直接確定第4段的邊，目標函數(shù)值為lb=3+4+6+3=16，為一個可行解；由于結點8是葉子結點，并且其目標函數(shù)值是PT中最小的，所以它是最優(yōu)解，搜索結束。12034567894923878847568665376401lb=20231startlb=1802lb=1603lb=15圖圖9.8 分支限界法求解多段圖

23、的最短路徑問題示例分支限界法求解多段圖的最短路徑問題示例(表示該結點被丟棄，結點上方的數(shù)組表示搜索順序表示該結點被丟棄，結點上方的數(shù)組表示搜索順序)535lb=1636lb=1887lb=22lb=165857第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.3 9.3 組合問題中的分支限界法組合問題中的分支限界法 9.3.2 9.3.2 任務分配問題任務分配問題 9.3.3 9.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題9.3.1 9.3.1 0/1背包問題背包問題9.3.2 任務分

24、配問題任務分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務分配問題的成本矩陣任務分配問題的成本矩陣9.3.2 任務分配問題任務分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務分配問題的成本矩陣任務分配問題的成本矩陣9.3.2 任務分配問題任務分配問題 nikkvlb1行的最小值第9.3.2 任務分配問題任務分配問題 C9 2 7 86 4 3 75

25、8 1 87 6 9 4人員人員a人員人員b人員人員c人員人員d圖圖9.11 分支限界法求解任務分配問題示例分支限界法求解任務分配問題示例(表示該結點被丟棄，結點上方的數(shù)組表示搜索順序表示該結點被丟棄，結點上方的數(shù)組表示搜索順序)4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=1323567891213111nikkvlb1行的最小值第 C9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員

26、人員b人員人員c人員人員d任務1任務4任務2任務1任務3任務4任務1任務49.3.2 任務分配問題任務分配問題 9.3.2 任務分配問題任務分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員人員b人員人員c人員人員dn在結點在結點6 將J2人員a,J1人員b，獲得的成本為2+6=8 目標函數(shù)值:lb=8+(1+4)13 將結點6加入表PT中在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點3優(yōu)先進行搜索優(yōu)先進行搜索9.3.2 任務分配問題任務分配問題 9 2 7 86 4 3 75 8 1 87 6 9

27、 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員人員b人員人員c人員人員d在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點7優(yōu)先進行搜索優(yōu)先進行搜索9.3.2 任務分配問題任務分配問題 9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務4人員人員a人員人員b人員人員c人員人員d在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點6 6優(yōu)先進行搜索優(yōu)先進行搜索9.3.2 任務分配問題任務分配問題 在表在表PT中選取目標函數(shù)值極小的結點中選取目標函數(shù)值極小的結點1111優(yōu)先進行搜索優(yōu)先進行搜索9.3.2

28、任務分配問題任務分配問題 9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任務任務3 任務任務49.3.2 任務分配問題任務分配問題 (人員人員i-1分配的任務分配的任務,lb)(e) 擴展結點擴展結點11后的狀態(tài)，后的狀態(tài)，最優(yōu)解為最優(yōu)解為2a，1b，3c，4d(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) 擴展根結點后的狀態(tài)擴展根結點

29、后的狀態(tài) (b) 擴展結點擴展結點3后的狀態(tài)后的狀態(tài) PTSTPTST PTST (c) 擴展結點擴展結點7后的狀態(tài)后的狀態(tài) (d) 擴展結點擴展結點6后的狀態(tài)后的狀態(tài)(2,14) (3,14) (3,13)PTSTPTST 9.3.2 任務分配問題任務分配問題 算法算法9.3任務分配問題任務分配問題 1根據(jù)限界函數(shù)計算目標函數(shù)的根據(jù)限界函數(shù)計算目標函數(shù)的 down；采用貪心法得到；采用貪心法得到up； 2將待處理結點表將待處理結點表PT 初始化為空；初始化為空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人員如果人員k 分配任務分配

30、任務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 9.3.2 任務分配問題任務分配問題 算法算法9.3任務分配問題任務分配問題 5.3 如果如果k= =n且葉子結點的且葉子結點的lb值在表值在表PT中最小，中最小， 則輸出該葉子結點對應的最優(yōu)解；則輸出該葉子結點對應的最優(yōu)解； 5.4 否則，如果否則，如果k= =n且表且表PT中的葉子結點的中的葉子結點的lb值不是最小，則值不是最小，則 5.4.1 up=表

31、表PT中的葉子結點最小的中的葉子結點最小的lb值值; 5.4.2 將表將表PT中超出目標函數(shù)界的結點刪除；中超出目標函數(shù)界的結點刪除； 5.5 i=表表PT中中l(wèi)b最小的結點的最小的結點的xk值；值； 5.6 k=表表PT中中l(wèi)b最小的結點的最小的結點的k值；值；k+;9.3.2 任務分配問題任務分配問題 9.3 9.3 組合問題中的分支限界法組合問題中的分支限界法 9.3.2 9.3.2 任務分配問題任務分配問題 9.3.3 9.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題9.3.1 9.3.1 0/1背包問題背包問題9.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題T 5 7 910 5 2

32、 9 9 5 7 8 10J1J2J3J4機器1 機器2 機器3 設設 J=J1, J2, J3, J4 是是 4 個待處理的作業(yè)，每個作業(yè)的處個待處理的作業(yè)，每個作業(yè)的處理順序相同理順序相同: 機器機器1上處理上處理機器機器2上處理上處理機器機器3上處理上處理需要的處理時間如下矩陣所示需要的處理時間如下矩陣所示:9.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題上界？隨機產生幾個方案，從中選取最短完成時間為問題的上界？隨機產生幾個方案，從中選取最短完成時間為問題的上界。如若處理順序為上界。如若處理順序為: :J4 J1 J3 J2，調度方案，調度方案: :J4:7 J1:5 J3:9 J2:1

33、0機器機器1機器機器2機器機器3 圖圖9.13 批處理調度問題的調度方案批處理調度問題的調度方案空閑空閑:7 J4:8 J1:7 J3:9 J2:5空閑空閑:15 J4:10 J1:9 J3:5 J2:29.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題上界：41min3121kiknjjitttn批處理作業(yè)調度問題的限界函數(shù)批處理作業(yè)調度問題的限界函數(shù)ndown理想情況機器1和機器2開始作業(yè)后無空閑，最后處理的恰好是在機器3上處理時間最短的作業(yè)。例如，以作業(yè) Ji 開始的處理順序，估算處理所需的最短時間是最短時間是：tij: 表示表示 Ji 需要機器需要機器 j 的處理時間的處理時間(1in,

34、 1j3)9.3.3 批處理作業(yè)調度問題批處理作業(yè)調度問題作業(yè)Ji在機器1上的處理時間作業(yè)作業(yè)1作業(yè)作業(yè)n在機器2上的處理時間總和在機器3上處理時間最短的作業(yè)n目標函數(shù)下界計算目標函數(shù)下界計算lb若已安排了k-1個作業(yè)集合，即：M 1, 2, , k-1，|M|=k-1sum1k-1：機器機器1 1完成k-1個作業(yè)的處理時間sum2k-1：機器2完成k-1個作業(yè)的處理時間現(xiàn)要處理作業(yè)k，此時，該部分解的目標函數(shù)值的下界lb計算方法如下：（1）sum1k=sum1k-1+ tk1（2）（3）sum2k=maxsum1k, sum2k-1 + tk2 23,maxsum1k,sum2k-1min ijj k j Mi Mlbtt9.3.3 批