例如：（2,6,3,5,4,14,16）
M1：2,6,3 M2：5,4 M3：14,16
设7个独立作业{1,2,3,4,5,6,7}由3台机器 M1，M2和M3加工处理。各作业所需的 处理时间分别为{2,14,4,16,6,5,3}。 将作业按从小到大依次分配给空闲的机器：
1 2 0 7 3 2 1 0 4 12 3 4 7 6 4 5 5 6 2 14 6 16 23
设7个独立作业{1,2,3,4,5,6,7}由3台机器 M1，M2和M3加工处理。各作业所需的 处理时间分别为{2,14,4,16,6,5,3}。 将作业按次序平均分配给每台机器：
机器 M1 M2 M3 作业 1,2,3 4,5 6,7 时间 2+14+4=20 16+6=22 5+3=8
优点：比较简单，容易想到 缺点：没有考虑时间代价，机器所运行的作业完 全由作业的次序决定，当运行时间比较大的作业 集中在一起时，会把它们分配给同一个机器，这 样所用的时间比较长，效率比较低
分n<=m( 作业数小于机器数)，n>m(作业数大于 机器数)求解。 当n<=m时，将n个作业分配给m台机器中的前n 台就可以了。 当 n>m 时，需要选择算法来确定最优顺序将作 业分配给空闲的处理机，使得处理时间最短。
三种解决方案： 1、将作业按次序平均分配给每台机器； 2、把作业按处理时间从小到大排序，然 后依次分配给空闲的机器； 3、把作业按处理时间从大到小排序，然 后依次分配给空闲的机器（Greedy算法）
设7个独立作业{1,2,3,4,5,6,7}由3台机器 M1，M2和M3加工处理。各作业所需 的处理时间分别为{2,14,4,16,6,5,3}。
4 16 2 14 5 6 6 5 3 4 7 3 1 2
机器 M1 M2
作业 4 2,7
时间 16 14+3=17
M3
5,6,3,1
6+5+4+2=17
M2 3
5
9
设7个独立作业{1,2,3,4,5,6,7}由3台机器M1， M2和M3加工处理。各作业所需的处理时间 分别为{2,14,4,16,6,5,3}。 把作业按从大到小依次分配给空闲的机器（Greedy算 法）： 解多机调度问题的贪心策略是最长处理时间作 业优先，即把处理时间最长的作业分配给最先空闲的 机器，这样可以保证处理时间长的作业优先处理，从 而在整体上获得尽可能短的处理时间。 首先将n个作业依其所需处理的时间使用选择排 序的方法从大到小排序，然后依此顺序将作业分配给 空闲的处理机器。
2+5+16=23 3+9=12 4+14=18
优点：比较方便，同时也考虑到了时间的安排， 比第一种算法有了改进。 缺点：运行时间最长的作业一定是最后完成的， 如果运行最长作业前， 其他机器运行时间差不多 就会造成其他几个机器等待一个机器的状况，这 样机器的运行效率也比较低。
1
M1 2
6
7
4
23
7
最优顺序： M1:11+16=27 M2:12+14=26 M3:8+9+10=27
代码——排序
将n个作业依其 所需处理的处理 时间使用选择排 序的方法从大到 小排序
时间复杂度：
首先将n个作业依其所需的处理时间从大到 小排序，然后按顺序将作业分配给空闲的处 理机，主要计算量在于将作业按处理时间进 行从大到小排序。算法的时间复杂度为 O（n2）。
贪心算法的优点解题效率更高，即使贪心算法 不能得到整体最优解，但其最终结果却是最优解的 很好的近似解。 贪心算法总是做出在当前看来是最好的选择， 不能从整体最优上加以考虑，它所做出的选择只是 在某种意义上的局部最优选择。对于某些情况，它 并不是整体最优选择。
16 14 12 11 10 9 8
贪心算法确定的序： M1:16+9=25 M2:14+10=24 M3:12+11+8=31
多机调度问题
王婷 Y30150687
问题描述 解决方法 代码展示 时间复杂度
设有 n 个独立的作业， 1,2,3,…,n ，由 m 台相同的机器进行加工处理。第 i 个作业所 需的处理时间为ti。 约定：每个作业均可在任何一台机器 上加工处理，但未完工前不允许中断处理。 作业不能拆分成更小的子作业。 多机调度问题要求给出一种作业调度 方案，使所给的n个作业在尽可能短的时间 内由m台机器加工处理完成。
总结
多机调度问题到目前为止还没有有效 的解法，对于这一类问题，用最长处理时 间作业优先的贪心选择策略有时可以设计 出较好的近似算法。贪心算法在NP类问题 的求解中发挥着越来越重要的作用。
M1 M2
0
3
7 4 3
5 18 2
M3
设7个独立作业{1,2,3,4,5,6,7}由3台机器 M1，M2和M3加工处理。各作业所需的 处理时间分别为{2,14,4,16,6,5,3}。 将作业按从小到大依次分配给空闲的机器： 2 3 4 5 6 14 16
机器 作业 时间
M1 M2 M3
1,4,6 7,5 3,2