流水作业调度问题与Johnson法则

流水作业调度问题是指在一个流水线上有多个作业需要完成，并且每个作业都需要经过一系列的加工工序。流水作业调度问题的目标是找到一种方法，使得作业的完成时间最短。

Johnson法则是一种常用的解决流水作业调度问题的方法。它可以将流水作业调度问题转化为两个机器的调度问题。具体的步骤如下：

1. 将所有的作业按照各个工序的处理时间从小到大排序，得到一个排序后的作业序列。

2. 创建两个空的作业序列，分别代表机器1和机器2的作业序列。

3. 从排序后的作业序列中选择一个处理时间最小的作业，将其分配给机器1。

4. 从排序后的作业序列中选择一个处理时间最小的作业，将其分配给机器2。

5. 重复步骤3和步骤4，直到所有的作业都被分配完。

6. 将机器1的作业序列和机器2的作业序列合并，得到最终的作业调度序列。

Johnson法则的优点是简单易懂，并且在某些情况下可以得到最优解。但是它也有一些限制，例如只适用于两个机器的情况，对于多个机器的情况需要使用其他的算法。此外，Johnson法则也不能保证在所有情况下都可以得到最优解。