一、n种工件在单台设备上加工的排序
J1
J2
J3
机器
Jn
到达系统工 件的集合
离开系统 （机器）
为实现任务总等待时间最短的目标，保证尽可能 多的对象早日加工出来，加速资金周转，只需根 据最短加工时间准则对加工对象排序即可。
二、 n个工件在两台机器的排序问题
n个工件都必须经过机器1和机器2的加 工，即工艺路线是一致的。
• FCFS主要局限在于加工时间过长，常会使其它作业延期。
• SST考虑到了各任务在完成过程中的松紧缓急
• EDD会造成有的作业等待加工的时间很长，使在加工存货 与车间的拥挤程度增加。
第四节 制造业中的排序问题
一、n种工件在单台设备上加工的排序 二、n个工件在两台机器的排序问题 三、相同零件、不同移动方式下加工周期的计算
2
8
6
4
3
解：由约翰逊法可知，表中最小加工时间值是1个时 间单位，它又是出现在设备A上，根据约翰逊法的 规则，应将对应的工件4排在第一位，即得：
J4 - * - * - * - *
去掉J4，在剩余的工件中再找最小值，不难看出 ，最小值是2个时间单位，它是出现在设备B上的 ，所以应将对应的工件J1排在最后一位，即：
• “派工”，是按作业计划的要求，将具体生产任务安排到 具体的机床上加工。
• “赶工”，是实际进度已落后于计划进度时采取的行动。
• “加工路线”是工件加工的工艺过程决定的，是工件加工 在技术上的约束。比如，工件要经过车、铣、刨、磨、钻 的路线加工，我们可以用M1、M2、M3、M4、M5来表示。加 工顺序则表示每台机器加工n个工件的先后顺序，是排序 、编制作业计划、派工等要解决的问题。
你觉得应以怎样的准则排队？
• 超市收银 • 订单交货期不同时 • 病人看病 • ………
• 例：一个车间有一台加工中心，现有5个 工件需要该机器加工。相关的加工时间和
要求完成时间（交货期）如下表所示。
• SPT准则一般是作业通过时间最少和工作中心作业平均数 最少及利用率最大的最好方法。其主要缺点是让耗时长的 作业等待，特别当新的时间短的作业不断添加到系统中时， 等待的时间可能会相当长。
B——目标函数
• 研究排序问题，一般要做以下假设
–1、一个工件不能同时在几台不同的机器上加工 –2、工件在加工过程中采取平行移动方式，即当上道工
序完工后，立即送下道工序加工 –3、不允许中断。当一个工件一旦开始加工，必须一直
进行到完工，不得中途停止加入其它工件。 –4、每道工序只在一台机器上完成 –5、工件数、机器数和加工时间已知，加工时间与加工
第一节 生产作业计划概述
一、什么是生产作业计划？
• 作业计划就是安排零部件（作业、活动） 的加工顺序、出产数量、设备及人工使用、 投入时间及出产时间的计划。
• 在空间上把生产任务细 分到车间、工段、班组、 机台和个人；
• 在时间上把年、季较长 计划期的任务细分到月、 旬、周、日、轮班和小 时
• 在计划单位上把产品细 分到零件和工序
C（6）
A（15）
B（8）
总 装
D（7） C(5)
A(4)
B(10)
三、排序的目标
排序的目标
满足交货期
充分利用资源
作业排a /b 序c
缩短生产周期 降低准备成本
降低在制品库存
四、排序问题的分类和表示
（一）分类
行业
排序对象
排
序
问
服务者数量
题
的
分
加工路线
类
服务对象到达
服务业的排序问题 制造业的排序问题
第十一章
生产作业计划与控制
本章内容
• 第一节 生产作业计划概述 • 第二节 排序问题概述 • 第三节 作业排序的规则 • 第四节 制造业中的排序问题 • 第五节 生产作业控制 • 第六节 项目作业计划
重点掌握
排序规则和评价标准 不同移动方式下的生产周期计算 生产作业排序（约翰逊算法） 项目作业计划
部 装
A（15）
B（8）
C(6)
D（12）
总 装
A(4)
B（10）
C(5)
D(7)
（b）装配顺序为C→B→D→A，总装配时间为45小时
部 装
C（6） B（8）
总 装
C(5)
D（12）
a/b c
A（15）
B（10）
D（7）
A(4 )
（c）装配顺序为D→C→A→B，总装配时间为51小时
部 装
D(12)
三、相同零件、不同移动方式下加工周期的计算
加工一批相同工件时时，制品在生产过程 中的移动方式对生产周期有直接的影响。 制品在生产过程中的移动方式有三种：
– 顺序移动方式 – 平行移动方式 – 平行顺序移动方式
1、顺序移动
一批零件在上道工序全部加工完毕后才整批 转移到下道工序继续加工。
工序
第1道工序 t1
J1 J2
机器1
J3
Jn
到达系统工
件的集合
机器2
离开系统 （机器）
1 两台机器排序问题的目标 • 两台机器排序的目标是使最大完成时间（总加
工周期）Fmax最短。 Fmax的含义见如下的甘特
图(Gantt Chart)。
机器 A
B
在机器A上的作业时间
总加工周期
Fmax
时间
• 多台机器排序的目标一般也是使最大完成时间（总加
二、编制作业计划与排序
• 由于编制作业计划的主要问题是确定各台机器上 工件的加工顺序，因此“排序”很多时候等同于 “编制作业计划”
• 作业计划常涉及到另外几个概念：
– 派工 – 赶工 – 调度 – 控制 – 排程 – 工艺路线
• “排序”，确定工件在机器上的加工顺序
• “编制作业计划”，确定每个工件在机器上的加工顺序， 同时确定机器加工每个工件的开始时间和完工时间。
3
A
9
16 17 22
B
0
35
17 23
J1 - J2 - J3- J4 - J5
A 367 15 B 286 43
27 30 30
1
7
A
B
1
57
14 19 22

21 24 26
26
J4 - J2 - J3- J5 - J1 A1 675 3 B4 863 2
(a) J1 - J2 - J3- J4 - J5
④ 排除已安排好的工件，在剩余的工件中重复步骤 (2)和(3)，直到所有工件都安排完毕。
例：某一班组有A、B两台设备，要完成5个工件的加 工任务。每个工件在设备上的加工时间如下表所 示。求总加工周期最短的作业顺序。
工件在两台设备上的加工时间
工件编号
J1 J2 J3 J4 J5
设备A
3
6
7
1
5
设备B
工周期） Fmax最短。
2 两台机器排序问题的算法
• 实现两台机器排序的最大完成时间Fmax最
短的目标——优化算法就是著名的约翰逊 法(Johnson’s Law)。
• 约翰逊法解决这种问题分为4个步骤：
① 列出所有工件在两台设备上的作业时间。
② 找出作业时间最小者。
③ 如果该最小值是在设备1上，将对应的工件排在前 面，如果该最小值是在设备2上，则将对应的工件 排在后面。
服务者排序问题 服务对象排序问题 单服务者排序问题 多服务者排序问题 流水作业排序问题 非流水作业排序问题 静态作业排序问题 动态作业排序问题
（二）排序问题的表示
• n/m/A/B
n——工件数 m——机器数 A——车间类型（m=1为空白）：
A=F代表流水作业排序 A=P代表流水作业排列排序 A=G代表单件作业排序
120
160 时间
2、平行移动方式
每个零件在前道工序加工完毕后，立即转移 到下道工序继续加工，形成前后交叉作业。
工序
t1
t2 t3 t4
时间
• 优点：加工对象没有等待，生产周期短 • 缺点：运输工作量大而频繁，且在工序时间不均衡时造成
许多工作地人机负荷不足，设备会出现间断性停歇 • 适用对象：工序单件加工时间比较协调（如接近或成整数
工序
t1
t2 t3
30
t4 75 85
时间
3、平顺移动方式
• 当ti≤ti+1时，零件按平行移动方式转移； • 当ti＞ti+1时，只有当前道工序上完工的零件数量
足以保证后道工序连续加工时，才开始将完工的零 件转入后道工序。这样既可以避免后道工序发生工 作时断时续的现象，又可以集中利用时间。
工序
t1
• 在以下情况将出现排队现象： –平均到达率（工件/小时）高于平均服务率（工件/小时) –工件到达的间隔时间不一样 –机器加工时间不一样
二、一个排序的例子
四种型号的电视机的装配工时定额
型号
A B C D
部装定额工时 （小时）
15 8 6 12
总装定额工 时（小时）
4 10 5 7
（a）装配顺序为A→B→C→D，总装配时间为48小时
倍），加工对象体积较大
工序
t1
t2 t3 t4
时间
按平行移动方式，加工完这一批零 件需要多长时间？
一批零件的加工周期为：
m
T 平 ti (n 1)t L i 1
t L 最长的单件工序时间
例：已知n=4，t1=10分，t2＝5分钟，t3＝15分钟 ，t4＝10分钟，求T平:
T平＝（10＋5＋15＋10）＋（4-1) ×15 =85(分钟）
• 由该系统的平均工作数量（Average number of jobs）来 评价。