M1
1， 1，1
2 ，2，1
23
7
M2
2.3.2
1.3.2
7
12 13
M3
2.1.3
3
1.2. 3 7
0 图 11 － 2 无延迟作业计划
时间
31
Oj 1.1.1 2.1.3 1.2.3 2.2.1 2.3.2 1.3.2
工业工程教研室
32
优先派工法则
在介绍无延迟作业计划的构成步骤时，其中第③步的两个条件一般 都有多个工序可以满足。按什么样的准则来选择可安排的工序，对 作业计划的优劣有很大影响。为了得到所希望的作业计划，人们提 出了很多优先调度法则，按优先调度法则挑选工序比随意挑选一道 工序的方法更能符合计划编制者的要求，同时又不必列出所有可能 的作业计划，从而计算量小。
23
7
M2
1.3.2
8
M3
2.1.3
1.2.3
3
7
0
2.3.2
29
T*
M*
Oj
2
M1
1.1.1
3
M3
2.1.3
7
M3
1.2.3
M1
7

M1
2.2.1
8
M2
1.3.2
13
M2
2.3.2
时间
工业工程教研室
30
无延迟作业计划
① 设t＝1，{S1}为空集，{O1}为各工件第一道工序的集合。 ② 求T*＝min{Tk}，并求出T*出现的机器M*。如果M*有多台， 则任选一台（最早开始加工的机器先加工）。 ③ 从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工， 且Tj=T*。 ④ 将确定的工序Oj放入{St}，从{ Ot }中消去Oj，并将Oj的紧 后工序放入{ Ot }，使t＝t＋1。 ⑤ 若还有未安排的工序，转步骤②；否则，停止。
工业工程教研室
6
有关名次术语
“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮 船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输 入、输出单元。一句话，表示“服务者”
“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相 同的零件
“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上 的约束
工业工程教研室
无延迟作业计划的构成
t
{O t}
Tk
T k’
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
3
1.2.3
3
7
3
M3
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
1.3.2
12
13
12
M2
机
器
“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制 作业计划要解决的问题
工业工程教研室
7
排序问题的分类
对于多台及其的排序问题，按照工件加工路线的特征，可以分为单 件作业排序和流水作业排序问题：
单件作业排序：工件的加工路线不同； 流水作业排序：所有工件的加工路线完全相同；
工业工程教研室
27
能动作业计划的构成
我们称每安排一道工序称作一“步”，设 {St}──t步之前已排序工序构成的部分作业计划； {Ot}──第t步可以排序的工序的集合； Tk ──{ Ot }中工序Ok的最早可能开工时间； Tk’ ──{ Ot }中工序Ok的最早可能完工时 间。
工业工程教研室
28
能力作业计划的构成步骤
第十讲
制造业生产作业计划
E C J T
U N I V E R S I T Y
2
工业工程教研室
3
工业工程教研室
4
编制作业计划要解决的问题
编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化 目标，确定各种资源利用的时间问题。
由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的 约束，就带来了零件在机器上加工的顺序问题。
工业工程教研室
24
更为复杂的加工矩阵和加工时间矩阵
m1 m2 m3 m4 m5 m1 m3 m5 m4 m2
m3 m4 m2 m5 m1 m4 m3 m1 m5 m2 m2 m4 m3 m5 m1
05:22 08:22 05:00 11:22 2:21
01:20 03:00 05:12
02:21 09:30 08:23
工业工程教研室
零件的三种移动方式比较
比较项目 平行移动
19
平行顺序移动 顺序移动
生产周期 短 运输次数 多 设备利用 差 组织管理 中
中 中 好 复杂
长 少 好 简单
工业工程教研室
20
工业工程教研室
21
工业工程教研室
22
单件作业排序问题
单件作业排序问题的特点
每一个工件都有各自的加工路线，工件没有一定的流向。
区别：流水作业中工件的加工路线一致，工件的第K道工序永远在MK
上加工，工序编号和机器编号不一致
工业工程教研室
23
单件作业排序问题描述方法
加工描述矩阵和加工时间矩阵
1,1,1 1,2,3 1,3,2 D＝
2,1,3 2,2,1 2,3,2
241 T＝
345
描述一道工序需要三个参数： 工件号，工序号，机器号。 用（i,j,k）来表示工件i的第j道工序在机器k上进行加工
工业工程教研室
26
一般n/m/G/Fmax问题的算法
半能动作业计划：各工序按照最早可能开（完）工时间安排的作 业计划
能动作业计划：任何一台机器的每段空余时间都不足于加工一道 可加工工序的半能动作业计划。
无延迟作业计划：没有出现任何延迟（有工件等待加工时，机器 出现空闲）的能动作业计划
工业工程教研室
三种典型的移动方式 顺序移动方式：一批零件全部加工完成后，整批移动到下道工 序加工 平行移动方式：单个零件加工完成后，立即移动到下道工序加 工 平行顺序移动方式：两者混合
工业工程教研室
16
顺序移动方式
设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间， 只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单 件工时为ti（分钟/件），i=1.2…n. 则该批零件的加工周期为：
⑤ 若还有未安排的工序，转步骤②；否则，停止。
工业工程教研室
能力作业计划
t
{O t}
Tk
T k’
1
1.1.1
0
2
2.1.3
0
3
2
1.2.3
2
6
2.1.3
0
3
3
1.2.3
3
7
2.2.1
3
7
4
1.3.2
7
8
2.2.1
3
7
5
1.3.2
7
8
2.3.2
7
12
6
2.3.2
8
13
机
器
M1
1 ，1 ，1
2 ，2，1
① 设t＝1，{S1}为空集，{O1}为各工件第一道工序的集合。 ② 求T*＝min{Tk’}，并求出T*出现的机器M*。如果M*有多台， 则任选一台（能够最早完工的机器先完成加工任务）。
③ 从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加 工，且Tj<T*。
④ 将确定的工序Oj放入{St}，从{ Ot }中消去Oj，并将Oj的紧 后工序放入{ Ot }，使t＝t＋1。
工业工程教研室
13
求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法
Palmer法 CDS法
工业工程教研室
14
CDS
Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson
算法用于一般的n/m/P/Fmax问题，得到(ｍ－1)个加工顺序，取其中优者.
m
Tnt1nt2...ntmnti
i1
工业工程教研室
17
平行移动方式
零件平行移动的加工周期 T 平 为：
工业工程教研室
18
平行顺序移动方式
1.当ti<ti+1时，零件按照平行移动的方式转移； 2.当ti>=ti+1,以i工序的最后一个零件完工的时间为基准，往前推移(n1)*ti+1作为零件在i+1工序开始加工的时间。
工业工程教研室
33
8种常见的优先派工法则
① SPT(Shortest Processing Time)法则 优先选择加工时间最 短的工序。
② FCFS(First Come First Served)法则 优先选择最早进入可 排工序集合的工件。
③ EDD(Earliest Due Date)法则 优先选择完工期限紧的工件。 ④ MWKR(Most Work Remaining)法则 优先选择余下加工时间最 长的工件。 ⑤ LWKR(Least Work Remaining)法则 优先选择余下加工时间 最短的工件。 ⑥ MOPNR(Most Operations Remaining)法则 优先选择余下工 序数最多的工件。 ⑦ SCR(Smallest Critical Ratio)法则 优先选择临界比最小 的工件。临界比为工件允许停留时间与工件余下加工时间之比。 ⑧ RANDOM法则 随机地挑一个工件