问题描述:
有 n 个独立的作业算法一直没有找到最优解原因,由 m 个相同的机器处理。作业 i 所需的处理时间为 t。
任何作业都可以在任何机器上处理,但在完成之前不允许中断处理。任何工作都不能拆分成更小的工作。
需要一个作业调度方案,使得给定的n个作业可以在最短的时间内被m台机器处理。
算法分析:
使用处理时间最长的作业优先的贪心选择策略,可以设计出更好的近似算法来解决多机调度问题。
以 nm 为单位求解(作业数大于机器数)。
假设有7个独立作业,所需处理时间为{2,14,4,16,6,5,3},由M1、M2、M3三台机器处理。贪心算法生成的作业调度如下图所示算法一直没有找到最优解原因,需要的总处理时间为17
查看多机调度详情
我的问题是为什么这不是最佳解决方案。在什么情况下它不是最优解?因为书上说这只是一个近似解,所以它是这个例子的最优解