贪心法之多机调度问题.docx
105 浏览量
2023-11-08
10:00:34
上传
评论
收藏 37KB DOCX 举报
贪心法之多机调度问题
问题描述：
设有 n 个独立的作业，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为
t[i]。 任何作业可以在任何一台机器上面加工处理，但未完工之前不允许中断处理。任何
作业不能拆分成更小的作业。 要求给出一种作业调度方案，使所给的 n 个作业在尽可能短
的时间内由 m 台机器加工处理完成。
这个问题是 NP 完全问题，到目前为止还没有有效的解法(求最优解)，但是可以用贪心选
择策略设计出较好的近似算法(求次优解)。
算法分析：
采用最长处理时间作业优先的贪心选择策略，可以设计出解多机调度问题较好的近似算
法。
当 n<=m(作业数小于机器数)时，只要将机器 i 的 时间区间分配给作业 i 即可；
当 n>m 时，首先将 n 个作业从大到小排序，然后依此顺序将作业分配给空闲的处理
机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长
的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是
将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完
了只剩所需时间最长的作业在处理的情况，这样势必效率较低。
假定有 7 个独立作业，所需处理时间分别为｛2，14，4，16，6，5，3｝，由三台机器
M1,M2,M3 加工。按照贪心算法产生的作业调度如下图所示，所需总加工时间为 17.
代码实现：
资源评论
