johnson算法最优顺序怎么算

小亿
356
2023-08-01 09:23:37
栏目: 编程语言

Johnson算法是一种用于解决两台机器上的作业调度问题的算法,目标是使得完成所有作业的总时间最短。

Johnson算法的步骤如下:

  1. 将每个作业分为两个操作,分别在两台机器上执行。给每个操作编号,例如,第一台机器上的操作为1,2,3…,第二台机器上的操作为4,5,6…。

  2. 根据每个操作在两台机器上的处理时间,计算第一台机器上的作业完成时间和第二台机器上的作业完成时间,分别记为TA和TB。

  3. 比较第一台机器上的作业完成时间和第二台机器上的作业完成时间。如果TA<TB,则选择第一台机器上的操作作为下一个执行的操作,并将其从待调度的作业列表中移除。如果TA>TB,则选择第二台机器上的操作作为下一个执行的操作,并将其从待调度的作业列表中移除。

  4. 重复步骤3,直到所有的操作都被执行完毕。

  5. 根据操作的执行顺序计算作业的完成时间。

通过以上步骤,可以得到Johnson算法求解出的最优顺序。

0
看了该问题的人还看了