作业：用Palmer法求解
2、关键工件法
（1）计算每个工件的总加工时间，找出加工时间最长 的工件C，将其作为关键工件； （2）对于余下的工件若Pi1≤Pim，则按Pi1 不减的顺序排 成一个序列Sa ，若Pi1＞Pim， 则按Pim 不增的顺序排列成 一个序列Sb。 （3）顺序（ Sa，C，Sb）即为所求顺序。
K = 1
m
i [k (3 1) / 2]Pik
k 1
m
i [k 2]Pik
k 1
m
=(1-2) Pi1+(2-2) Pi2+(3-2) Pi3
=- P i1 + P i3
λi =- P i1 + P i3 λ1 = - P 11 + P 13= -1+4 = 3 λ2 = -P21 + P23= -2 + 5= 3 λ3 =- P31 + P33 = -6 + 8 = 2 λ4 =-P 41+P43 = -3 + 2 = -1 按λi不增的顺序排列，得到加工顺序 （1，2，3，4）和（2，1，3，4）， 两者均为最优顺序，Fmax=28。
例：有一个4/3/P/ Fmax 问题，其加工时间如下 表所示，用Palmer法求解。
表11 加工时间矩阵 -5 i Pi1 Pi2 Pi3 1 1 8 4 2 2 4 5 3 6 2 8 4 3 9 2
解
i [k (m 1) / 2]Pik , (k 1,2,3, )
k 1
M2
M3 M4
t1 t2 t3 t T平顺
4
时间 第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为
第2个工序的开始时间。即从红线开始向前推3个作为第2个工序的开始时间。

T=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4)
m m 1 i 1
T平顺 n ti (n 1) min( t j , t j 1 )
1， 3 2， 2，1 2，
1，2 3， 2，2 3，
二、一般n/m/G/Fmax问题的算法
1、符号说明
{St}──t步之前已排序工序构成的部分作
业计划； { Ot }──第t步可以排序的工序的集合； Tk ──{ Ot }中工序Ok 的最早可能开工时 间； Tk’ ──{ Ot }中工序Ok 的最早可能完工时 间。
4
代入例中数字： T 4 10 5 15 10） 160 (分钟） （ 一般式：T ni 1 ti
m
顺序移动方式下的加工周期计算
其中 : n 批量；m 工序数。
2、平行移动方式
每个零件在前道工序加工完毕后，立即转移到后 道工序去继续加工，形成前后工序交叉作业。

关键工件法求近优解举例
表11 加工时间矩阵 -5 i Pi1 Pi2 Pi3 1 1 8 4 2 2 4 5 3 6 2 8 4 3 9 2
1、找出最长时间
2、 Pi1≤Pim，则按Pi1不减
3、若Pi1≥Pim，则按Pim不增 4、组成（ Sa，C，Sb）
表11-6用关键零件法求解
i 1 2 3 4
2
2 2
5 5
5
6
6
3 max=28 最优顺序下的 F 最优加工顺序为S=（2，5，6，1，4，3）。
课堂作业：
Johnson法则，最优排序！
以及计算Fmax
（二）算法步骤的改进
把Johnson算法作些改变，改变后的算法 按以下步骤进行： ① 将所有ai≤bi的零件按ai值不减 的顺序排成一个序列A。 ② 将所有ai＞bi的零件按bi值不增 的顺序排成一个序列B。 ③ 将A放到B之前，就构成了最优 加工顺序

三、求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法 1、Palmer法：按斜度指标排列工件的启发式算法
工件的斜度指标按下式计算：
i [k (m 1) / 2]Pik k=1，2，3...m
k 1
m
m为机器数；Pik 为工件i在Mk 上的加工时间，k是机 器编号，按照各工件λi不增的顺序排列工件,可得 出满意顺序
m——工序数目；
ti——工件在第i工序的单 件工时；
1、顺序移动方式:
一批零件在上道工序全部加工完毕后,才整批转移
到下道工序加工。
工序 M1 M2 M3 M4
t1 t2 t3 t4 T顺序 时间
n——加工批量； m——工序数目； ti——工件在第i工序的单件工时；
顺序移动方式下的加工周期计算
T nt1 nt 2 nt 3 nt 4 ni 1 ti
i 1
Min(tj,tj+1)——前后相邻两工序中 单件工时之较小者 T=4×(10+5+15+10)-(4-1) ×(5+5+10)=100分钟
3、平行顺序移动方式
工序 加 工 周 期 的 计 算 M1 M2 t1 t2 t3 t4
M3 M4
M5
T平顺
时间
m 1 i 1
T平顺 n ti (n 1) min( t j , t j 1 )
pik pi 2 pi 3
k 2
表 11-7
i L=1 Pi1 Pi3 L=2 Pi1+Pi2 Pi2+Pi3
用 CDS法求解
1 1 4 9 12 2 2 5 6 9 3 6 8 8 10 4 3 2 12 11
当L＝1时，按Johnson算法得到加工顺序(1，2，3，4)， 相应的Fmax＝28。 当L＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3 ，1， 4)，相应的Fmax＝29。 所以，取顺序(1，2，3，4)。我们已经知道，这就是最 优顺序。
p
k 1
L
ik
pik
k 1
1
和
k m 1 L

m
pik
k 311
p
3
ik
pik
k 3
3
即Pi1和Pi3
再计算L=2时的加工时间，
p
k 1
L
ik

p
k 1
2
ik
pi1 pi 2
和
3
k m 1 L

m
pik
k 31 2
p
3
ik
10 15
2 2 5 8 2
12
4 1 7 5 3
13
3 3 6 7 4
16
7
12 13
11
20
27
33
17 21
22 25
30 32
35 38
42 46
4
加工周期为46
课堂作业：求Fmax.
表3顺序S下的加工时间矩阵
i P i1 P i2 P i3 P

i4
1
3 2 1
3
2
3 5 4 2
6
3
4 4 5 3
作业： 用CDS法求解
四、相同零件、不同移动方式下加工 周期的计算
零件在加工过程中可以采用三种典型的 移动方式：
顺序移动
平行移动 平行顺序移动
四、相同零件、不同移动方式下加工 周期的计算

例：一批制品，批量n =4件，须经四道工序加工， 各工序时间分别为：t1=10, t2=5, t3=15, t4=10。 n——加工批量；
工序 M1 M2 M3 M4
考虑平行性，实现交叉作业
t1
t2 t3
t4
T平顺 时间
按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，
第2个工序的第1个工件加工完成后立刻转移到第3个工序进行加工。
3、平行顺序移动方式
第2种情况：ti≥ ti+1
工序 M1
考虑设备加工的连续性
T=nt1+t2+x+t4 x X=nt3-(n-1)t2
10
4
2 3 7 2
12
5 6
1 7 5 3
13
3 6 4 1
16
5
10
11
15
18
25
31
5
15
20 23
27 29
32 35
36 37
11
17
加工周期为37
二、n/2/F/Fmax问题的最优算法
（一）Johnson算法：
① 从加工时间矩阵中找出最短的加工时 间。 ② 若最短的加工时间出现在M1上，则对 应的零件尽可能往前排；若最短加工时间出现 在M2上，则对应零件尽可能往后排。然后，从 加工时间矩阵中划去已排序零件的加工时间。 若最短加工时间有多个，则任挑一个 ③ 若所有零件都已排序，停止。否则， 转步骤①。
例题：求表11-3所示的6/2/F/Fmax问题的最优解。
i
表11-3加工时间矩阵 1 2 3 4 5 1 8 5 5 3 6 4
ai
bi
7
2
2
4
7
4
将零件2排第1位 2
将零件3排第6位 2 将零件5排第2位 将零件6排第3位
将零件4排第5位 将零件1排第4位 2 5
3 3 6 3 4 1 4 3
第二节 流水作业排序问题
流水作业排序问题的基本特征是每个零 件的加工路线都一致。即工件流向一致. 只要加工路线一致：M1， M2, M3，…..， Mm,不要求每个零件都经过每台机器加工