【动态规划】流水作业调度问题与Johnson法则.docVIP

HYPERLINK /liufeng_king/article/details/8678316 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))aπ(1)+T’。这与π是N的最优调度矛盾。故T’=T(S,bπ(1))。从而T’=T(S,bπ(1))。这就证明了流水作业调度问题具有最优子结构的性质。 ???? 由流水作业调度问题的最优子结构性质可知: ???? ?????从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。将问题规模缩小。公式（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取max{t-ai,0}。 ?????3、动态规划法求解思路 ???? 假设有一组作业需要在M1和M2 两台机器上进行流水作业，他们在M1和M2上的作业时间如下表： ?????问题是如何安排他们的加工顺序，使得，到最后一个作业在机器M2上加工完成所需要的时间最少。也就是所有作业在两台机器全部加工完成所需的时间最少。?????思路如下：考虑如果只有一个作业的情况，肯定所需时间就是它自身需要在M1和M2 上的加工时间总和；如果有两个作业就要考虑在两种不同的加工顺序下选取最优的一种作为候选，三个作业的时会出现三种组合情况(0,(1,2)); (1,(0,2)); (2,(0,1)),拿第一种为例,它表示先加工作业0,然后再按照作业1和作业2的优化顺序加工;将三种的作业时间计算出来,取最小值,即为三个作业的优化结果,同理可对更多的作业进行排序优化。具体做法是，用类似矩阵连乘的办法，自底向上将所有能的情况计算出来，并产生一个表，供后面的计算查用，减少重复计算的工作量。 ?????对于j1 作业M2 的等待时间为b0,实际上在M2加工j0作业的同时，M1 并行加工j1,实际它需要等待b1-a0时间。 ??????2+4+(5-4)+2=9 ?????从J0和J1两个作业的加工顺序，可以看出，先加工J0后J1，所用时间最短为9，将其填入表中，依此类推，即可得出最优解。 ?????a4+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 ?????选其中加工时间短的作为候选方案；在具体计算时非最优子集不必考虑，这样可以减少计算次数。 ?????4、流水作业调度的Johnson法则 ???? 设兀是作业集S在机器M2的等待时间为t时的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是i 和j ，即π(1)=I,π(2)=j。则有动态规划递归式可得 ???? 其中 ?????如果作业i和j满足min{bi,aj} ≥min{bj,ai},则称作业i和j满足Johnson不等式。如果作业i和j 不满足Johnson不等式，则交换作业i和j满足