分枝-限界branchbound(編輯修改稿)
2024-11-04 13:23 本頁面
【文章內(nèi)容簡介】 正在展開的子節(jié)點(diǎn) x， 如 ?(x)≥U，則停止產(chǎn)生子節(jié)點(diǎn) x， 即不將其放入活節(jié)點(diǎn)表 ? 這種限界方法也可用于 FIFO活結(jié)點(diǎn)表上，稱為 FIFO分枝 限界。 U初始為 ∞ ，其后用新得到的可行解值加以修改 帶截止期的作業(yè)調(diào)度問題（ 1） ? n個(gè)作業(yè)， 1臺處理機(jī)，每個(gè)作業(yè) i對應(yīng)一個(gè)三元組(pi,di,ti) ? pi－ 罰款額 ? di－ 截止期 ? ti － 需要的處理機(jī)時(shí)間 ? 求可行的作業(yè)子集 J，使得罰款額 Σpj最小 ,其中 j為不在J中的作業(yè) ? 定長元組表示可行作業(yè)子集 :(x(1),┅ ,x(n)) ? 設(shè) X=(x(1),…x(k)) 為狀態(tài)空間樹的節(jié)點(diǎn) ? 下界 ?(x)可估計(jì)為已確知的罰款額 : Σ(1x(j))pj ,求和范圍為1≤j≤k 帶截止期的作業(yè)調(diào)度問題（ 2） ? 限界 ? 可行解的必要條件： Σij=1xjtjdi ? 為能較早地使用 ?(x) ≥ U的限界功能 ,可以在每個(gè)結(jié)點(diǎn) x計(jì)算 c(x)的上界 u(x),并用 u(x)修改 U值 ? u(x)可取 x為根的子樹下包含的任一可行解的值 ? 例如取 x(k+1)=… x(n)=0,或用貪心法快速得到一個(gè)可行解 ? 算法每生成一個(gè)子節(jié)點(diǎn)時(shí)就用 u(x)修改 U 調(diào)度問題的定長元組表示 已知 4個(gè)作業(yè)的三元組 (pi,di,ti)分別為 (5,1,1) (10,3,2) (6,2,1) (3,1,1) 調(diào)度問題的另一種狀態(tài)空間樹 12543 X1=1876 1015911141312X1=2 X1=3X1=4X2=3X2=316X4=4 X3=3X3=4 X3=4X2=4X2=4 X2=4X3=4LC檢索＋限界 689 1 0213 4 51 21 171 3x1= 1x1= 2 x1= 3x1= 4x2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1