0018算法笔记——流水作业调度问题与Johnson法则.docx

0018算法笔记——流水作业调度问题与Johnson法则 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)) T’=min(b[c[i+1]],a[c[i]])其调度顺序最优； 红线右侧满足b[c[i]]=b[c[i+1]] 符合johnson 不等式，min(b[c[i]],a[c[i+1]])>=min(b[c[i+1]],a[c[i]])其调度顺序最优； 中间过渡部分横向比较，左侧a[c[i]]b[i]?b[i]:a[i];ob = a[i]i;j--){ 31.//如果前一个数大于后一个数，则交换 32.if(d[j]<=d[j-1]){ 33. temp = d[j]; 34. d[j] = d[j-1]; 35. d[j-1] = temp; 36. flag = 1; 37. } 38. } 39.//如果本次排序没有进行一次交换，则break，减少了执行之间。

40.if(flag == 0){ 41.break; 42. } 43. } 44.} 运行结果如下： 。