第6章分支限界法-資料下載頁
2024-10-04 19:17本頁面
【正文】 x = 。 bestd = (ld, )。 } } S=n1的情況，計算出此時的密度和 bestd進(jìn)行比較。 35 電路板排列問題 算法描述 else {// 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn) for (int i = + 1。 i = n。 i++) { HeapNode node = new HeapNode(0, new int [m + 1], 0, new int [n + 1])。 for (int j = 1。 j = m。 j++) // 新插入的電路板 [j] = [j] + board [[i]][j]。 36 電路板排列問題 int ld = 0。 // 新插入電路板的密度 for (int j = 1。 j = m。 j++) if ([j] 0 amp。amp。 total[j] != [j]) ld++。 = (ld, )。 if ( bestd) {// 可能產(chǎn)生更好的葉結(jié)點(diǎn) = + 1。 for (int j = 1。 j = n。 j++) [j] = [j]。 [] = [i]。 [i] = []。 (node)。 } } } 算法描述 計算出每一個兒子結(jié)點(diǎn)的密度與 bestd進(jìn)行比較大于 bestd時加入隊(duì)列 37 批處理作業(yè)問題 1. 問題的描述 給定 n個作業(yè)的集合 J={J1,J2,… ,Jn}。 每一個作業(yè) Ji都有 2項(xiàng)任務(wù)要分別在 2臺機(jī)器上完成。每一個作業(yè)必須先由機(jī)器 1處理，然后再由機(jī)器 2處理。作業(yè) Ji需要機(jī)器 j的處理時間為 tji， i=1,2,… ,n；j=1,2。 對于一個確定的作業(yè)調(diào)度，設(shè)是 Fji是作業(yè) i在機(jī)器 j上完成處理的時間。則所有作業(yè)在機(jī)器 2上完成處理的時間和 ??? ni iFf1 2稱為該作業(yè)調(diào)度的完成時間和。批處理作業(yè)調(diào)度問題要求對于給定的 n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達(dá)到最小。 38 批處理作業(yè)問題 2. 限界函數(shù) 在結(jié)點(diǎn) E處相應(yīng)子樹中葉結(jié)點(diǎn)完成時間和的下界是： },m a x { 212 SSFfMii ?? ??注意到如果選擇 Pk， 使 t1pk在 k=r+1時依非減序排列， S1則取得極小值 。 同理如果選擇 Pk使 t2pk依非減序排列，則 S2取得極小值。 }?,?m ax { 212 SSFfMii ?? ??這可以作為優(yōu)先隊(duì)列式分支限界法中的限界函數(shù)。 39 批處理作業(yè)問題 3. 算法描述 算法的 while循環(huán)完成對排列樹內(nèi)部結(jié)點(diǎn)的有序擴(kuò)展。在 while循環(huán)體內(nèi)算法依次從活結(jié)點(diǎn)優(yōu)先隊(duì)列中取出具有最小 bb值（完成時間和下界）的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并加以擴(kuò)展。 首先考慮 =n的情形，當(dāng)前擴(kuò)展結(jié)點(diǎn) enode是排列樹中的葉結(jié)點(diǎn)。 。當(dāng) bestc時更新當(dāng)前最優(yōu)值 bestc和相應(yīng)的當(dāng)前最優(yōu)解 bestx。 當(dāng) n時，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn) enode的所有兒子結(jié)點(diǎn)。對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個兒子結(jié)點(diǎn) node， 計算出其相應(yīng)的完成時間和的下界 bb。 當(dāng) bb bestc時，將該兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。而當(dāng) bb? bestc時，可將結(jié)點(diǎn) node舍去。 40 批處理作業(yè)問題 do { if ( == n ) {// 葉結(jié)點(diǎn) if ( bestc) { bestc = 。 for (int i = 0。 i n。 i++) bestx[i] = [i]。 } } 3. 算法描述 當(dāng) bestc時，更新當(dāng)前最優(yōu)值 beste和相應(yīng)的最優(yōu)解 bestx 41 批處理作業(yè)問題 3. 算法描述 else // 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn) for (int i = 。 i n。 i++) { (, ,i)。 int [] f= new int [3]。 int bb=bound(enode,f)。 if (bb bestc ) { HeapNode node=new HeapNode(enode,f,bb,n)。 (node)。 } (, ,i)。 } // 完成結(jié)點(diǎn)擴(kuò)展 當(dāng) bbbestc時，將兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1