贪心算法的思路是每次选择最优的策略,以期望能得到全局最优解。对于多机调度问题,一种常用的贪心策略是将作业按照处理时间从大到小排序,然后依次将作业分配给当前处理时间最短的机器。

按照这个策略,我们可以进行如下的步骤:

  1. 将作业按照处理时间从大到小排序:j4(16),j2(14),j5(6),j6(5),j3(4),j7(3),j1(2)。

  2. 创建三个列表分别用于记录每台机器的当前处理时间:machine1,machine2,machine3。

  3. 依次将作业分配给当前处理时间最短的机器。具体步骤如下:

    • 将j4分配给machine1,machine1的当前处理时间变为16。
    • 将j2分配给machine2,machine2的当前处理时间变为14。
    • 将j5分配给machine3,machine3的当前处理时间变为6。
    • 将j6分配给machine3,machine3的当前处理时间变为11。
    • 将j3分配给machine3,machine3的当前处理时间变为15。
    • 将j7分配给machine2,machine2的当前处理时间变为17。
    • 将j1分配给machine1,machine1的当前处理时间变为18。
  4. 最后,三台机器的最长处理时间即为总的完成时间。在这个例子中,最长处理时间为18,因此7个作业调度到三台机器后的最短完成时间为18。

需要注意的是,这个贪心算法并不能保证一定得到全局最优解,只能得到一个近似的解。要想得到全局最优解,需要使用其他算法,如动态规划

用贪心算法求解多机调度问题:设7个独立作业j1j2j3j4j5j6j7由三台机器M1M2M3加工处理各作业所需的处理时间分别为214416653求7个作业调度到三台机器后的最短完成时间

原文地址: https://www.cveoy.top/t/topic/hHvd 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录