0026算法笔记——多机调度问题

1、问题描述

设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。

多机调度问题是一个NP完全问题，到目前为止还没有完全有效的解法。对于这类问题，用贪心选择策略有时可以设计出一个比较好的近似算法。

2、贪心算法求解思路

采用最长处理时间作业优先的贪心策略:
当n≤m时, 只要将机器i的[0, ti]时间区间分配给作业i即可。
当n>m时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。

具体代码如下：

(1)MinHeap.h

     4、复杂度
     n>m时, 排序耗时O(nlogn). 初始化堆耗时O(m). 堆的DeleteMin和insert 共需O(nlogm).因此算法Greedy 所需时间:O(nlogn)。
     程序执行结果如图：