流水作业调度

问题描述

$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{array}{r}T(S,t)=a_i+T(S-\{i\},b_i+max\{t-a_i,0\})\end{array}$$

其中，$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\}⩾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$ 时，对 $\mathrm{\forall }k\ne i$ 都有 $min\{b_i,a_k\}⩾min\{b_k,a_i\}$，那么应将任务 $i$ 安排在最前面。
• 当 $min\{a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n\}=b_j$ 时，对 $\mathrm{\forall }k\ne j$ 都有 $min\{b_k,a_j\}⩾min\{b_j,a_k\}$，那么应将任务 $j$ 安排在最后面。

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