农夫之子㊣

Johnson 算法
求解流水作业调度问题的Johnson算法具体描述如下：
（1） 设a[i]和b[i]（0<=i<n）分别为作业i在两台设备上的处理时间。建立由三元组（作业号，处理时间，设备号）组成的三元组表d。其中，处理时间是指每个作业所包含的两个任务中时间较少的处理时间。例7－11的作业0的三元组为（0，3，0），作业1的三元组为（1，2，1）……如图7－18（a）所示。
（2） 对三元组表按处理时间排序，得到排序后的三元组表d。如图7－18（b）所示。
（3） 对三元组表的每一项d（i）(0<=i<n),从左右两端生成最优作业排列c[j](0<=j<n),c[j]是作业号。如果d[i]设备号为1，则将作业i置于c的左端末尾，否则置于c的右端末尾。如图7－18（c）所示，由两端想中间存放。


作业号 处理时间 设备号
0 1 2 2
1 0 3 1
2 2 8 1
3 3 9 1

作业号 处理时间 设备号
0 0 3 1
1 1 2 2
2 2 8 1
3 3 10 1
(a)三元组表 (b)按处理时间排序



(0, 2, 3, 1)
(c)最优作业排列

P1 3 8 10 4

P2 6 9 15 2
(d)最优调度方案

程序7－12流水作业调度的Johnson算法。
程序【7－12】Johnson算法
Struct Triplet{ //三元组结构
Int Operator<(Triplet b)const {return t <b.t;}
Int jobNo,t,ab; //jobNo为作业,体委处理时间,ab为设备号
};
Void FlowShop(int n,int *a,int*b,int*c)
{
Triplet d[mSize]={{0,0,0}};
For(int i=0;i<n;i++) //算法步骤(1),生成三元组表d
If (a[i]<b[i]){
d[i].jobNo=i;d[i].ab=0;d[i].t=a[i];
}
Else {
d[i].jobNo=i;d[i].ab=1;d[i].t=b[i];
}
Sort(d,n); //算法步骤(2),任意排序算法
Int left=0,right=n-1;
For(i=0;i<n;i++) //算法步骤(3),生成最优解
If (d[i].ab==0)c[left++]=d[i].jobNo;
Else c[right--]=d[i].jobNo;
}
Johnson算法的时间取决于对作业集合的排序,因此,在最怀情况下算法的时间复杂度为O(nlogn),所需的空间复杂度为O(n).