QQ泡沫乐园 · 免费提供游戏辅助,破解软件,活动资讯,喜欢记得收藏哦!
综合软件_线报活动_游戏辅助_最新电影_最优质的的辅助分享平台

什么情况下会不是最优解?近似解是什么原因?

泡沫乐园 2022-05-23 19:09

问题描述:

有 n 个独立的作业算法一直没有找到最优解原因,由 m 个相同的机器处理。作业 i 所需的处理时间为 t。

任何作业都可以在任何机器上处理,但在完成之前不允许中断处理。任何工作都不能拆分成更小的工作。

需要一个作业调度方案,使得给定的n个作业可以在最短的时间内被m台机器处理。

算法分析:

使用处理时间最长的作业优先的贪心选择策略,可以设计出更好的近似算法来解决多机调度问题。

以 nm 为单位求解(作业数大于机器数)。

假设有7个独立作业,所需处理时间为{2,14,4,16,6,5,3},由M1、M2、M3三台机器处理。贪心算法生成的作业调度如下图所示算法一直没有找到最优解原因,需要的总处理时间为17

查看多机调度详情

我的问题是为什么这不是最佳解决方案。在什么情况下它不是最优解?因为书上说这只是一个近似解,所以它是这个例子的最优解

相关文章