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)
最优作业排列
(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).