流水作业调度

问题描述

$n$ 个作业 $N = \{ 1, 2, \cdots, n \}$ 要在 2 台机器 $M_1$ 和 $M_2$ 组成的流水线上完成加工。每个作业须先在 $M_1$ 上加工，然后在 $M_2$ 上加工。$M_1$ 和 $M_2$ 加工作业 $i$ 所需的时间分别为 $a_i$ 和 $b_i$ ，每台机器同一时间最多只能执行一个作业。

流水作业调度问题要求确定这 $n$ 个作业的最优加工顺序，使得所有作业在两台机器上都加工完成所需最少时间。

问题分析

• 一定存在最优调度使 $M_1$ 上的加工是无间断的，即 $M_1$ 上的总加工时间是所有 $a_i$ 之和，$M_2$ 上不一定是 $b_i$ 之和。
• 一定存在最优调度使作业在两台机器上的加工次序是完全相同的。因为若是 $b_i$ 和 $b_j$ 交换，则 $b_j$ 需要 $a_j$ 结束，等待时间更长。因此仅需考虑在两台机上加工次序完全相同的调度。

设 $S \subseteq N$ 为 $n$ 个作业的子集。机器 $M_1$ 开始加工 $S$ 中的作业时，机器 $M_2$ 还在加工其他作业，要等时间 $t$ 后才可利用。

于是我们设完成 $S$ 中作业所需的最短时间为 $T(S, t)$，则完成所有作业所需的最短时间为 $T(N, 0)$。基于此定义，容易得出状态转移方程：

$$\begin{aligned} T(S, t) = a_i + T(S - \{i\}, b_i + \max \{t - a_i, 0\}) \end{aligned}$$

其中，$a_i$ 表示选择一个作业 $i$ 先加工，在 $M_1$ 加工的时间。而后面剩下的作业 $S - \{i\}$ 要等在作业 $i$ 之前的所有作业加工完（等待 $\max \{t - a_i, 0\}$ 时间），并且作业 $i$ 也加工完（等待 $b_i$ 时间）才能在 $M_2$ 加工。

然而，虽然满足最优子结构性质，也在一定程度满足子问题重叠性质，但是 $N$ 的每个非空子集都计算一次，共 $2^n-1$ 次，具有指数级的时间复杂度。

Johnson 不等式

如果作业 $i$ 和 $j$ 满足 $\min \{ b_i, a_j \} \geqslant \min \{ b_j, a_i \}$，则称作业 $i$ 和 $j$ 满足 Johnson 不等式。

Johnson 不等式的意义在于，只要满足 Johnson 不等式，那么任务 $i$ 应在任务 $j$ 之前。推广到一般情况：

• 当 $\min \{ a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n \} = a_i$ 时，对 $\forall k \ne i$ 都有 $\min \{ b_i, a_k \} \geqslant \min \{ b_k, a_i \}$，那么应将任务 $i$ 安排在最前面。
• 当 $\min \{ a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n \} = b_j$ 时，对 $\forall k \ne j$ 都有 $\min \{ b_k, a_j \} \geqslant \min \{ b_j, a_k \}$，那么应将任务 $j$ 安排在最后面。

Johnson 不等式确定了流水作业的处理顺序，不需要指数级的时间即可求解。