流水作业调度问题 8页

一、问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。二、算法分析n个作业{1,2,…,n}要在由2台机器和组成的流水线上完成加工。每个作业加工的顺序都是先在上加工，然后在上加工。和加工作业所需要的时间分别为t[i,1]和t[i,2],.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器上开始加工，到最后一个作业在机器上加工完成所需的时间最少。从直观上我们可以看到，一个最优调度应使机器没有空闲时间，且机器的空闲时间是最少。在一般情况下，机器上会有机器空闲和作业积压两种情况。设全部作业的集合为。是的作业子集。在一般情况下，机器开始加工中作业时，机器还在加工其他作业，要等时间t后才能利用。将这种情况下完成中作业所需的最短时间计为。流水作业调度问题的最优解为。1.证明流水作业调度问题具有最优子结构设a是所给n个流水作业的一个最优调度，它所需要的加工时间为。其中，是在机器的等待时间为时，安排作业所需的时间。记，则我们可以得到。n事实上，有T的定义可知.若，设是作业集在机器的等待时间为情况下的一个最优调度。则是的一个调度且该调度所需的时间。这与a是N的一个最优调度矛盾，所以。从而。这就是证明了流水作业调度问题具有最优子结构的性质。1.建立递归式计算最优解由流水作业调度问题的最优子结构的性质我们可以得到，。推广到更一般的情形，我们便有：。其中，这一项是由于机器上，作业需在时间之后才能开工。因此，在机器上完成作业之后，在机器上还需时间才能完成对作业的加工。按照上面所叙述的递归式，可以设计出解决流水作业调度问题的动态规划算法。通过对递归式的分析，算法可以得到进一步的改进。2.流水调度问题的Johnson法则设a是作业集S在机器的等待时间为t时的任意一个最优调度。如果在调度中，安排在最前面的两个作业分别为i和j，即。则由动态规划的递归式可以得到：其中，n如果作业i和j满足，则称作业i和j满足Johnson不等式。如果作业i和j不满足Johnson不等式，则交换作业i和j的加工次序后，作业i和j满足Johnson不等式。在作业集S当机器的等待时间为t时的调度a中，交换作业i和作业j的加工次序，得到的作业集S的另一个调度a’，它所需要的加工时间为。其中，当作业i和j满足Johnson不等式时，我们有从而，由此可得，因此任意t有从而，。由此可见。换句话说，当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，作业i和作业j就满足Johnson不等式了，且不增加加工时间。由此可得，对于流水作业调度问题，必存在一个最优的调度a，使得作业和满足Johnson不等式：，称这样的调度a为满足Johnson法则的调度。n进一步可以证明，调度a满足Johnson法则当且仅当对任意的i和j都有i。所以此时要想把1，4做完，需要14（7+7）个时间。执行5时：M1上运行6个时间后，M2还在继续运行4，并没有结束。M1的结束时间为12，而M2结束4的时间为14，即<12,14>.所以此时要想把1，4，5做完，需要23（14+9）个时间。执行2时：M1上运行7个时间后，M2还在继续运行5，并没有结束。M1的结束时间为19，而M2结束5的时间为23，即<19,23>.所以此时要想把1，4，5，2做完，需要26（23+3）个时间。n执行6时：M1上运行8个时间后，M2已经不在继续运行2。M1的结束时间为27，而M2结束2的时间为26，即此时M2已经空闲了一个时间，即<27,26>.所以此时要想把1，4，5，2，6完成，需要29（27+2）个时间。执行3时：M1上运行6个时间后，M2已经不在继续运行6。M1的结束时间为33，而M2结束6的时间为29，即此时M2已经空闲了3个时间，即<33,29>.所以此时要想把1，4，5，2，6，3完成，需要35（33+2）个时间。所以，根据运行结果，作业执行时间为35.（当输入为7的情形与输入为6的类似，这里就不再叙述）