工厂：对每个工人和工作地安排每天的生产任务，规 定开始时间和完成时间 医院：安排病人手术——安排手术室、配备手术器械、 手术医师和护士 学校：安排上课时间表，使学生能按规定的时间到规 定的教室听事先安排的教师讲课 项目计划管理：作业计划
（二）有关的名词术语（一）
排序——排序(Sequencing) ：确定零件在机器上的加工顺序 编制作业计划(Scheduling)：加工制造发生之前的活动（火 车时刻表）。包括确定加工顺序、加工任务的分配和加工每个 零件的开始和完成时间 调度：作业计划编制后实施生产控制所采取的一切行动（火 车运行的安排，发生晚点后的处理）
加工时间矩阵表
（3）延期量：交货期拖延的时间（D）
最大延期量:Dmax=max｛Di｝
总延期量：∑Di
（4）加工周期
C4
时间单台设备排序问题 √
多台设备排序问题
√单流件水作作业业排排序序问问题题
排
按工件到达车间
序
的情况
问
题
分 类
按目标函数的情 况
静态排序问题 动态排序问题 单目标排序问题 多目标排序问题
派工（ Dispatching ）：在作业计划制定以后，按照作业 计划的要求，将具体生产任务通过工票或施工单的形式下达 到具体的机床和工人 赶工（ Expediting ）：在实际进度已落后于计划进度时 采取的行动 控制（ Controlling ）：
（二）有关的名词术语（二）
机器——表示“服务者”，可以是工厂里的各种机床， 也可以是维修工人；可以是轮船要停靠的码头，也可以是 电子的计算机中央处理单元、存贮器和输入、输出单元 零件——代表“服务对象”。可以是单个零件，也可以 是一批相同的零件 加工路线——零件加工经过不同机器构成的路线。（某 零件要经过车、铣、占、磨的路线加工，我们可以用 M1,M2,M3,M4来表示） 加工顺序——表示每台机器加工n个零件的先后顺序，是 排序要解决的问题
加工时间矩阵表
Ji J2 J5 J6 J1 J4 J3
pi1 1 3 4 5 5 8
工
pi2 2 7 4 7 4 2
序
M1
M2
Fmax=28
时间
计算最长流程时间——表上计算法
加工时间矩阵表
Ji
J2
J5
J6
J1
J4
J3
pi1 1 1 3 4 4 8 5 13 5 18 8 26
pi2 2 3 7 11 4 15 7 22 4 26 2 28
第9章 制造业作业计划与控制
第一节 制造业作业计划
生产计划体系回顾 MRP——确定了各车间的零部件投入出产计划，将全厂
性的生产计划变成了各车间的生产任务。 车间——（1）安排任务：把生产任务安排到车间的每一
工作地并落实到每一个岗位的操作者；（2）保证完成任 务：通过对作业的实时监督与跟踪，使实际的生产进度按 计划要求按质按时按量完成——车间作业管理的主要内容 → 将任务安排到工作地，牵涉到任务分配和作业排序问题
工件编号 4 2 1 5 6 3
加工时间 2 8 7 5 6 10
等待时间 0 2 10 17 22 28
完成时间 2 10 17 22 28 38
交货期
10 12 14 14 18 20
拖期时间 0 0 3 7 10 18
注:总的拖期数是4件，平均拖期时间为： (0+0+3+7+10+18)/6=6.33,平均流程时间
组合原则
有时，需采用排序规则的组合进行排序。 例：SPT+MWRK+RANDOM，含义是首先选用
SPT规则选择下一个待加工的任务；若同时有多 个任务被选中，则采用MWRK规则再次选择；若 仍有多个任务被选中，最后采用RANDOM从中随 机选择一个作为下一个待加工的任务。 例： SPT+EDD
Johnson算法,其步骤： （1）从加工时间矩阵中找出最短的加工时间。
（2）若最短的加工时间出现在M1上，则对应的工件尽可能往 前排；若最短加工时间出现在M2上，则对应工件尽可能往后排。 然后，从加工时间矩阵中划去已排序工件的加工时间。若最短
加工时间有多个，则任挑一个。
（3）若所有工件都已排序，停止。否则，转步骤(1)。
例：5个工件经过4台设备加工，目标是使加工周 期最短的流水作业排序可以表示为： 5/4/F/ Fmax
二 单台设备排序问题
根据优先规则对每 一个达到的订单安
排作业顺序
（一）优先规则
1.SPT(shortest processing time)规则。优先选择 加工时间最短的工序。
——工件的平均流程时间最短，从而减少在制品。 2.FCFS(first come first served)规则。优先选择
(2+10+17+22+28+38)/6=19.5
表2 按照后来优先的规则排序
作业排序
123456
工件编号
654321
加工时间
6 5 2 10 8 7
等待时间
0 6 11 13 23 31
完成时间
6 11 13 23 31 38
交货期
18 15 10 20 12 14
拖期时间
0 0 3 3 19 24
回顾： 一、生产计划的总体框架
生产计划体系的总体框架
回顾：二、生产计划的系统结构
主生产计划
生产计划系统结构
作业排序（sequencing）
作业排序是解决各个生产层次中生产任务的加工顺序问题， 既包括哪个生产任务先投产，哪个生产任务后投入，还包 括在同一设备上不同工件的加工顺序。
作业排序（sequencing） ：确定工件在设备上的加工顺序
排序法则的应用范例
例：有6个工件需要在某台设备上加工,各工件的加工时 间如表1所示(工件编号是工件到达工作地的先后次序,当 前日期为0,采用以上六种排序方法进行排序.
工件的加工顺序与交货期
工件编号i
123456
加工时间
7 8 10 2 5 6
交货期
14 12 20 10 15 18
解: 表1 按照先来先加工的规则排序 作业排序 1 2 3 4 5 6 工件编号 1 2 3 4 5 6 加工时间 7 8 10 2 5 6 等待时间 0 7 15 25 27 32 完成时间 7 15 25 27 32 38 交货期 14 12 20 10 15 18 拖期时间 0 3 5 17 17 20
19.5
最小松动时间优先
5
8.86
22.83
临街比率优先
5
11.16
25.55
后来先加工
4
8.17
20.33
最短加工时间优先是最好的规则，因为其拖期数，平均拖 期时间，平均流程时间都是最小的，第二是交货期优先规则， 第三是后来先加工,第四是最小松动规则，第五是先来先加工 规则，临界比率优先规则最后。
例 求下表所示的6／2／P／Fmax问题的最优解。
加工时间矩阵表
Ji J1 J2 J3 J4 J5 J6 pi1 5 1 8 5 3 4 pi2 7 2 2 4 7 4
结果：
J2 J5 J6 J1 J4 J3 Fmax=28
J2 J5 J1 J6 J4 J3 J2 J5 J1 J4 J6 J3
计算最长流程时间——图示法
三 流水作业的排序问题
1. n/2/P/Fmax问题的最优算法 2. 一般n/m/P/Fmax问题的启发式算法 3. 相同零件、不同移动方式下加工周期的计算
（一） n/2/P/Fmax问题的最优算法
n个工件都必须经过机器1和机器2的加工，即工 艺路线是一致的。
n/2/P/Fmax问题的最优算法（一）
的最大流程时间。
n/2/P/Fmax问题的最优算法（二）
Johnson的改进算法,其步骤： ①将所有pi1≤pi2的工件按pi1值不减的顺序排成一个序列A。 ②将所有pi1＞ pi2的工件按pi2 值不增的顺序排成一个序列B。 ③将A放到B之前，就构成了最优加工顺序。 例 求下表所示的6／2／P／ Fmax问题的最优解。
（三）排序的目标函数
已知条件
零件加工工艺过程 作业时间ti 交货期 Ci
J1 J2
J3
t1
t2
t3
F1
F2
F3
F4
C1 C2 C3
（1）流程时间：任务在车间的停留时
间Fi
总流程时间：∑Fi
最大流程时间：Fmax=max｛Fi｝
J4
平均流程时间：∑Fi/n
（2）等待时间
t4
总等待时间
平均等待时间
按参数的性质
确定型排序问题 随机型排序问题
（五）排序问题的表示方法
排序问题的4参数表示法——n/m/A/B n——零件数 m——机器数 A——车间类型，
“F”——流水作业排序问题 “P”——流水作业排列排序问题√ “G”——一般单件作业排序问题 m＝1，A为空白 B——目标函数，通常是使其最小。 如：n/3/p/CMAX
pi2 2 3 7 11 7 18 4 22 4 26 2 28
Fmax=28
综上：
三个排序最短的最大流程时间相同 ——说明：当遇到相同的最小时间值时，可任选其
一排序，得到的就是最优排序 Johnson规则只是一个充分条件，不是必要条件。 ——请同学们课下计算排序： J2 J5 J6 J4 J1 J3
时间是主要的 7.SCR(smallest critical ratio)规则。优先选择临界比最小的
工件。 临界比率=（交货期-当前日期）/作业时间
——保证工件延误时间最少的法则
（一）优先规则（续）