流水线作业调度问题及Johnson法则

简介：
本文章探讨了流水线作业调度的问题，并深入分析了解决此类问题的经典算法——Johnson法则，提供了理论与实践相结合的有效解决方案。 流水作业调度问题涉及在由多台机器组成的流水线上安排作业的加工顺序，以确保从第一个作业开始在第一台机器（M1）上进行加工到最后一个作业完成于第二台机器（M2）上的时间最短。这个问题可以通过分解为更小的问题来解决，并且可以使用动态规划法。 具体来说，在由两台特定机器组成的流水线上有n个需要处理的作业{1，2，…，n}。每个作业必须先在第一台机器上加工然后转移到第二台机器继续加工；M1和M2完成第i项工作所需的时间分别为ai 和 bi。目标是确定这 n 个作业的最佳排序方式，以使从第一个作业开始到最后一个作业结束的总时间最短。 为了分析这个问题，我们定义 T(S,t) 表示当第一台机器 M1 开始加工某个子集 S 的作业时第二台机器还需要额外的时间 t 才能完成当前正在处理的工作。流水作业调度问题的最佳解即为 T(N,0)，其中 N 是所有需要安排的作业集合。 动态规划法可以用来解决这个问题，其基本思路是：如果有单一工作，则所需时间等于该工作在M1和M2上的加工总时长；若有两个工作则需考虑两种不同的排列顺序，并选取最优的一种作为候选。随着处理的工作数量增加至三个或更多，每种可能的组合都需要被评估并选择最小的时间消耗方案。 Johnson法则提供了一种解决流水作业调度问题的方法，它通过将大问题分解为一系列较小的问题来简化计算过程。这种方法利用动态规划技术解决了这些子问题，并最终给出了所有工作以最短时间完成的最佳排序方式。 综上所述，我们可以通过应用动态规划法和 Johnson 法则有效地解决流水作业调度问题，从而找到使得从第一个作业开始于第一台机器到最后一个作业结束于第二台机器的时间最小化的加工顺序。