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

动态规划-流水作业调度报告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中作业所需的最短时间记为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的最优调度矛盾.故T’≤T(S,b(π1).从而T’=T(S,b(π1).即当机器M1为空闲即未安排任何加工任务时，则任何一个作业的第一个任务（第一道工序）都可以立即在M1上执行，无须任何先决条件。因此容易知道，必有一个最优调度使得在M1上的加工是无间断的。实际上，如某个最优调度π在M1上安排的加工是有间断的，则我们可以把所有在M1上出现间断处的任务的开始加工时间提前，使得在M1上的加工是无间断的；而在M2上仍按π原先的安排。把这样调整之后的调度记作为π’。由于在调度π’下，任何一个任务在M1上加工的结束时间不晚于在调度π下的结束时间，故调度π’不会影响在M2上进行加工的任何一个任务的开始时间。由于调度π’在M1上的结束时间早于调度π，在M2上的结束时间与调度π相同，而π又是最优调度，所以π’也是最优调度。由此我们得到：一定有一个最优调度使得在M1上的加工是无间断的。另外，也一定有一个最优调度使得在M2上的加工空闲时间（从O时刻起算）为最小，同时还满足在M1上的加工是无间断的。（证明留作作业）因此，如果我们的目标是只需找出一个最优调度，我们可以考虑找：在M1上的加工是无间断的、同时使M2的空闲时间为最小的最优调度。（根据上述理由，这样的最优调度一定存在。）可以证明，若在M2上的加工次序与在M1上的加工次序不同，则只可能增加加工时间（在最好情况下，增加的时间为O）。也就是说，在M1上的加工次序已确定的情况下，至少有一个最优调度，其在M1上的加工次序与在M2上的加工次序是完全相同的。因此，当只需找到一个最优调度时，我们仅需要考虑在和M1和M2上加工次序完全相同的调度。以下的讨论均以此为前提。为简化起见，我们假定所有ai≠0。因为如果有ai=0的作业，我们可以先对所有ai≠0的作业进行调度，然后把所有ai=0的作业放到最前面执行（可按任意次序）。最优调度具有如下性质：在所确定的最优调度的排列中去掉第一个执行作业后，剩下的作业排列仍然还是一个最优调度，即该问题具有最优子结构的性质。而且，在计算规模为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上完成作业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+max{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}=bj+bi-aj+max{t-ai,0,aj-bi}=bj+bi-aj-ai+max{t,ai,ai+aj-bi}。记tij=bj+bi-aj-ai+max{t,ai,ai+aj-bi}（=bj+max{t’-aj,0}），则调度π的g(S,t)=ai+aj+g(S-{i,j},tij)。将调度π中的作业i与j的加工次序交换（其它加工次序不变）所得调度记为π’，则调度π’的最早完工时间g’(S,t)=ai+aj+g(S-{i,j},tji)。显然，若tij≤tji，则有g(S,t)≤g’(S,t)即i在前j在后的安排用时较少；反之，若tijtji，则j在前i在后的安排用时较少。因此，我们要找出判断tij与tji之间的大小关系的表达式。由于tij-tji=max{t,ai,ai+aj-bi}-max{t,aj,ai+aj-bj}，故我们只要比较max{t,ai,ai+aj-bi}与max{t,aj,ai+aj-bj}的大小就可以了,即tij≤tji当且仅当max{t,ai,ai+aj-bi}≤max{t,aj,ai+aj-bj}。由于max{t,ai,ai+aj-bi}≤max{t,aj,ai+aj-bj}对任何t≥0成立，当且仅当max{ai,ai+aj-bi}≤max{aj,ai+aj-bj}成立，当且仅当ai+aj+max{-aj,-bi}≤ai+aj+max{-ai,-bj}成立，当且仅当max{-aj,-bi}≤max{-ai,-bj}成立，当且仅当min{aj,bi}≥min{ai,bj}成立。即当min{ai,aj,bi,bj}为ai或者bj时，Johnson不等式成立，此时把i排在前j排在后的调度用时较少；反之，若min{ai,aj,bi,bj}为aj或者bi时，则j排在前i排在后的调度用时较少。将此情况推广到一般。当min{a1,a2,┅,an,b1,b2,┅,bn}=ak时，则对任何i≠k，都有min{ai,bk}≥min{ak,bi}成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业；当min{a1,a2,┅,an,b1,b2,┅,bn}=bk时，则对任何i≠k，也都有min{ak,bi}≥min{ai,bk}成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业。C4程序实现主要程序classJobtype{public:intoperator=(Jobtypea)const{return(key=a.key);}intkey;intindex;booljob;};intFlowShop(intn,inta[],intb[],intc[]){Jobtype*d=newJobtype[n];for(inti=0;in;i++){d[i].key=a[i]b[i]?b[i]:a[i];d[i].job=a[i]=b[i];d[i].index=i;}MergeSort(d,n);//对n个作业进行排序intj=0,k=n-1;for(i=0;in;i++){if(d[i].job)c[j++]=d[i].index;//选定作业的加工顺序elsec[k--]=d[i].index;}//记住进行加工作业所用的时间j,kj=a[c[0]];k=j+b[c[0]];for(i=1;in;i++){j+=a[c[i]];k=jk?k+b[c[i]]:j+b[c[i]];}cout最优加工顺序endl;for(intg=0;gn;g++){coutg+1[a[c[g]],b[c[g]]];}coutendl;//输出最优加工顺序cout最优调度所用的时间endl;coutkendl;//输出最优调度所用的时间deleted;returnk;}voidmain(){intc[20];intn;int*a,*b;ifstreamfin(data.txt);finn;make1darray(a,n+1);make1darray(b,n+1);for(inti=0;in;i++){fina[i]b[i];}cout原来的加工顺序endl;for(i=0;in;i++){couti+1[a[i],b[i]];}coutendl;FlowShop(n,a,b,c);}C5算法复杂性分析由于合并排序需要O(nlogn)时间,对数组a[n],b[n],c[n]进行初始化都是用了O(n)本程序,下标变量初始化：i←0；j←0；k←n-1;是O(1),主要有3个循环语句而且用时是都是O(n),∴算法的时间复杂度为O(nlogn)