《《平行機排序問題》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《平行機排序問題》PPT課件.ppt（24頁珍藏版）》請在裝配圖網上搜索。
1、平行機排序問題 Parallel Machine Scheduling,平行機排序問題,有多份文件需安排給幾個打字員打印，若每個 打字員的打字速度相同，應該如何安排使得這 些文件在最短時間內完成。,問題描述,設有m臺完全相同的機器 , n個互相獨立的工 件 ，每個工件只需在一臺機器上不中斷的加工 一次，并設m
2、我們想要的目標函數為 ，它表示所有的工件加工工 作在最短時間內完成。若記 為機器 所要加工的所有 工件所需的總的時間，那么顯然有 。 討論這種所需加工時間最小的平行機排序問題也稱為使時 間跨度最小的平行機排序問題。,,,,,,,,整數線性規(guī)劃（PMS）,,,,說明,整數線性規(guī)劃的解中不能說明次序，但是由于平行機排序 問題中，每臺機器加工的總時間不受這臺機器的加工次序 影響，所以這個整數線性規(guī)劃的最優(yōu)解即也就給出了最優(yōu) 排序.,平行機排序問題與裝箱問題,這兩個問題成為對偶問題。把這兩個問題中的箱子和機器 對應，物品與工件對應。那么裝箱問題就是箱子長度固 定，目標是使箱子數最小；而平行
3、機排序問題是箱子數固 定，目標是使得箱子長度最短。,平行機排序問題最優(yōu)解的下界,定理：最優(yōu)解值的一個下界為 。,,近似算法,LS算法（List Scheduling） LPT算法（Largest Processing Time) Multifit算法 多項式時間近似方案,,LS算法,將每一個工件分給最早空閑的機器。 為在線算法，時間復雜度 。,,算法描述,,,絕對性能比,定理： 。,,實例,5臺相同機器，20個工件，加工時間分別為 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31,LPT算法,先將物品按照
4、加工時間從大到小排序，然后按照LS算法排 序。 此算法為離線算法，時間復雜度,,絕對性能比,定理： 。,,實例,5臺相同機器，20個工件，加工時間分別為 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31,Multifit算法,將m臺機器看成m個箱子，n個工件看成有長度的物 品，其長度為該工件在機器上所需的加工時間。 先確定箱子容量的上下界 ，然后用FFD算法 判斷是否能將所有物品放入容量為 的m個 箱子中，以調整上下界，迭代k次后以上界作為輸出。,,,算法描述,該算法初始上界為CU取LPT算法所得到的解值，初始
5、下界 為CL.,,絕對性能比,定理：當Multifit算法中FFD算法迭代了k次，則對任意實 例I , 且常數部分 不可改進，即 。,,,,實例,5臺相同機器，20個工件，加工時間分別為 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31 迭代2次,多項式時間近似方案,取出mk個加工時間最長的工件，若mkn，則取出所有工件。 對取出的所有工件用枚舉法求出最優(yōu)排序。 由得到的mk個工件最優(yōu)排序出發(fā)，將剩下的n-mk個工件用LS算法，安排它們的加工。,,絕對性能比、時間復雜性,定理 ： ， 的時間復雜性為,,,,實例,5臺相同機器，20個工件，加工時間分別為 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31 取k=2,練習,6臺相同機器，25個工件，加工時間分別為 10，13，15，27，18，8，5，9，21， 17，12，7，11，3，6，16，23，22，4， 19，26，31，1，2，9 分別用LS算法，LPT算法， Multifit算法 （迭 代3次）， 算法（取k=3）進行排序,,
《平行機排序問題》PPT課件.ppt
