动态规划 流水线作业调度的最优子结构证明不明白
1、问题描述:
n个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。
2、问题分析
直观上,一个最优调度应使机器M1没有空闲时间,且机器M2的空闲时间最少。在一般情况下,机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1,2,…,n}。S是N的作业子集。在一般情况下,机器M1开始加工S中作业时,机器M2还在加工其他作业,要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。
设π是所给n个流水作业的一个最优调度,它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时,安排作业π(2),…,π(n)所需的时间。
记S=N-{π(1)},则有T’=T(S,bπ(1))。
证明:事实上,由T的定义知T’>=T(S,bπ(1))。若T’>T(S,bπ(1)),设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。则π(1),π'(2),…,π'(n)是N的一个调度,且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。这与π是N的最优调度矛盾。故T’<=T(S,bπ(1))。从而T’=T(S,bπ(1))。这就证明了流水作业调度问题具有最优子结构的性质。
1. 由T的定义知T’>=T(S,bπ(1))。
看定义而这好像是相等啊?怎么得出T’>=T(S,bπ(1))?
2.若T’>T(S,bπ(1)),设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度
为什么?
3.T’=T(S,bπ(1))。这就证明了流水作业调度问题具有最优子结构的性质。?
二者相等为什么说明具有最优子结构性质?
这些部分不是很懂。望指点。
[解决办法]