流水作业调度问题.pdf

一、问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。二、算法分析n个作业{1,2,…,n}要在由2台机器M和M组成的流水线上完成加工。每个作业加工12的顺序都是先在M上加工，然后在M上加工。M和M加工作业i所需要的时间分别为1212t[i,1]和t[i,2],1in.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M上开始加工，到最后一个作业在机器M上加工完成所需的时间最少。12从直观上我们可以看到，一个最优调度应使机器M没有空闲时间，且机器M的空闲12时间是最少。在一般情况下，机器M上会有机器空闲和作业积压两种情况。2设全部作业的集合为N{1,2,....,n}。SN是N的作业子集。在一般情况下，机器M开始加工S中作业时，机器M还在加工其他作业，要等时间t后才能利用。将这种情12况下完成S中作业所需的最短时间计为T(S,t)。流水作业调度问题的最优解为T(N,0)。1.证明流水作业调度问题具有最优子结构设a是所给n个流水作业的一个最优调度，它所需要的加工时间为t[a(1),1]T'。其中，T'是在机器M的等待时间为t[a(1),2]时，安排作业a(2),a(3),......,a(n)所需2的时间。记SN{a(1)}，则我们可以得到T'T(S,t[a(1),2])。事实上，有T的定义可知T'T(S,t[a(1),2]).若T'T(S,t[a(1),2])，设a'是作业集S在机器M的等待时间为t[a(1),2]情况下的一个最优调度。则2a(1),a'(2),.....,a'(n)是N的一个调度且该调度所需的时间t[a(1),1]T(S,t[a(1),2])t[a(1),1]T'。这与a是N的一个最优调度矛盾，所以T'T(S,t[a(1),2])。从而T'T(S,t[a(1),2])。这就是证明了流水作业调度问题具有最优子结构的性质。2.建立递归式计算最优解由流水作业调度问题的最优子结构的性质我们可以得到，T(N,0)min{t[i,1]T(N{i},t[i,2])}。推广到更一般的情形，我们便有：1inT(S,t)min{t[i,1]T(S{i},t[i,2]max{tt[i,1],0})}。其中，max{tt[i,1],0}这iS一项是由于机器M上，作业i需在max{t,t[i,1]}时间之后才能开工。因此，在机器M21上完成作业i之后，在机器上还需t[i,2]max{t,t[i,1]}t[i,1]t[i,2]max{tt[i,1],0}时间才能完成对作业i的加工。按照上面所叙述的递归式，可以设计出解决流水作业调度问题的动态规划算法。通过对递归式的分析，算法可以得到进一步的改进。3.流水调度问题的Johnson法则设a是作业集S在机器M的等待时间为t时的任意一个最优调度。如果在调度中，2安排在最前面的两个作业分别为i和j，即a(1)i,a(2)j。则由动态规划的递归式可以得到：T(S,t)t[i,1]T(S{i},bmax{tt[i,1],0})t[i,1]t[j,1]T(S{i,j},t)iij其中，tt[j,2]max{t[i,2]max{tt[i,1],0}t[j,1],0}ijt[j,2]t[i,2]t[j,1]max{max{tt[i,1],0},0,t[j,1]t[i,2]}t[j,2]t[i,2]t[j,1]max{tt[i,1],t[j,1]t[i,2],0}t[j,2]t[i,2]t[j,1]t[i,1]max{t,t[i,1]t[j,1]t[i,2],t[i,1]}如果作业i和j满足min{t[i,2],t[j,1]}min{t[j,2],t[i,1]}，则称作业i和j满足Johnson不等式。如果作业i和j不满足Johnson不等式，则交换作业i和j的加工次序后，作业i和j满足Johnson不等式。在作业集S当机器M的等待时间为t时的调度a中，交换作业i和作业j的加工次2序，得到的作业集S的另一个调度a’，它所需要的加工时间为T'(S,t)t[i,1]t[j,1]T(S{i,j},t)。ji其中，tt[j,2]t[i,2]t[j,1]t[i,1]max{t,t[i,1]t[j,1]t[j,2],t[j,1]}ji当作业i和j满足Johnson不等式min{t[i