求解流水作业调度问题的 Johnson 算法具体描述如下：
（1） 设 a[i] 和 b[i] （ 0<=i
）分别为作业
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
从左右两端生成最优作业排列
c[j](0<=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
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
算法步骤
(1),
生成三元组表
d
If (a[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
算法步骤
(3),
生成最优解
If (d[i].ab==0)c[left++]=d[i].jobNo;
Else c[right–]=d[i].jobNo;
}
Johnson 算法的时间取决于对作业集合的排序 , 因此 , 在最怀情况下算法的时间复杂度为 O(nlogn), 所需的空间复杂度为 O(n).
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208055.html原文链接：https://javaforall.net
