流水作业调度

问题描述

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

其中,$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 不等式确定了流水作业的处理顺序,不需要指数级的时间即可求解。

Previous
Next