问题描述：n 个作业{ 1，2，…，n}要在由 2 台机器 M1 和 M2 组成的流
水线上完成加工。每个作业加工的顺序都是先在 M1 上加工，然后在 M2 上加
工。M1 和 M2 加工作业 i 所需的时间分别为 ai 和 bi。流水作业调度问题要求
确定这 n 个作业的最优加工顺序，使得从第一个作业在机器 M1 上开始加工，
到最后一个作业在机器 M2 上加工完成所需的时间最少。
分析：直观上，一个最优调度应使机器 M1 没有空闲时间，且机器 M2 的
空闲时间最少。在一般情况下，机器 M2 上会有机器空闲和作业积压 2 种情况。
动态规划求解上述问题
定义：设全部作业的集合为 N={ 1，2，…，n}。S⊆N 是 N 的作业子集。在
一般情况下，机器 M1 开始加工 S 中作业时，机器 M2 还在加工其它作业，要等
时间 t 后才可利用。将这种情况下完成 S 中作业所需的最短时间记为 T(S,t)，那
么流水作业调度问题的最优值为 T(N,0)。
证明：上述问题具有动态规划算法的最优子结构性质
设
π= ¿ π
(
1
)
, π
(
2
)
,⋯ , π
(
i
)
,⋯ , π (n)>¿
（其中
π
(
i
)
∈ N
）是所给 n 个流水作业的
一个最优调度，它所需的加工时间为 a
π
(
1
)
+T’。其中 T’是在机器 M2 的等待时间
为 b
π
(
1
)
时，安排作业
π
(
2
)
, π
(
3
)
, π
(
4
)
,⋯ , π
(
n
)
所需的时间。记 S=N-{
π
(
1
)
}，则有
T’=T(S,b
π
(
1
)
)。
证：因以最优调度
π
加工作业时需用时 a
π
(
1
)
+T’，此时总时间最少，但是并
不意味着 T’时间所对应的调度(对作业
π
(
2
)
, π
(
3
)
, π
(
4
)
,⋯ , π
(
n
)
的调度)一定是最优
的，而作业
π
(
2
)
, π
(
3
)
, π
(
4
)
,⋯ , π
(
n
)
对应的最优调度用时为 T(S,b
π
(
1
)
，因此原则上
T’
≥
T(S,b
π
(
1
)
。若 T’
¿
T(S,b
π
(
1
)
，设
π ’
是作业集 S 在机器 M2 的等待时间为 b
π
(
1
)
