多机调度问题

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）