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

流水作业调度问题是指在一个流水线上有多个作业需要完成，并且每一个作业都需要经过一系列的加工工序。流水作业调度问题的目标是找到一种方法，使得作业的完成时间最短。
Johnson法则是一种经常使用的解决流水作业调度问题的方法。它可以将流水作业调度问题转化为两个机器的调度问题。具体的步骤以下：
1. 将所有的作业依照各个工序的处理时间从小到大排序，得到一个排序后的作业序列。
2. 创建两个空的作业序列，分别代表机器1和机器2的作业序列。
3. 从排序后的作业序列当选择一个处理时间最小的作业，将其分配给机器1。
4. 从排序后的作业序列当选择一个处理时间最小的作业，将其分配给机器2。
5. 重复步骤3和步骤4，直到所有的作业都被分配完。
6. 将机器1的作业序列和机器2的作业序列合并，得到终究的作业调度序列。
Johnson法则的优点是简单易懂，并且在某些情况下可以得到最优解。但是它也有一些限制，例如只适用于两个机器的情况，对多个机器的情况需要使用其他的算法。另外，Johnson法则也不能保证在所有情况下都可以得到最优解。