1.问题分析 设有n个独立的作业{1, 2, ..., n}，由m台相同的机器{M1, M2, ..., Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个 作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间 内由m台机器加工处理完成。 2.问题的解决方法 贪心算法求解多机调度问题的贪心策略是最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。 作业的个数为n，机器的数目为m A: n<m 这种情况很简单，将n个作业分配给m个机器中的n个就可以了。 B: n>m 设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。这里给出三种解决办法：

方法一：贪心算法。按照最长处理时间的作业优先原则，先将处理时间最长的作业分配给最先空闲的机器，然后再分配其它作业。根据这种方法，可以得到如下的作业调度方案：

M1：4(3) 2(1)
M2：16(4) 6(5)
M3：14(2) 5(6) 3(7)

其中，括号中的数字表示作业的编号，数字前的数字表示作业需要的处理时间。

方法二：最小堆算法。将m台机器按照空闲时间的先后顺序组成一个最小堆，每次将作业分配给空闲时间最短的机器即可。根据这种方法，可以得到如下的作业调度方案：

M1：4(3) 2(1)
M2：6(5) 16(4)
M3：14(2) 5(6) 3(7)

方法三：动态规划算法。设f(i,j)表示前i个作业分配给j台机器的最小完成时间，其中第i个作业分配给第j台机器。则有如下的状态转移方程：

f(i,j) = min{max{f(k,j-1), sum(i-k+1, i)}}, 1 <= k < i

其中，max{f(k,j-1), sum(i-k+1, i)}表示将第k到第i个作业分配给最后一台机器处理所需要的最长时间，sum(i-k+1, i)表示第k到第i个作业的总处理时间。根据动态规划算法，可以得到如下的作业调度方案：

M1：4(3) 2(1)
M2：16(4) 3(7)
M3：14(2) 5(6)

其中，括号中的数字表示作业的编号，数字前的数字表示作业需要的处理时间。

相关问题

1.问题分析 设有n个独立的作业{1, 2, ..., n}，由m台相同的机器{M1, M2, ..., Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个 作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间 内由m台机器加工处理完成。 2.问题的解决方法 贪心算法求解多机调度问题的贪心策略是最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。 作业的个数为n，机器的数目为m A: n<m 这种情况很简单，将n个作业分配给m个机器中的n个就可以了。 B: n>m 设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}

按照贪心策略，我们首先把处理时间最长的作业16分配给空闲机器M1，然后再把处理时间第二长的作业14分配给空闲机器M2，最后再把剩下的所有作业分配给M3。所以，该问题的调度方案为：
M1：4、16
M2：2、14
M3：3、5、6、7
因此，完成这7个独立作业的最短处理时间为16。

多机调度问题: 设有n项独立的作业(1,2,..., n),由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定:任何一项作业可在任何一台机器上处理，但未完工前不准中断处理:任何作业不能拆分更小的子作业 请给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。写出算法思想、具体伪码，并证明其正确性。

算法思想：贪心算法 + 最小堆

1. 首先将 n 个作业按照所需处理时间 t 从大到小排序
2. 创建一个大小为 m 的最小堆，将前 m 个作业加入堆中
3. 对于剩余的作业，每次从堆中取出处理时间最短的作业，将其分配到该作业所需处理时间最短的机器上，并更新该机器的处理时间
4. 将新的作业加入堆中，重复步骤 3 直到所有作业都被处理完毕

具体伪码：

1. 将作业按照处理时间从大到小排序
2. 创建大小为 m 的最小堆 heap
3. for i in range(m):
       将作业 i 分配到第 i 台机器上，并更新该机器的处理时间
       将作业 i 的处理时间加入堆 heap 中
4. for i in range(m, n):
       取出堆顶元素 job，将其分配到处理时间最短的机器上，并更新该机器的处理时间
       将 job 的处理时间加入堆 heap 中
5. 返回最后一台机器的处理时间作为总时间

正确性证明：

- 对于第一组 m 个作业，我们将它们分配到 m 台机器上，每台机器的处理时间为该作业所需处理时间。因此，这 m 个作业的总时间为 m 台机器中处理时间最长的那台机器的处理时间。
- 对于第二组作业，我们每次从堆中取出处理时间最短的作业，并将其分配到处理时间最短的机器上。因此，第二组作业的总时间一定不会超过第一组作业的总时间，即不会超过 m 台机器中处理时间最长的那台机器的处理时间。
- 由于我们在每次分配作业时都选择了处理时间最短的机器，因此在最坏情况下，每台机器的处理时间都不会超过总时间的两倍。因此，我们得到的调度方案一定是最优的。