。

每个作业加工的顺序都是先在M1上加工#xff0c;然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi#xff0c;1≤i≤n。

N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi1≤i≤n。

流水作业高度问题要求确定这n个作业的最优加工顺序使得从第一个作业在机器M1上开始加工到最后一个作业在机器M2上加工完成所需的时间最少。

算法分析

因此得到一个贪心的性质让a,b中a比较小的尽可能先执行a,b中b比较小的尽可能后执行

Johnson贪心算法步骤如下

1将所有作业按M1,M2的时间分为两组a[i]b[i]的为N1a[i]b[i]为N2

3按顺序先执行N1

algorithm//用于下面的排序函数sort()库函数的调用

using

JOB[n];//开辟一个空间大小为n的JOB即有n个的JOB对象

for(i0;in;i)

sort(d,nd,cmp);//对n个对象按key的大小进行排序

j0;

//下面的for()对上面对key进行排好的序再按job为真的key升排序job

for(i0;in;i)

//前一个作业的时间与前一个作业的第一个时间和第二个作业的时间相

delete