流水作业调度问题.docx

问题描述
给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。
算法分析
n个作业{1,2,…,n}要在由2台机器和组成的流水线上完成加工。每个作业加工的顺序都是先在上加工，然后在上加工。和加工作业所需要的时间分别为t[i,1]和t[i,2],.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器上开始加工，到最后一个作业在机器上加工完成所需的时间最少。
从直观上我们可以看到，一个最优调度应使机器没有空闲时间，且机器的空闲时间是最少。在一般情况下，机器上会有机器空闲和作业积压两种情况。
设全部作业的集合为。是的作业子集。在一般情况下，机器开始加工中作业时，机器还在加工其他作业，要等时间t后才能利用。将这种情况下完成中作业所需的最短时间计为。流水作业调度问题的最优解为。
证明流水作业调度问题具有最优子结构
设a是所给n个流水作业的一个最优调度，它所需要的加工时间为。其中，是在机器的等待时间为时，安排作业所需的时间。
记，则我们可以得到。
事实上，有T的定义可知.若，设是作业集在机器的等待时间为情况下的一个最优调度。则是的一个调度且该调度所需的时间。这与a是N的一个最优调度矛盾，所以。从而。这就是证明了流水作业调度问题具有最优子结构的性质。
建立递归式计算最优解
由流水作业调度问题的最优子结构的性质我们可以得到，。推广到更一般的情形，我们便有：。其中，这一项是由于机器上，作业需在时间之后才能开工。因此，在机器上完成作业之后，在机器上还需时间才能完成对作业的加工。
按照上面所叙述的递归式，可以设计出解决流水作业调度问题的动态规划算法。通过对递归式的分析，算法可以得到进一步的改进。
流水调度问题的Johnson法则
设a是作业集S在机器的等待时间为t时的任意一个最优调度。如果在调度中，安排在最前面的两个作业分别为i和j，即。则由动态规划的递归式可以得到：

其中，

如果作业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法则的调度。
进一步可以证明，调度a满足Johnson法则当且仅当对任意的i和j都有i<j时有。由此可知，任意两个满足Johnson法则的调度均为最优调度。至此，我们将流水调度问题转化为求满足Johnson法则的调度问题。
算法的描述
从上面的分析可知，流水作业调度问题一定存在满足Johnson法则的最优调度，且容易由下面的算法确定。
流水作业调度问题的Johnson算法：
令；
将中作业依的非减序排列；将中作业依的非增序排列；
作业接种作业构成满足Johnson法则的最优调度。
具体的代码在文件夹《流水作业调度——动态规划法》文件夹中。
时空效率分析
算法FlowJob的主要计算时间花在对作业集的排序上。在这里，我们使用冒泡排序法(BubbleSort)，因此，在最坏情况下算法FlowJob所需要的计算时间为。所需要的空闲显然是。
运行结果

当输入的作业数目为6时的运行结果

当输入的作业数为8时的运行结果

分析输出结果
当输入的作业数目为6时：
每个作业在M1上执行的时间为，在M2上执行的时间为，输入的数据为：
作业序123456276468532792算法按照先执行的作业，保证M2机器上没有等待，本例中作业1、4、5满足条件，被选择先执行。当选择第一个作业时，算法选择让M2第一次等待时间最少的那个，本例中作业1的最小，这样就可以让M2第一次等待最少。所以在的集合中，越小越靠前执行。
当执行的作业时，要保证最后一个作业在M2上的执行时间最短，所以作业2，6，3是按照非增序排列，保证了作业3的是它们三个当中最小的一个。
算法在计算执行时间的过程如下图所示：

作业执行次序为：1，4，5，2，6，3.
执行1时：M1上运行2