多機調(diào)度問題

1、多機調(diào)度問題王婷Y30150687問題描述解決方法代碼展示時間復(fù)雜度設(shè)有n個獨立的作業(yè)，1,2,3,n，由m臺相同的機器進行加工處理。第i個作業(yè)所需的處理時間為ti。約定：每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間盡可能短的時間內(nèi)由m臺機器加工處理完成。分nm(作業(yè)數(shù)大于機器數(shù))求解。當(dāng)nm時，需要選擇算法來確定最優(yōu)順序?qū)⒆鳂I(yè)分配給空閑的處理機，使得處理時間最短。三種解決方案：1、將作業(yè)按次序平均平均分配給每臺機器；2、把作業(yè)按處理時間從小到大從小到大排序，然后依次分配給空閑

2、的機器；3、把作業(yè)按處理時間從大到小從大到小排序，然后依次分配給空閑的機器（Greedy算法）設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。將作業(yè)按次序平均分配給每臺機器：機器機器作業(yè)作業(yè)時間時間M11,2,32+14+4=20M24,516+6=22M36,75+3=8優(yōu)點：比較簡單，容易想到缺點：沒有考慮時間代價，機器所運行的作業(yè)完全由作業(yè)的次序決定，當(dāng)運行時間比較大的作業(yè)集中在一起時，會把它們分配給同一個機器，這樣所用的時間比較長，效率比較低例如：（2,6,3,5,4,14,16）M1：2,6,3M2

3、：5,4M3：14,16設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。將作業(yè)按從小到大依次分配給空閑的機器：146M1027237501812M232M30431734526234561416設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。將作業(yè)按從小到大依次分配給空閑的機器：機器機器作業(yè)作業(yè)時間時間M11,4,62+5+16=23M27,53+9=12M33,24+14=182 3 4 5 6 14 16優(yōu)點：比較方便，

4、同時也考慮到了時間的安排，比第一種算法有了改進。缺點：運行時間最長的作業(yè)一定是最后完成的，如果運行最長作業(yè)前， 其他機器運行時間差不多就會造成其他幾個機器等待一個機器的狀況，這樣機器的運行效率也比較低。M1 2 7 23M2 3 916475設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。把作業(yè)按從大到小依次分配給空閑的機器（Greedy算算法法）：解多機調(diào)度問題的貪心策略是最長處理時間作業(yè)優(yōu)先，即把處理時間最長的作業(yè)分配給最先空閑的機器，這樣可以保證處理時間長的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理時

5、間。首先將n個作業(yè)依其所需處理的時間使用選擇排序的方法從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機器。機器機器作業(yè)作業(yè)時間時間M1416M22,714+3=17M35,6,3,16+5+4+2=17設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。4256371161465432貪心算法的優(yōu)點解題效率更高，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。貪心算法總是做出在當(dāng)前看來是最好的選擇，不能從整體最優(yōu)上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。對于某些情況，它并不是整體最優(yōu)選擇。16 14 12 11 10 9 8貪心算法確定的順序：M1:16+9=25M2:14+10=24M3:12+11+8=31最優(yōu)順序：M1:11+16=27M2:12+14=26M3:8+9+10=27代碼排序?qū)個作業(yè)依其所需處理的處理時間使用選擇排序的方法從大到小排序時間復(fù)雜度：首先將n個作業(yè)依其所需的處理時間從大到小排序，然后按順序?qū)⒆鳂I(yè)分配給空閑的處理機，主要計算量在于將作業(yè)按處理時間進行從大到小排序。算法的時間復(fù)雜度為O（n2）