0018算法笔记——【动态规划】流水作业调度问题与Johnson法则Word文档下载推荐.docx
《0018算法笔记——【动态规划】流水作业调度问题与Johnson法则Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《0018算法笔记——【动态规划】流水作业调度问题与Johnson法则Word文档下载推荐.docx（12页珍藏版）》请在冰点文库上搜索。
将问题规模缩小。
公式
（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取max{t-ai,0}。
3、动态规划法求解思路
假设有一组作业需要在M1和M2两台机器上进行流水作业，他们在M1和M2上的作业时间如下表：
问题是如何安排他们的加工顺序，使得，到最后一个作业在机器M2上加工完成所需要的时间最少。
也就是所有作业在两台机器全部加工完成所需的时间最少。
思路如下：
考虑如果只有一个作业的情况，肯定所需时间就是它自身需要在M1和M2上的加工时间总和；
如果有两个作业就要考虑在两种不同的加工顺序下选取最优的一种作为候选，三个作业的时会出现三种组合情况（0,（1,2））;
（1,（0,2））;
（2,（0,1））,拿第一种为例,它表示先加工作业0,然后再按照作业1和作业2的优化顺序加工;
将三种的作业时间计算出来,取最小值,即为三个作业的优化结果,同理可对更多的作业进行排序优化。
具体做法是，用类似矩阵连乘的办法，自底向上将所有能的情况计算出来，并产生一个表，供后面的计算查用，减少重复计算的工作量。
对于j1作业M2的等待时间为b0,实际上在M2加工j0作业的同时，M1并行加工j1,实际它需要等待b1-a0时间。
2+4+（5-4）+2=9
从J0和J1两个作业的加工顺序，可以看出，先加工J0后J1，所用时间最短为9，将其填入表中，依此类推，即可得出最优解。
a4+a0+a2+a1+a3+[（b4+b0+b1+b2）-（a0+a1+a2+a3）]+b3
=1+2+3+4+6+[（7+5+2+3）-（2+4+3+6）]+1
=16+[17-15]+1=19
选其中加工时间短的作为候选方案；
在具体计算时非最优子集不必考虑，这样可以减少计算次数。
4、流水作业调度的Johnson法则
设兀是作业集S在机器M2的等待时间为t时的任一最优调度。
若在这个调度中，安排在最前面的两个作业分别是i和j，即π
（1）=I,π
（2）=j。
则有动态规划递归式可得
其中
如果作业i和j满足min{bi,aj}≥min{bj,ai},则称作业i和j满足Johnson不等式。
如果作业i和j不满足Johnson不等式，则交换作业i和j满足Johnson不等式。
证明：
在作业集S中，对于机器M2的等待时间为t的调度π，交换作业i和j的加工顺序，得到作业集S的另一个调度π’，它所需的加工时间为
当作业i和j满足Johnson不等式min{bi,aj}≥min{bj,ai}时，有
从而
由此可得
因此，对任意t有
从而，tij≤tji,由此可见，换句话说，当作业i和j不满足Johnson不等式时，交换它们的加工顺序后，作业i和j满足Johnson不等式，且不增加加工时间。
由此可知，对于流水作业调度问题，必存在最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式：
这样的调度π称为满足Johnson法则的调度。
进一步还可以证明，调度满足Johnson法则当且仅当对任意i<
j有：
由此可知，任意两个满足Johnson法则的调度具有相同的加工时间，从而所有满足Johnson法则的调度均为最优调度。
5、流水作业调度问题Johnson算法
从上面的分析可知，流水作业调度问题一定存在满足Johnson法则的最优调度，且容易由下面的算法确定：
流水作业调度问题的Johnson算法：
（1）令N1={i|ai<
bi},N2={i|ai>
=bi};
（2）将N1中作业按ai的非减序排序；
将N2中作业按bi的非增序排序；
（3）N1中作业接N2中作业构成满足Johnson法则的最优调度。
Johnson算法中分类及排序的作用（验证不等式）设数组c[]为排序后的作业排列，排序结果如下：
红线左侧满足a[c[i]]<
=b[c[i]]和a[c[i]]<
=a[c[i+1]]符合johnson不等式，min（b[c[i]],a[c[i+1]]）>
=min（b[c[i+1]],a[c[i]]）其调度顺序最优；
红线右侧满足b[c[i]]<
=a[c[i]]和b[c[i]]>
=b[c[i+1]]符合johnson不等式，min（b[c[i]],a[c[i+1]]）>
中间过渡部分横向比较，左侧a[c[i]]<
b[c[i]]右侧b[c[i+1]]<
=a[c[i+1]]满足min（b[c[i]],a[c[i+1]]）>
=min（b[c[i+1]],a[c[i]]）其调度顺序也最优；
程序具体代码如下：
[cpp]
viewplain
copy
1.//3d9
动态规划
流水作业调度问题
2.#include
"
stdafx.h"
3.#include
<
iostream>
4.using
namespace
std;
5.
6.const
int
N
=
5;
7.
8.class
Jobtype
9.{
10.
public:
11.
operator
=（Jobtype
a）
const
12.
{
13.
return（key<
=a.key）;
14.
}
15.
key,index;
16.
bool
job;
17.};
18.
19.int
FlowShop（int
n,int
a[],int
b[],int
c[]）;
20.void
BubbleSort（Jobtype
*d,int
n）;
//本例采用冒泡排序
21.
22.int
main（）
23.{
24.
a[]
{2,4,3,6,1};
25.
b[]
{5,2,3,1,7};
26.
c[N];
27.
28.
minTime
FlowShop（N,a,b,c）;
29.
30.
cout<
作业在机器1上的运行时间为：
endl;
31.
for（int
i=0;
i<
N;
i++）
32.
33.
a[i]<
;
34.
35.
36.
作业在机器2上的运行时间为：
37.
38.
39.
b[i]<
40.
41.
42.
43.
完成作业的最短时间为：
minTime<
44.
编号从0开始，作业调度的顺序为：
45.
46.
47.
c[i]<
48.
49.
50.
return
0;
51.}
52.
53.int
c[]）
54.{
55.
*d
new
Jobtype[n];
56.
n;
57.
58.
d[i].key
a[i]>
b[i]?
b[i]:
a[i];
//按Johnson法则分别取对应的b[i]或a[i]值作为关键字
59.
d[i].job
=b[i];
//给符合条件a[i]<
b[i]的放入到N1子集标记为true
60.
d[i].index
i;
61.
62.
63.
BubbleSort（d,n）;
//对数组d按关键字升序进行排序
64.
65.
j
0,k
n-1;
66.
67.
68.
69.
if（d[i].job）
70.
71.
c[j++]
d[i].index;
//将排过序的数组d，取其中作业序号属于N1的从前面进入
72.
73.
else
74.
75.
c[k--]
//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序
76.
77.
78.
79.
a[c[0]];
80.
k
j+b[c[0]];
81.
i=1;
82.
83.
+=
a[c[i]];
//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完
84.
j<
k?
k+b[c[i]]:
j+b[c[i]];
//计算最优加工时间
85.
86.
87.
delete
d;
88.
k;
89.}
90.
91.//冒泡排序
92.void
n）
93.{
94.
i,j,flag;
95.
temp;
96.
97.
for（i=0;
i++）{
98.
flag
99.
for（j=n-1;
j>
j--）{
100.
//如果前一个数大于后一个数，则交换
101.
if（d[j]<
=d[j-1]）{
102.
temp
d[j];
103.
d[j]
d[j-1];
104.
d[j-1]
105.
1;
106.
107.
108.
//如果本次排序没有进行一次交换，则break，减少了执行之间。
109.
if（flag
==
0）{
110.
break;
111.
112.
113.}
运行结果如下：
升级会员 