流水作业调度
一、可行性分析与项目开发计划
ｎ个作业{n,...2,1}要在由2台机器M1和M2组成的流水线上完成加工。每个作业的顺序都是现在M1上加工，然后再M2上加工。M1和M2加工作业i所需的时间分别是ai和bi，1<=i<=n.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。
直观上，一个最优调度应该使得机器M1没有空闲时间，而且机器M2的空闲时间最少，在一般情况下，机器M2上会出现机器空闲和作业积压两种情况。设全部作业的集合为N={1,2，…n}。NS是N的作业子集，在一般情况下，机器M1开始加工作业S中作业时，机器M2还在加工其他作业，要等时间t后才可以利用。将这种情况下完成S中作业所需要的最短时间记做T(S,t),则流水作业调度问题的最优值就是T(N,0).
我们通过分析可以知道流水作业调度问题具有最优子结构的性质，因此考虑用动态规划算法自后向前来解决其最优问题。这就需要通过建模来得出最优子结构的递归式子，从而设计算法求解最优值。
二、需求分析
1、用户可以根据自己的需要输入想要进入流水线的作业数。
2、用户可以输入这几个作业在机器M1和M2上的加工时间。
3、由主函数调用流水作业调度的Johnson算法来实现对流水作业的安排。
4、输出经过Johnson算法安排后的作业序列，这就是最终的一个最优调度。
三、概要设计
1、总体设计：
假定这n个作业在机器M1上加工时间为ai,在机器M2上加工时间为bi，1<=i<=n. 由流水作业调度问题具有最优子结构性质可知，
T(N,0)=min{ai+T(N={i},bi)}1<=i<=n
推广到一般情况下，
T(S,t)={ai+T(S-{i},bi+max{t-ai,0})} i∈S
式子中，max{t-ai,0}这一项是由于在机器这一项是由于在机器M2上，作业i必须在max{t，ai}时间之后才能开工，因此，在机器M1上完成作业加工i之后，在机器还需要bi+max{t,ai}=bi+max{t-ai,0}时间完成对作业i的加工。
按照上述递归式，可以设计出流水作业调度问题的动态规划算法，但是算法还可以进一步简化。
设π是作业集S在机器M2的等待时间为t时的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是i和j，记π(1)=i，π(2)=j由动态规划递归式可得：
如果作业i和作业j满足min{bi,ai}>=min{bj,aj},则称作业i和作业j满足Johnson不等式。
如果作业i和作业j不满足Johnson不等式，则交换作业i和作业j的加工顺序后，作业
i和作业j满足Johnson不等式，而且不增加加工时间。
因此，任意两个满足Johnson法则的调度具有相同的加工时间，从而所有满足Johnson 法则的调度均为最优调度，流水作业调度问题转化为求解满足Johnson法则的调度问题。流水作业调度的Johnson算法：
(1)令N1={i|ai=bi}；
(2)将N1中的作业按照ai的非减序排序，将N2中的作业按照bi的非增序排序；
(3)N1中作业接N2中作业构成满足 Johnson法则的最优调度。
2、为了实现上述算法，需要采用顺序表的抽象数据类型：
ADT Sqlist{ 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同、可以唯一标识数据元素的关键字
数据关系R：数据元素同属于一个集合。
基本操作：
sort(&L, n)
初始条件：顺序表L存在
操作结果:对顺序表L中的内容按关键字大小进行由小到大的排序
Flowshop(n, a, b, c)
初始条件：数组a.、b存在并且不为空，大小为n
操作结果：执行Johnson算法，并且返回最优调度的时间长度，在数组c中存放最优调度安排}ADT Sqlist
3、本项目主要有以下几个模块：
(1)输入需要调度作业的模块：输入作业的个数，以及在每个作业在机器M1和机器M2上需要加工的时间。
(2)排序模块：对一个顺序表按照关键字由小到大进行排序
(3)执行Johnson算法模块：对N个作业调用Johnson算法确定最优调度和最优调度下总的调度时间。
(4)输出最优调度方案的模块：输出最优调度安排方式和最优调度所用的时间。整体架构如下
main{ 初始化 {
Johnson算法 }
显示结果 }
四、详细设计
1、数据结构的设计
为了实现Johnson算法，本项目采用以下的数据结构：
typedef struct{
int key,index; bool job;
}Jobtype;
typedef struct{
Jobtype r[MAXSIZE];
int length;
}Sjob;//顺序表类型
对于整个N个作业定义为一个顺序表类型，在其数组中存在的每一个作业记录有关键字和索引，并且也有逻辑量来标识在M1和M2机器上加工时间的大小。
2、对抽象数据类型的部分操作的算法设计如下：
/*对一个顺序表按照关键字由小到大进行排序*/
void sort(Sjob &L,int n)
{
L.length=n;
int i,j;
Jobtype t;
for(i=0;ifor(j=i+1;jif(L.r[i].key>L.r[j].key)
{
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
/*执行Johnson算法确定最优调度*/ int Flowshop(int n,int a[],int b[],int c[]) {
int i;
Sjob d;
for(i=0;i{d.r[i].key=a[i]>b[i]?b[i]:a[i];
d.r[i].job=a[i]<=b[i];
d.r[i].index=i;
}
sort(d,n);
int j=0,k=n-1;
for(i=0;i{
if(d.r[i].job)
c[j++]=d.r[i].index;
else
c[k--]=d.r[i].index;
}
j=a[c[0]];
k=j+b[c[0]];
for(i=1;i{
j+=a[c[i]];
k=j}
return k;
}
3、函数调用关系：
