Johnson算法是一种用于解决两台机器上的作业调度问题的算法,目标是使得完成所有作业的总时间最短。
Johnson算法的步骤如下:
将每个作业分为两个操作,分别在两台机器上执行。给每个操作编号,例如,第一台机器上的操作为1,2,3…,第二台机器上的操作为4,5,6…。
根据每个操作在两台机器上的处理时间,计算第一台机器上的作业完成时间和第二台机器上的作业完成时间,分别记为TA和TB。
比较第一台机器上的作业完成时间和第二台机器上的作业完成时间。如果TA<TB,则选择第一台机器上的操作作为下一个执行的操作,并将其从待调度的作业列表中移除。如果TA>TB,则选择第二台机器上的操作作为下一个执行的操作,并将其从待调度的作业列表中移除。
重复步骤3,直到所有的操作都被执行完毕。
根据操作的执行顺序计算作业的完成时间。
通过以上步骤,可以得到Johnson算法求解出的最优顺序。