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