名词术语(续)
“零件”则代表“服务对象”。零件可 以是单个零件，也可以是一批相同的零 件
“加工路线”是零件加工经过不同机器 构成的路线。比如，某零件要经过车、 铣、占、磨的路线加工，我们可以用 M1,M2,M3,M4来表示。 “加工顺序”则表示每台机器加工n个零 件的先后顺序，是排序要解决的问题
表 11－7 用 CDS 法求解
i
1234
l=1
Pi1
1263
Pi3
4582
L=2
Pi1+pi2
9 6 8 12
Pi2+pi3
12 9 10 11
当ｌ＝1时，按Johnson算法得到加工顺序(1， 2，3，4)； 当ｌ＝2时，得到加工顺序(2，3 ，1，4)。对于顺序(2，3，1， 4)，相应的 Fmax＝29。所以，取顺序(1，2，3，4)。我们 已经知道，这就是最优顺序。
4参数表示法:
n /m /A /B。 其中, n ──零件数；
m ──机器数； A ──作业类型；在A的位置若标以 “F”，则代表流水作业排序问题。若标以 “P”，则表示流水作业排列排序问题。若标 以“G”，则表示一般单件作业排序问题。当m ＝1，则A处为空白 B──目标函数，通常是使其值最小 。
表11-4 改进算法
i
1 23456
ai
518534
bi
722474
i
256143
ai
134558
bi
274742
序列A为 (2， 5，6，1)，序列B为(4，3)，构 成最优顺序为 (2，5，6，1， 4，3)，与 Johnson算法结果一致。
Johnson法则只是一个充分条件，不是必 要条件。不符合这个法则的加工顺序， 也可能是最优顺序。如对例11-2顺序(2 ，5，6，4，1，3)不符合Johnson法则， 但它也是一个最优顺序
T 345
241 ＝
t
{Ot}
表11-11 无延迟计划的构成
Tk
Tk?
T*
M*
1
1.1.1
0
2
0
M1
2.1.3
0
3
0
M3
2
1.2.3
2
6
2.1.3
0
3
0
M3
31.2.33来自73M3
2.2.1
3
7
3
M1
4
1.3.2
7
8
2.2.1
3
7
3
M1
5
1.3.2
7
8
7
M2
2.3.2
7
12
7
M2
6
2.3.2
8
13
12
③ 从{Ot}中挑出满足以下两个条件的工 序Oj：④需要将机确器定M的*加工工序，Oj且放T入j＝{STt*}。，从{ Ot } 中消去Oj，并将Oj的紧后工序放入{ Ot }，使t ＝t＋1。
⑤ 若还有未安排的工序，转步骤②；否 则，停止。
1,1,1 1,2,3 1,3,2 D＝
2,1,3 2,2,1 2,3,2
Pi1
1263
Pi2
8429
Pi3
4582
表 11－6 用关键零件法求解
i
1
2
3
4
Pi1
1
2
6
3
Pi2
8
4
2
9
Pi3
4
5
8
2
pi
13 11 16
14
CDS法
Campbell-Dudek-Smith 三人提出了 一个启发式算法,简称CDS法。他们把 Johnson算法用于一般的n/m/P/Fmax问题 ，得到(ｍ－1)个加工顺序，取其中优者
单件作业排序问题
加工描述矩阵和加工时间矩阵
1,1,1 1,2,3 1,23,24 1
D＝
＝T
2,1,3 2,2,1 2,3,2
34
无延迟作业计划(non-delay schedule)的构成
我们称每安排一道工序称作一“步”， 设
{St}──t 步 之 前 已 排 序 工 序 构 成 的 部 分作业计划；
表11-1 加工时间矩阵
i
123456
Pi1
423142
Pi2
456745
Pi3
587555
Pi4
424331
表11－2 顺序S下的加工时间矩阵
i
615243
Pi1
22 46 410 212 113 316
Pi2
57 411 415 520 727 633
Pi3
512 517 522 830 535 742
最优加顺工序为S＝(2，5，6，1，4，3)。最优顺序下Fm的ax=28。
算法步骤的改进
把Johnson算法作些改变，改变后的算法 按以下步骤进行： 的顺序①排成将一所个有序ai列≤Ab。i的零件按ai值不减
② 将所有ai＞bi的零件按bi值不增 的顺序排成一个序列B。
③ 将A放到B之前，就构成了最优 加工顺序
对于3台机器的流水车间排序问题，只有 几种特殊类型的问题找到了有效算法。
对于一般的流水车间排列排序问题，可 以用分支定界法。
求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的 启发式算法
关键零件法 CDS法
关键零件法求近优解举例
表11-5 加工时间矩阵
i
1234
M2
机
器
M1
1， 1， 1 2 ， 2， 1
③ 若所有零件都已排序，停止。否则， 转步骤①。
求最优顺序
表11－3 加工时间矩阵
i
1 23456
ai
5 18534
bi
7 22474
将零件2排第1位 2
将零件3排第6位 2
3
将零件5排第2位 2 5
3
将零件6排第3位 2 5 6
3
将零件4排第5位 2 5 6
43
将零件1排第4位 2 5 6 1 4 3
{ Ot }──第t步可以排序的工序的集 合；
Tk ──{ Ot }中工序Ok的最早可能开 工时间；
Tk’ ──{ Ot }中工序Ok的最早可 能完工时间。
无延迟作业计划的构成步骤:
① 设t＝1，{S1}为空集，{O1}为各工件 第一道工序的集合。 M*。如②果M求*有T*多＝台mi，n{则Tk任}，选并一求台出。T*出现的机器
流水作业计划问题
流水线是流水车间(Flow shop) 典型的 代表，每个零件的加工路线都一致。 只要加工路线一致：M1， M2, M3，…..， Mm,不要求每个零件都经过每台机器加工
最长流程时间Fmax的计算
最长流程时间又称作加工周期 6/4/p/ Fmax问题，当按顺序S＝( 6,1,5,2,4,3)加工时，求Fmax.
Pi4
113 421 325 232 338 446
加工周期为46
n/2/F/Fmax问题的最优算法
Johnson算法： ① 从加工时间矩阵中找出最短的加工时
间。 ② 若最短的加工时间出现在M1上，则对
应的零件尽可能往前排；若最短加工时间出现 在 加工M2上时，间则矩对阵应中零划件去尽已可排能序往零后件排的。加然工后时，间从。 若最短加工时间有多个，则任挑一个