7
7
14
9
6 6
1
8 3
3
2 9
7
5
31
39
5
9 4
5 19
2 46
2、两台机器排序问题
两台机器排序的目标是使最大完成时间（总 加工周期）Fmax最短 。 实现两台机器排序的最大完成时间Fmax最短 的目标，一优化算法就是著名的约翰逊法 (Johnson’s Law)。其具体求解过程如下例所 示。
1
2 1 8
5
8 7 22
6
10 10 30
机器3
机器4 总和
pi3
pi4
练习
J5
机器1 机器2 pi1 pi2 2 2 7 15 3
J2
5 15 17 4
J6
9 21 31 8
J1
17 23 36
J3
J4
5 22 4 26
5
8
8
2
6
10
2
5
2
1
25 37
1
2
27 39
机器3
机器4
pi3
pi4
7 22 5 27 10 41 5 46 4 50 1 51
–顺序移动方式：一批零件全部加工完成后， 整批移动到下道工序加工 –平行移动方式：单个零件加工完成后，立 即移动到下道工序加工 –平行顺序移动方式：两者混合
2、排序问题的表示法
排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； A----车间类型； F=流水型排序， P=排列排序 G=一般类型,即单件型排序 B-----目标函数
三、流水作业排序问题
1、最长流程时间Fmax的计算 举例：有一个6/4/p/ Fmax问题，其加工时 间如下表所示。当按顺序S＝（6，1，5， 2，4，3）加工时，求Fmax。
2 2 4 5
3 6 2 8
4 3 9 2
举例
i 1 Pi1 1 2 2 3 6 4 3
l=1
Pi3
Pi1+Pi2
4
9
5
6
8
8
2
12
l=2
Pi2+Pi3
12
9
10
11
当 l＝1 时，按 Johnson 算法得到加工顺 序（1 ， 2 ，3，4）；当 l=2 时，得到加 工顺序(2，3，1，4)。对于顺序（2，3， 1 ， 4 ），相应的 Fmax=29。所以，取 顺序（1，2，3，4）。
• • • • • •
将工件2排在第1位 将工件3排在第6位 将工件5排在第2位 将工件6排在第3位 将工件4排在第5位 将工件1排在第4位
2 2 2 2 2 2
5 5 5 5
6 6 6
1
4 4
3 3 3 3 3
• 最优加工顺序为S=(2,5,6,1,4,3), Fmax =28
Johnson算法的改进
二、排序问题的分类和表示法
1、排序问题的分类：
• 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 • 根据加工路线的特征 单件作业排序(Job Shop) 流水作业排序(Flow Shop) • 根据工件到达系统的情况 静态排序 动态排序
• 根据参数的性质 确定型排序 随机型排序 • 根据要实现的目标 单目标排序 多目标排序
计算Fmax
i Pi1 Pi2 Pi3 1 1 8 4 2 2 4 5 3 6 2 8 4 3 9 2
1 9
3 13 18
9 15 26
12
24 28
13
（3）CDS法
Campbell, Dudek, Smith三人于1970年共同 提出了一个启发式算法，简称CDS法。他 们把Johnson算法用于一般的n /m /P/Fmax 问题，得到（m一1)个加工顺序，取其中 优者。
(a) J1 - J2 - J3- J4 - J5
A
B
30
(b) J4 - J2 - J3- J5 - J1
A
B
26
比较
可以看出，初始作业顺序的总加工周期 是30，用约翰逊法排出的作业顺序总加工 周期是26，显然后者的结果优于前者。
两台机器排序问题的算法（续）
I Ai Bi 1 5 7 2 1 2 3 8 2 4 5 4 5 3 7 6 4 4
关键工件法（续）
工件i
Pi1
1
2
2
1
3
6
4
3 Sa (2,1) Sb(4) 所求顺序：
Pi2
Pi3
4
5 11 JC
8
4 13
2
8 16
9
2 14
（2,1,3,4）
练习
J1 机器1 机器2 pi1 pi2 8 J2 3 J3 5 J4 4 J5 2 J6 4
2
5 5 20
8
2 5 18
2
1 4 12
举例
J1 机器1 pi1 5 J2 5 J3 4 J4 1 J5 2 J6 10
机器2
机器3 机器4 机器5 总和
pi2
pi3 pi4 pi5
5
8 2 5 25
5
3 8 2 23
5
3 2 1 15
3
4 1 2 11
6
7 5 8 28
10
4 6 10 40
具体过程
找出关键工件：工作负荷最大的40，对应的是工件6， 所以 Jc=J6
约翰逊－贝尔曼法则
• 约翰逊法解决这种问题分为4个步骤： • (1)列出所有工件在两台设备上的作业时间。 • (2)找出作业时间最小者。 • (3)如果该最小值是在设备1上，将对应的工件排在 前面，如果该最小值是在设备2上，则将对应的工件 排在后面。 • (4)排除已安排好的工件，在剩余的工件中重复步 骤(2)和(3)，直到所有工件都安排完毕。 •
排序常用的符号
Ji----工件i，i=1,2,..n。 Mj ---- 机器j，j＝1，2，…，m. di----工件Ji 的完工期限。 pij----工件Ji在机器Mj上的加工时间,j=1,…,m Pi----工件Ji的加工时间, wij----工件Ji在机器Mj前的等待时间, j=1,…,m Wi----工件Ji在加工过程中总的等待时间, Ci----工件Ji 的完成时间, Fi----工件Ji 的流程时间，即工件在车间的实际停留时间，在工 件都已到达的情况下, Fi= Pi+ Wi Li----工件Ji 的延误时间, Li= Ci- di , Li<=0 按期或完成提前； Li>0 延误 Fmax----最长流程时间， Fmax＝max{Fi}
1 1 8 4
2 2 4 5
3 6 2 8
4 3 9 2
求解过程
λi ＝ k
k 1 3
(3 1) / 2 Pik
求解过程
k=1，2，3 ＝ -Pi1+Pi3 λ1＝-P11+P13= -1＋4＝3 λ2＝-P21+P23= -2+5=3 λ3＝-P31+P33= -6+8=2 λ4＝-P41+P43= -3+2=-1 按λi不增的顺序排列工件，得到加工顺序 （1，2，3，4）和（2，1，3，4）， Fmax=28
• 1. 将所有ai ≤ bi的工件按ai值不减的 顺序排成一个序列A； • 2. 将ai＞bi的工件按bi值不增的顺序排 成一个序列B； • 3. 将A放到B之前，就构成了一个最优 加工顺序。
改进算法举例
工件号 ai bi 1 5 7 2 1 2
5 1
3 8 2
6 4
4 5 4
1
5 3 7
4
6 4 4
三种方法比较
以上三种方法，优度最高的是CDS法， 其次是关键工件法，Palmer法最低。 从计算工作量来讲，关键工件法最简便， Palmer法次之， CDS最复杂。
四、相同零件不同移动方式下 加工周期的计算
• 当n个零件相同，则无排序问题。但不 同移动方式下的加工周期不同 • 三种典型的移动方式
Jc。 2、 除Jc外，将满足Pi1<Pim的工件，按Pi1值的大小， 从小到大排在Jc的前面。 3 、 除Jc外，将满足pi1>pim的工件，按Pim值的大小， 从大到小排在Jc的后面。 4、除Jc外，将满足Pi1=Pim的工件，排在Jc的前面或者 后面 • 步骤5 如有多个方案，可再加比较，从中选优。
假设条件
1.一个工件不能同时在几台不同的机器上加工。 2.工件在加工过程中采取平行移动方式，即当上一道工 序完工后，立即送下道工序加工。 3.不允许中断。当一个工件一旦开始加工，必须一直进 行到完工，不得中途停止插入其它工件。 4.每道工序只在一台机器上完成。 5.工件数、机器数和加工时间已知，加工时间与加工顺 序无关。 6.每台机器同时只能加工一个工件。
10
2 2 20 5 30 8 32 2
12
4 1 27 7 35 5 38 3
13
3 3 33 6 42 7 46 4
16
最长流程时间的计算
i
Pi1
举例2
2
6
1
4 4
4
5
6 9
18 24 30 3
3 12 19 32
35 4
5
8 24
16
22 34 44
30 36
48 52
Pi2
Pi3 Pi4
3
具体做法是，对加工时间 Pik和
k 1 l
k m 1l
Pik
m
（ l=1，2，…，m-1），用 Johnson 算法求 （m-1)次加工顺序，取其中最好的结果。