C++程序-流水作业调度.doc

一、 问题描述给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为ti,j。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。二、 算法分析n个作业1,2,n要在由2台机器和组成的流水线上完成加工。每个作业加工的顺序都是先在上加工，然后在上加工。和加工作业所需要的时间分别为ti,1和ti,2, .流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器上开始加工，到最后一个作业在机器上加工完成所需的时间最少。从直观上我们可以看到，一个最优调度应使机器没有空闲时间，且机器的空闲时间是最少。在一般情况下，机器上会有机器空闲和作业积压两种情况。设全部作业的集合为。是的作业子集。在一般情况下，机器开始加工中作业时，机器还在加工其他作业，要等时间t后才能利用。将这种情况下完成中作业所需的最短时间计为。流水作业调度问题的最优解为。1. 证明流水作业调度问题具有最优子结构设a是所给n个流水作业的一个最优调度，它所需要的加工时间为。其中，是在机器的等待时间为时，安排作业所需的时间。记，则我们可以得到。事实上，有T的定义可知.若，设是作业集在机器的等待时间为情况下的一个最优调度。则是的一个调度且该调度所需的时间。这与a是N的一个最优调度矛盾，所以。从而。这就是证明了流水作业调度问题具有最优子结构的性质。2. 建立递归式计算最优解由流水作业调度问题的最优子结构的性质我们可以得到，。推广到更一般的情形，我们便有：。其中，这一项是由于机器上，作业需在时间之后才能开工。因此，在机器上完成作业之后，在机器上还需时间才能完成对作业的加工。按照上面所叙述的递归式，可以设计出解决流水作业调度问题的动态规划算法。通过对递归式的分析，算法可以得到进一步的改进。3. 流水调度问题的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都有ij时有。由此可知，任意两个满足Johnson法则的调度均为最优调度。至此，我们将流水调度问题转化为求满足Johnson法则的调度问题。4. 算法的描述从上面的分析可知，流水作业调度问题一定存在满足Johnson法则的最优调度，且容易由下面的算法确定。流水作业调度问题的Johnson算法：（1） 令；（2） 将中作业依的非减序排列；将中作业依的非增序排列；（3） 作业接种作业构成满足Johnson法则的最优调度。具体的代码在文件夹流水作业调度动态规划法文件夹中。三、 时空效率分析 算法FlowJob的主要计算时间花在对作业集的排序上。在这里，我们使用冒泡排序法(BubbleSort)，因此，在最坏情况下算法FlowJob所需要的计算时间为。所需要的空闲显然是。/ FlowOperation.h#ifndef FLOWOPERATION_H#define FLOWOPERATION_Hclass FlowOperationpublic:FlowOperation();FlowOperation();void run(); / 运行接口private:int number; / 流水作业个数int numberB; / 记录N1的个数int numberC; / 记录N1的个数int *a; / 存储流水作业时间int *b; / N1（Ai=Bi）bool input(); / 输入接口bool sort(); / X=0 or X=1 快速排序 目的是满足Johnson 不等式 min(Bi,Aj)min(Bj,Ai) 任意 jibool sortB(int *b,int i,int j,int X); / X=0;bool sortC(int *c,int i,int j,int X); / X=1;void output(); / 输出计算的最优调度所用的时间;#endif/ FlowOperation.cpp#include using std:endl;using std:ios;using std:cout;#include using std:fstream;using std:ifstream;using std:ofstream;#include /using std:exit;#include FlowOperation.h#define N 50 / 预定义有50个作业 根据实际情况可作调整ifstream inputFile(input.txt,ios:in);ofstream outputFile(output.txt,ios:out);FlowOperation:FlowOperation() / 构造函数number=0;numberB=0;numberC=0;a=new int *N;b=new int *N;c=new int *N;for (int i=0;iN;i+)ai=new int 2;bi=new int 2;ci=new int 2;FlowOperation:FlowOperation() / 析构函数for (int i=0;inumber;outputFilenumberendl;coutnumberendl;for (int j=0;j2;j+) / 读取数据 并导入到output.txt文件中for (int i=0;iaij;outputFileaij ;coutaij ;outputFileendl;coutendl;outputFileendl;coutendl;for (int i=0;inumber;i+) / 分类 判断 ai 与 bi 的关系 即 ai0 与 ai1的大小关系 if (ai0ai1) / 提取满足ai=bi的时间事件 在机器M1上的工作时间 小于M2上的工作时间 存储在数组c中cnumberC0=ai0;cnumberC1=ai1;numberC+;coutnumberB=numberBendl;for (int k=0;k2;k+)for (int i=0;inumberB;i+)coutbik ;coutendl;coutendl;coutnumberC=numberCendl;for ( k=0;k2;k+)for (int i=0;inumberC;i+)coutcik ;coutendl;coutendl;if (a!=NULL)if (b!=NULL) | (c!=NULL)return true;return false;return false;bool FlowOperation:sort()if (sortB(b,0,numberB-1,0) / 判断是否一对数组b 排好序if (sortC(c,0,numberC-1,1) / 判断是否一对数组c 排好序return true;return false;return true;bool FlowOperation:sortB(int *b,int i,int j,int X) / 升序排序if (ij)int left=i;int right=j;j+;/ 目的是使用 -jint pivot=biX;while (ij)while(ij) / 从左边寻找第一个大于 pivot 的数 不适用等号if (b+iXi) / 从右边寻找第一个小于 pivot 的数 不适用等号 if (b-jXpivot)continue;break;if (ij)int t;t=biX;biX=bjX;bjX=t;int Y=(X+1)%2;t=biY;biY=bjY;bjY=t;int t;t=bleftX;bleftX=bjX;bjX=t;int Y=(X+1)%2;t=bleftY;bleftY=bjY;bjY=t;sortB(b,left,j-1,X);sortB(b,j+1,right,X);return true;bool FlowOperation:sortC(int *c,int i,int j,int X) / 降序排序if (ij)int left=i;int right=j;j+;/ 目的是使用 -jint pivot=ciX;while (ij)while(ipivot)continue;break;while(ji) / 从右边寻找第一个大于 pivot 的数 不适用等号 if (c-jXpivot)continue;break;if (ij)int t;t=ciX;ciX=cjX;cjX=t;int Y=(X+1)%2;t=ciY;ciY=cjY;cjY=t;int t;t=cleftX;cleftX=cjX;cjX=t;int Y=(X+1)%2;t=cleftY;cleftY=cjY;cjY=t;sortC(c,left,j-1,X);sortC(c,j+1,right,X);return true;void FlowOperation:run() / 运行接口if (input() / 调用并判断 是否完成输入、和划分if (sort() / 判断是否已排好序output(); / 调用outpu()函数 实现导入、输出void FlowOperation:output() / 结果输出for (int k=0;k2;k+) / 把排序好的数据导入到output.txt文件中 以备查看 for (int i=0;inumberB;i+)coutbik ;outputFilebik ;coutendl;outputFileendl;coutendl;outputFileendl;for ( k=0;k2;k+) / 把排序好的数据导入到output.txt文件中 以备查看for (int i=0;inumberC;i+)coutcik ;outputFilecik ;coutendl;outputFileendl;coutendl;outputFileendl;/ 以下代码是实现计算总时间sumint sum=b00; int t=b01;for (int i=1