作业
加工时间（天） 预定日期（天）
A
2
7
B
8
16
C
4
4
D
10
17
E
5
15
F
12
18
2019/11/12
武汉理工大学管理学院 袁付礼
11
生
产
与 运 作
按FCFS规则排序
管
理
排序的结果是A-B-C-D-E-F。
顺序 加工时间 流程时间 预定交货期
A B C D E F 合计 平均
2019/11/12
序相同，作业时间如下表所示:
1
作业 机床
A
B
C
D2
5
t1 3 6 5 7
t2 2 8 6 4
C DA
6
7
3
6
8
T
42
2019/11/12
T = 2+4+8+6+5 = 25
武汉理工大学管理学院 袁付礼
17
生
产 与 运
五、3台机器上N项作业的排
作 管
序(简称为N/3排序)
理
此方法是约翰逊（Johnson）规则的扩展 方法，它是将三台设备合并为两台假想的 设备，然后按约翰逊(Johnson)规则进行排 序。
第十一章 作业排序
本章主要介绍制造业的作业排序问 题。
生
产
与
运 作
一、作业排序的概念和类型
管
理
1、概念
对一定期间内分配给生产单位的作业任务， 根据产品(零件)的工艺路线和设备负荷可 能性，确定各个生产单位作业任务的先后 顺序。
作业排序问题通常表述为“n项作业任务 在m个生产单位的排序的问题”。
第五步，根据以上（M-1）个工作顺序方案，分 别作图求出它们的总流动时间从中取得小值，最 小值所对应的排序方案为最优的或近似最优的方 案。
2019/11/12
武汉理工大学管理学院 袁付礼
23
生 产 与 运 作 管 理
2019/11/12
武汉理工大学管理学院 袁付礼
24
2019/11/12
武汉理工大学管理学院 袁付礼
2
生
产
与
运 作
一、作业排序的概念和类型
管
理
2、作业排序的类型：
⑴流水型m×n排序问题 指n项任务在m台设 备上加工，所有任务的工艺顺序相同，有n! 个排序方案。
⑵非流水型m×n排序问题 指n项任务在m台 设备上加工，所有任务的工艺顺序不同， 有(n!)m个排序方案。
2019/11/12
武汉理工大学管理学院 袁付礼
3
生
产
与
运 作
一、作业排序的概念和类型
管
理
作业排序的表示方法为
生产单位数×作业任务数/排序问题类型/ 评价尺度(优化目标)
如m ×n/FLW/Fmax表示m个生产单位完 成n项作业任务、流水型排序问题和以最 大流程时间作为评价尺度。
2019/11/12
2
2
7
8
10
16
4
14
4
10
24
17
5
29
15
12
41
18
41
120
120/41=2.93 120/6=20
武汉理工大学管理学院 袁付礼
延期天数(如果 为负则赋值0)
0 0 10 7 14 23 54 54/6=9
12
生
产
与 运 作
按SPT规则
管
理
作业顺序是A-C-E-B-D-F
顺序 加工时间 流程时间 预定交货期
作业 机床
A
B
C
D 解： 1
t1
9
6
9
10
作业 机床
A
B
C
D
t2
3
4
6
5
tG 12 10 15 15
t3
7
8 12 6
tH 10 12 18 11
2019/11/12
BCDA
武汉理工大学管理学院 袁付礼
19
生
产
与 运 作
续
管
理
2
6
9
10
9
4
6
5
3
作业题：
作业
排序并计算 机床
加工周期。
t1
t2
2019/11/12
2019/11/12
武汉理工大学管理学院 袁付礼
9
生
产
与 运 作
三、单台机床作业排序方法
管
理
1×n流水排序型问题的优先规则：
先到先服务(FCFS)
最短作业时间(SPT) 最短交货延期量(EDD) SPT与EDD结合原则 最小松弛时间(SST) 后到先服务(LCFS)
按期完成作业项目最多的原则： 即先按交货期优先原则逐项安 排作业顺序，并依次计算每项 任务是否拖期，如果遇到某项 任务拖期，则将其移至最后加 工；之后，若又有任务拖期， 则又将其移至最后加工。
管
理
作业顺序是C-A-E-B-D-F
顺序 加工时间
流程时间
预定交货 期
C A E B D F 合计 平均
2019/11/12
4
4
4
2
6
7
5
11
15
8
19
16
10
29
17
12
41
18
41
110
110/41=2.68 110/6=18.33
武汉理工大学管理学院 袁付礼
延期天数(如果 为负则赋值0)
0 0 0 3 12 23 38 38/6=6.33
按期完成作业项目最多的原则
2019/11/12
武汉理工大学管理学院 袁付礼
10
生
产
与 运 作
三、单台机床作业排序方法
管
理
例：下表是在某工作中心等待加工的6项作业的 加工时间（包含换产时间）与预定日期，假设
工作的到达顺序与表中顺序相符 。根据以下规
则来决定其作业顺序：①FCFS②SPT③EDD④ SST并对它们分别进行评价。
8
12
6
7
T
T = 7+6+12+6+9+6 = 46
ABCDE 36776 58627
武汉理工大学管理学院 袁付礼
F 4 9
20
生
产 与 运
六、M台机器上N项作业的排
作 管
序(简称为N/M排序)
理
一般解法：分枝定界法
启发式算法——称为CDS算法，该算法是 将N/3的约贝扩展方法进一步扩展到一般 的N/M问题，以求得一个近似的最优解。 也叫坎贝尔-杜达克-史密斯法。
第三步，根据第1、第2、第3台，三台机器的操作 时间合并，以及第（M-2）、第（M-1）、第M台 三台机器的操作时间合并，又得到两组操作时间， 应用约贝规则，排出第3个作业顺序方案；
2019/11/12
武汉理工大学管理学院 袁付礼
22
生
产
与 运 作
CDS算法的步骤(续)
管
理
第四步，重复以上运算，最后将第1、第2、…， 第（M-1）共（M-1）台机器和操作时间合并， 以及将第2、第3、…、第M共（M-1）台机器的 操作时间合并，得到的两组操作时间，也应用约 贝规则，排出第（M-1）个作业顺序方案；
第i项任务的完成时刻(ci)为
ci = ri+ti1 +wi1+ti2+wi2+…+tim + wim
2019/11/12
武汉理工大学管理学院 袁付礼
6
生
产
与 运 作
计算公式(续)
管，则： m
ti ti1ti2 tim tij j1
令wi为作业任务i的总等候时间，则： m
A C E B D F 合计 平均
2019/11/12
2
2
7
4
6
4
5
11
15
8
19
16
10
29
17
12
41
18
41
108
108/41=2.63 108/6=18
武汉理工大学管理学院 袁付礼
延期天数(如果 为负则赋值0)
0 2 0 3 12 23 40 40/6=6.67
13
生
产
与 运 作
按EDD规则
合计 平均
41
133
133/41=3.24 133/6=22.17
57 57/6=9.5
2019/11/12
武汉理工大学管理学院 袁付礼
15
生
产
与 运 作
四、两台机床作业排序方法
管
理
加工顺序相同的若干个作业在两台机床上的加 工排序，我们运用约翰逊（Johnson）规则解决。 其步骤如下：
(1)列出每个作业在两台机床上的作业时间；
注意： 当满足 m atx 2m in t3或 m atx 2 m in t1时
此方法可得到最优解；否则，只能得到近似最优解。
2019/11/12
武汉理工大学管理学院 袁付礼
18
生
产 与 运
约翰逊(Johnson)规则的
作 管
扩展方法
理
例：4项作业在三台设备上进行加工，其 加工顺序相同，作业时间如下表所示:
14
生
产
与 运 作