流水作业调度问题 性质证明

假设有n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

在一般情况下，M1在加工作业集合S中的一个作业时，M2还在加工上一个作业，此时假设M2还需要时间t才能完成上个作业。这种情况下完成作业集合S中所有作业所需的最短时间记为T(S, t)。 

π是给n个流水作业的最优调度，所需的最短时间为T(N, t) = aπ(1) + T'，其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所i的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

流水作业调度问题的最优子结构性质证明如下：

T'是对作业π(2)，…，π(n)安排后完成的时间，显然T'是大于等于对这些作业最优调度后所需要的时间T(S,bπ(1))的。当T'>T(S,bπ(1))时，设π'是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))。根据T'>T(S,bπ(1))的不等式传导性，可以得知aπ(1)+T(S,bπ(1))<aπ(1)+T’。而aπ(1)+T’=T(S, t)，是对作业全’集N的最优调度，因此，T(S, t)也应该是最小的。进而T'>T(S,bπ(1))是不成立的。最终得到T'只可能等于T(S,bπ(1))，也就是说，即便在对于全集N的一个最优调度中，它的子集也满足最优调度。因此流水作业调度问题具有最优结构的性质。