C 程序-流水作业调度.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所需要的计算时间为。所需要的空闲显然是。

//FlowOperation.h

#ifndefFLOWOPERATION_H
#defineFLOWOPERATION_H

classFlowOperation
{
public:
FlowOperation();
~FlowOperation();
voidrun();//运行接口
private:
intnumber;//流水作业个数
intnumberB;//记录N1的个数
intnumberC;//记录N1的个数
int**a;//存储流水作业时间
int**b;//N1（Ai<Bi）
int**c;//N2（Ai>=Bi）

boolinput();//输入接口
boolsort();//X=0orX=1快速排序目的是满足Johnson不等式min(Bi