流水作业调度

1、精选优质文档-倾情为你奉上流水作业调度一、 可行性分析与项目开发计划个作业要在由2台机器M1和M2组成的流水线上完成加工。每个作业的顺序都是现在M1上加工，然后再M2上加工。M1和M2加工作业i所需的时间分别是和，1<=i<=n.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。直观上，一个最优调度应该使得机器M1没有空闲时间，而且机器M2的空闲时间最少，在一般情况下，机器M2上会出现机器空闲和作业积压两种情况。设全部作业的集合为N=1,2，n。是N的作业子集，在一般情况下，机器M1开始加工作

2、业S中作业时，机器M2还在加工其他作业，要等时间t后才可以利用。将这种情况下完成S中作业所需要的最短时间记做T(S,t),则流水作业调度问题的最优值就是T(N,0).我们通过分析可以知道流水作业调度问题具有最优子结构的性质，因此考虑用动态规划算法自后向前来解决其最优问题。这就需要通过建模来得出最优子结构的递归式子，从而设计算法求解最优值。 二、 需求分析1、 用户可以根据自己的需要输入想要进入流水线的作业数。2、 用户可以输入这几个作业在机器M1和M2上的加工时间。3、 由主函数调用流水作业调度的Johnson算法来实现对流水作业的安排。4、 输出经过Johnson算法安排后的作业序列，这就是

3、最终的一个最优调度。三、 概要设计总体设计：假定这n个作业在机器M1上加工时间为,在机器M2上加工时间为，1<=i<=n.由流水作业调度问题具有最优子结构性质可知， 1<=i<=n推广到一般情况下， 式子中，这一项是由于在机器M2上，作业i必须在时间之后才能开工，因此，在机器M1上完成作业加工i之后，在机器还需要时间完成对作业i的加工。按照上述递归式，可以设计出流水作业调度问题的动态规划算法，但是算法还可以进一步简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是i和j，记，由动态规划递归式可得：其中如果作业i和作业j

4、满足,则称作业i和作业j满足Johnson不等式。如果作业i和作业j不满足Johnson不等式，则交换作业i和作业j的加工顺序后，作业i和作业j满足Johnson不等式，而且不增加加工时间。因此，任意两个满足Johnson法则的调度具有相同的加工时间，从而所有满足Johnson法则的调度均为最优调度，流水作业调度问题转化为求解满足Johnson法则的调度问题。流水作业调度的Johnson算法：(1)令N1=i|，N2=i|；(2)将N1中的作业按照的非减序排序，将N2中的作业按照的非增序排序；(3)N1中作业接N2中作业构成满足 Johnson法则的最优调度。1、为了实现上述算法，需要采用顺序

5、表的抽象数据类型ADT Sqlist数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同、可以唯一标识数据元素的关键字数据关系R：数据元素同属于一个集合。基本操作：sort(&L, n)初始条件：顺序表L存在操作结果:对顺序表L中的内容按关键字大小进行由小到大的排序Flowshop(n, a, b, c)初始条件：数组a.、b存在并且不为空，大小为n操作结果：执行Johnson算法，并且返回最优调度的时间长度，在数组c中存放最优调度安排 ADT Sqlist2、本项目主要有以下几个模块：(1)输入需要调度作业的模块：输入作业的个数，以及在每个作业在机器M1和机器M2上

6、需要加工的时间。(2)排序模块：对一个顺序表按照关键字由小到大进行排序(3)执行Johnson算法模块：对N个作业调用Johnson算法确定最优调度和最优调度下总的调度时间。(4)输出最优调度方案的模块：输出最优调度安排方式和最优调度所用的时间。整体架构如下main初始化Johnson算法显示结果四、 详细设计五、1、数据结构的设计：为了实现Johnson算法，本项目采用以下的数据结构：typedef structint key,index;bool job;Jobtype;typedef struct Jobtype rMAXSIZE; int length;Sjob;/顺序表类型对于整个N

7、个作业定义为一个顺序表类型，在其数组中存在的每一个作业记录有关键字和索引，并且也有逻辑量来标识在M1和M2机器上加工时间的大小。2、对抽象数据类型的部分操作的算法设计如下：/*对一个顺序表按照关键字由小到大进行排序*/void sort(Sjob &L,int n) L.length=n;int i,j;Jobtype t;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(L.ri.key>L.rj.key)t=L.ri;L.ri=L.rj;L.rj=t;/*执行Johnson算法确定最优调度*/int Flowshop(int n,int a

8、,int b,int c) int i; Sjob d; for(i=0;i<n;i+)d.ri.key=ai>bi?bi:ai; d.ri.job=ai<=bi; d.ri.index=i;sort(d,n);int j=0,k=n-1;for(i=0;i<n;i+)if(d.ri.job)cj+=d.ri.index;else ck-=d.ri.index;j=ac0;k=j+bc0;for(i=1;i<n;i+) j+=aci; k=j<k?k+bci:j+bci;return k;函数调用关系：mainJohnson算法Sort算法六、 编码#inc

9、lude "stdio.h"#define MAXSIZE 1000typedef structint key,index;bool job;Jobtype;typedef struct Jobtype rMAXSIZE; int length;Sjob;/顺序表类型void sort(Sjob &L,int n) L.length=n;int i,j;Jobtype t;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(L.ri.key>L.rj.key)t=L.ri;L.ri=L.rj;L.rj=t;int Flowsh

10、op(int n,int a,int b,int c) int i; Sjob d; for(i=0;i<n;i+)d.ri.key=ai>bi?bi:ai; d.ri.job=ai<=bi; d.ri.index=i;sort(d,n);int j=0,k=n-1;for(i=0;i<n;i+)if(d.ri.job)cj+=d.ri.index;else ck-=d.ri.index;j=ac0;k=j+bc0;for(i=1;i<n;i+) j+=aci; k=j<k?k+bci:j+bci;return k;void main()int n,i;in

11、t aMAXSIZE,bMAXSIZE,cMAXSIZE;printf("流水线中的作业个数是：");scanf("%d",&n);printf("第一个的加工时间是：");for(i=0;i<n;i+)scanf("%d,",&ai);printf("第二个的加工时间是：");for(i=0;i<n;i+)scanf("%d,",&bi);int m=Flowshop(n,a,b,c); for(i=0;i<n;+i) printf

12、("%d ",ci);printf("n");printf("最短加工完成时间是%dn",m); 七、 测试在运行dos窗口下输入命令，这次测试输入4个作业，得出了如下结果：进行一组测试，得出了如下结果:若按照Johnson算法手工做题，可知知道N1=0,2,3,N2=1;最优调度是0，2,3,1计算的最优调度时间是38再次进行一组测试，这次再次测试4个作业的情况，在N1和N2中各有两个作业的情况。得到了如下结果：如按照手工计算，可知N1=1,3，N2=0,2，排序后的最优调度是3,1,2,0,和程序结果一致，而且最优调度时间也是45再次进行一次较为合理的测试：若出现两个作业的加工时间一样，这次作业的个数是6个，作业1和作业5在两个机器上的加工时间是一样的得到如下的结果