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

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

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

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

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