动态规划-流水作业调度报告.doc

《动态规划-流水作业调度报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划-流水作业调度报告C1问题描述和分析N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。设全部作业的集合为N={1,2,…,n},S⊆N,,一般情况下,机器M1开始加工作业S时,机器M2还在加工其他作业,要等时间t后才可利用.将这种情况下完成S中作业所需的最

2、短时间记为T(S,t).流水作业调度的最优值为T(N,0)即,设π是所给n个流水作业的一个最优调度,它所需的加工时间为a(π1)+T’.其中T’是在此机器M2的等待时间为b(π1)时,安排作业π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的最优调度

3、矛盾.故T’≤T(S,b(π1).从而T’=T(S,b(π1).即当机器M1为空闲即未安排任何加工任务时，则任何一个作业的第一个任务（第一道工序）都可以立即在M1上执行，无须任何先决条件。因此容易知道，必有一个最优调度使得在M1上的加工是无间断的。实际上，如某个最优调度π在M1上安排的加工是有间断的，则我们可以把所有在M1上出现间断处的任务的开始加工时间提前，使得在M1上的加工是无间断的；而在M2上仍按π原先的安排。把这样调整之后的调度记作为π’。由于在调度π’下，任何一个任务在M1上加工的结束时间不晚于在调度π下的结束时间，故调度π’不会

4、影响在M2上进行加工的任何一个任务的开始时间。由于调度π’在M1上的结束时间早于调度π，在M2上的结束时间与调度π相同，而π又是最优调度，所以π’也是最优调度。由此我们得到：一定有一个最优调度使得在M1上的加工是无间断的。另外，也一定有一个最优调度使得在M2上的加工空闲时间（从O时刻起算）为最小，同时还满足在M1上的加工是无间断的。（证明留作作业）因此，如果我们的目标是只需找出一个最优调度，我们可以考虑找：在M1上的加工是无间断的、同时使M2的空闲时间为最小的最优调度。（根据上述理由，这样的最优调度一定存在。）可以证明，若在M2上的加工次序

5、与在M1上的加工次序不同，则只可能增加加工时间（在最好情况下，增加的时间为O）。也就是说，在M1上的加工次序已确定的情况下，至少有一个最优调度，其在M1上的加工次序与在M2上的加工次序是完全相同的。因此，当只需找到一个最优调度时，我们仅需要考虑在和M1和M2上加工次序完全相同的调度。以下的讨论均以此为前提。为简化起见，我们假定所有ai≠0。因为如果有ai=0的作业，我们可以先对所有ai≠0的作业进行调度，然后把所有ai=0的作业放到最前面执行（可按任意次序）。最优调度具有如下性质：在所确定的最优调度的排列中去掉第一个执行作业后，剩下的作业排

6、列仍然还是一个最优调度，即该问题具有最优子结构的性质。而且，在计算规模为n的作业集合的最优调度时，该作业集合的子集合的最优调度会被多次用到，即该问题亦具有高度重复性。这就引导我们考虑用动态规划法求解C2算法设计递归计算最优值由流水作业调度问题的最优子结构性质可知,T(N,0)=min{ai+T(N-{i},bi)},其中1≤i≤n推到一般情形下便有T(S,t)=min{ai+T(S-{i},bi+max{t-ai,0})}其中,max{t-ai,0}这一项是由于在机器M2上,作业i须在max{t,ai}时间之后才能开工.因此,在机器M1上完

7、成作业i之后,在机器上还需要bi+max{t,ai}-ai=bi+max{t-ai,0}时间才能完成对作业i加工.而需要对算法作一定的改进。设π是作业子集S的某一个调度，该调度首先安排作业i，其次安排作业j，M2需等待t个时间单位以后才可以用于S中的作业加工。记t’=bi+max{t-ai,0}，则由（*）式调度π的g(S,t)可写为g(S,t)=ai+g(S-{i},t’)=ai+aj+g(S-{i,j},bj+max{t’-aj,0})。由于x+max{y1,y2,⋯,yn}=max{x+y1,x+y2,⋯,x+yn},，t’=bi+m

8、ax{t-ai,0}，所以bj+max{t’-aj,0}=bj+max{bi+max{t-ai,0}-aj,0}=bj+bi-aj+max{max{t-ai,0},aj-bi}=