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