作业调度问题2

《作业调度问题2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业调度问题的优化算法西北第二民族学院计算机科学与技术系王伦津流水作业调度的动态规划算法批处理作业调度分支限界法多机调度问题的贪心算法批处理作业调度回溯算法问题的提出：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。一、流水作业调度分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少

2、。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1，2，…，n}。SN是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)

3、)。若T’>T(S,b(1))，设’是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)，’(2)，…，’(n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1))

4、择方案。将问题规模缩小。（1）（2）公式（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取max{t-ai,0}。流水作业调度实例：假设有一组作业需要在M1和M2两台机器上进行流水作业，他们在M1和M2上的作业时间如下表：M1M2J025J142J233J361J417问题是如何安排他们的加工顺序，使得，到最后一个作业在机器M2上加工完成所需要的时间最少。也就是所有作业在两台机器全部加工完成所需的时间最少。解决问题的思路是：考虑如果

5、只有一个作业的情况，肯定所需时间就是它自身需要在M1和M2上的加工时间总和；如果有两个作业就要考虑在两种不同的加工顺序下选取最优的一种作为候选，三个作业的时会出现三种组合情况(0,(1,2));(1,(0,2));(2,(0,1)),拿第一种为例,它表示先加工作业0,然后再按照作业1和作业2的优化顺序加工;将三种的作业时间计算出来,取最小值,即为三个作业的优化结果,同理可对更多的作业进行排序优化。本例的具体做法是，用类似矩阵连乘的办法，自底向上将所有能的情况计算出来，并产生一个表，供后面的计算查用，减少重复计算的工作量。j0j1j2j3j4j079121619j169j

6、2610j379j48M1M2J025J142J233J361J417从J0和J1两个作业的加工顺序，可以看出，先加工J0后J1，所用时间最短为9，将其填入表中，依此类推，即可得出最优解。4+2+(2-2)+5=112+4+(5-4)+2=9所花费时间分别为a0+a1+(b0-a1)+b1或a1+a0+(b1-a0)+b0令p=a0+a1+b0+b1则有P-a1或p-a0取其最小值对于j1作业M2的等待时间为b0,实际上在M2加工j0作业的同时，M1并行加工j1,实际它需要等待b1-a1时间(a)12(b)14(c)13(d)12(e)15(f)14a0+a1+a2+a

7、3+b3=2+4+3+6+1=16a0+a2+a1+a3+b3=16a4+a0+a2+a1+a3+[(b4+b0+b1+b2)-(a0+a1+a2+a3)]+b3=1+2+3+4+6+[(7+5+2+3)-(2+4+3+6)]+1=16+[17-15]+1=19分析上页图(c)和图(f)是在原作业0和作业1的基础上，增加作业2，从两者的最优方案(c)中，先执行作业2，作业0在M2机器上加工的等待时间，原先为0，由于作业2的加入且b2>a0,因此等待时间增加了b2-a0,总加工时间为13，而在(a)图中后执行作业2，总作业时间为12；图（b