生產(chǎn)作業(yè)排序的問題(編輯修改稿)
2025-03-28 03:58 本頁面
【文章內(nèi)容簡介】 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 對于一般的 n/m/P/Fmax問題 ， 可以用分支定界法求得最優(yōu)解 ， 但計算量很大 。 實(shí)際中 ， 可以用啟發(fā)式算法求近優(yōu)解 。 ) 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 Palmer法 ? 計算工件斜度指標(biāo) ?i ： m : 機(jī)器數(shù) pik ：工件 i在機(jī)器 k上的加工時間。 i=1,2,? ,n ? 排序方法 : 按 ?i從大到小的順序排列。 ? 按排序的順序計算 Fmax ??????m1kiki p]2/)1m(k[ ) 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 關(guān)鍵工件法 ： ? 計算 Pi=? Pij ， 找出 Pi最長的工件 ， 將之作為關(guān)鍵工件 C。 ? 對其余工件 ， 若 Pi1≤ Pim ， 則按 Pi1由小到大排成序列 SA。 若 Pi1 Pim ， 則按 Pim由大到小排成序列 SB。 ? 順序 （ SA， C， SB） 即為近優(yōu)解 。 ) 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 用關(guān)鍵工件法求解i 1 2 3 4P i1 1 2 6 3P i2 8 4 2 9P i3 4 5 8 2p i 1 3 1 1 1 6 1 4 ) 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 CDS法 ： ? CDS法 是 Johnson算法 的擴(kuò)展方法，從 M1個排序中找出近優(yōu)解。 加工順序 A 加工時間 B 加工時間1 t1tm2 t1+t2tm 1+tm3 t1+t2+t3tm 2+tm1+tm? ?? ??m1 t1+t2+ ?+tm 1t2+ ? +tm1+tm ) 四、一般 n/m/P/ Fmax問題的啟發(fā)式算法 ? L＝ 1，按 Johnson算法得到加工順序 (1， 2， 3， 4)， Fmax＝ 28 ? L＝ 2，按 Johnson算法得到加工順序 (2， 3， 1， 4)， Fmax＝ 29 ? 取順序 (1， 2， 3， 4）為最優(yōu)順序。 用 CDS 法求解
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1