任务
A B C D E
操作1所需时间（小 时） 3.0 2.0 1.0 3.0 3.5
操作2所需时间（小 时） 1.2 2.5 1.6 3.0 1.5
任务 A B C D E
操作1所需时间（小时） 3.0 2.0 1.0 3.0 3.5
操作2所需时间（小时） 1.2 2.5 1.6 3.0 1.5
• [例] 一个加工车间负责加工发动机机壳，现在共有5个机壳 等待加工。只有一名技工在岗，做此项工作。现在已经估算 出各个机壳的标准加工时间，顾客也已经明确提出了他们所 希望的完工时间。下表显示了周一上午的情况，顾客的取货 时间用从周一上午开始，还有多少工作小时来计算。
发动机机壳
机壳1 机壳2 机壳3 机壳4 机壳5
• 3.在制品库存（WIP）
• 在制品是对介于原材料和成品之间的生产过程中 的产品的称谓。一个工件正从一个工作地移向另 一个，由于一些原因被拖延加工，正在被加工或 放置于零件库中，都可以看作在制品库存。
• 4.利用率
• 用一台机器或一个工人的有效生产时间占总工作 时间的百分比来表示。
五、优先调度规则
近。LWKR法则，使工作量小的工件尽快完成。
第二节 流水作业排序问题
• 流水作业排序问题的基本特征是每个工件的加工 路线都一致。
• 加工路线一致，是指工件的流向一致，并不要求 每个工件必须经过加工路线上每台机器加工。
• 对于流水作业排序问题，工件在不同机器上的加 工顺序不尽一致。
• 排列排序问题：所有工件在各台机器上的加工顺 序都相同的情况。
顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。
优先调度法则
• 按SPT法则可使工件的平均流程时间最短，从而减 少在制品量。
• FCFS法则来自排队论，它对工件较公平。 • EDD法则可使工件延误时间最小。 • MWKR法则使不同工作量的工件的完工时间尽量接
机壳3 29 15 44 44
总数
102
平均数
20.4
平均在制品库存=102/44=2.32个
预计顾客 取货时间
顾客实际 提前 拖延 取货时间 小时数 小时数
18
18
15
12
12
3
10
17
7
22
29
7
20
44
24
120
18
38
3.6 7.6
平均总库存=120/44=2.73个
流程时间=等待时间+加工时间 平均在制品库存=各工件流程时间之和÷加工周期 平均总库存=各工件实际取货时间之和÷加工周期
• 对于多台机器排序问题，根据加工路线的特征，分成 –单件作业排序(Job - Shop)问题 –流水作业排序(Flow - Shop)问题
• 工件的加工路线不同，是单件作业排序问题的基本特征； • 所有工件的加工路线完全相同，是流水作业排序问题的
基本特征。也就是说，每个零件都顺序地经过线上不同 机器加工，它们的加工路线一致。
• 将任务安排到工作地，牵涉到作业计划。
编制作业计划要解决的问题
• 由于每台机器都可能被分配了多项任务，就带来了 零件在机器上加工的顺序问题。
• 编制作业计划要解决先加工哪个工件、后加工哪个 工件的加工顺序问题
• 确定机器加工每个工件的开始时间和完成时间 • 例如;医院要安排病人手术，为此要安排手术室，
工序完工后，立即送下道工序加工。 • 3.不允许中断。一个工件一旦开始加工，必须一直进
行到完工，不得中途停止插入其他工件。 • 4.每道工序只在一台机器上完成。 • 5.工件数、机器数和加工时间已知，加工时间与加工
顺序无关。 • 6.每台机器同时只能加工一个工件
有关符号
• Ji：工件i，i=1，2，…，n • Mj：机器j，j=1，2，…，n • pij为Ji在Mj上的加工时间 • ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最
3
pi 113 4 21 3 25 2 32 3 38 4 46
4
二、两台机器排序问题
• 两个或更多的作业必须在两台机器上以相同的工序进行加 工，要使加工周期最短，约翰逊于1954年提出了一个有效 算法，那就是著名的Johnson算法。约翰逊算法包括以下 几个步骤：
• （1）列出每个作业在两台机器上的加工时间。 • （2）选择最短的加工时间，如果有两个相同的值，则任
第十一章 制造业作业计划与控制
• 引言 • 通过MRP确定各车间的零部件投入出产计划，
从而将全厂性的产品出产计划变成了各车间生 产作业计划，将车间的生产任务变成各个班组、 各个工作地和各个工人的任务。只有将计划安 排到工作地和工人，任务才算真正落到实处。 将任务安排到工作地，牵涉到任务分配和作业 排序问题，这正是本章要讨论的。
i123456 Pi1 4 2 3 1 4 2 Pi 2 4 5 6 7 4 5 Pi3 5 8 7 5 5 5 Pi4 4 2 4 3 3 1
i6 1 5 2 4
3
pi 22 46
1
410
212 113
3 16
pi 5 7 4 11 4 15 5 20 7 27 6 33
2
pi 5 12 5 17 5 22 8 30 5 35 7 42
一、最长流程时间Fmax的计算
• n/m/P/Fmax问题，n个零件要按相同的加工路线经 过m台机器加工，目标是使这批零件的最长流程时 间最短。
• 最长流程时间又称加工周期，它是从第一个零件 在第一台机器开始加工时算起，到最后一个零件 在最后一台机器上完成加工时为止所经过的时间。
• 例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当 按顺序S=（6，1，5，2，4，3）加工时，求Fmax。
0 1.0
3.0
6.0
操作1 C,1 B,2
D,3
操作2
C,1.6
B,2.5
2.6
5.5
E,3.5 D,3.0
9.5 A,3.0
E,1.5
9.0
11
12.5
13.7 A, 1.2
0 1.0
3.0
6.0
操作1 C,1 B,2
D,3
操作2
C,1.6
B,2.5
2.6
5.5
E,3.5 D,3.0
9.5 A,3.0
早时间 • di为Ji的完工期限 • Ci为Ji的完工时间 • Cmax为最长完工时间 • Fi为Ji的流程时间，即工件在车间的实际停留时间 • Fmax为最长流程时间 • Li为工件的延迟时间 • Lmax为最长延迟时间
三、排序问题的分类
• 根据机器数的多少
–单台机器的排序问题 –多台机器的排序问题
四、作业排序方案的评价标准
• 1.工作流程时间
• 从工件可以开始加工至完工的时间，包括在各个机器 之间的移动时间、等待时间、加工时间以及由于机器 故障、部件无法得到等问题引起的延误时间等。
• 2. 加工周期
• 完成一组工作所需的全部时间。它是从第一个工件在 第一台机器上开始加工时算起，到最后一个工件在最 后一台机器上完工时为止所经过的时间。
5
6
ai
5
1
8
5
3
4
bi
7
2
2
4
7
4.5
将零件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
【例 题】
• 有5件任务都需要两步操作（先1后2）来完成，下表给出了相 应的时间：
• （1）根据Johnson算法安排工作顺序； • （2）计算加工周期。
• 11.1 作业计划问题的基本概念 • 11.2 流水作业排序问题 • 11.3 单件作业的排序问题 • 11.4 生产作业控制
11 收入、费用和利润
学习目的与要求
要求掌握： 1. 最长流程时间的计算 2. 2.约翰逊算法 3.一般流水作业排序问题的3种启发式算法 4. 相同零件的3种移动方式下机器加工周期的计算方法
允许停留时间和工件余下加工时间之比。 • MWKR规则 优先选择余下加工时间最长的工件。 • LWKR规则 优先选择余下加工时间最短的工件。 • MOPNR规则 优先选择余下工序数最多的工件。 • RANDOM规则 随机地挑选下一个工件。
一般作业排序的目标
➢满足顾客或下一道工序的交货期要求 ➢流程时间最短 ➢准备时间最短或成本最小化 ➢在制品库存最低 ➢机器设备或劳动力利用最大化
总数
115
平均数
23.0
平均在制品库存=115/44=2.61个
预计顾客 取货时间
顾客实际 提前 拖延 取货时间 小时数 小时数
10
10
2
12
14
2
18
18
1
20
32
12
22
44
22
118
3
36
0.6 7.2
平均总库存=118/44=2.68个
比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程 时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务 （平均延迟时间较少），它也提供了更低的总库存水平。
配备手术器械、手术医师和护士。
第一节 排序问题的基本概念
• 一、名词术语
• 排序：确定工件在机器上的加工顺序。 • 作业计划：不仅要确定工件的加工顺序，而且还
要确定机器加工每个工件的开始时间和完成时间。 通常情况下都是按最早可能开（完）工时间来编 制作业计划。 • 派工：按作业计划的要求，将具体生产任务安排 到具体的机床上加工。 • 赶工：实际进度已落后于计划进度时采取的行动。