一、最长流程时间Fmax的计算
• n/m/P/Fmax问题，n个零件要按相同的加工路线经 过m台机器加工，目标是使这批零件的最长流程时 间最短。 • 最长流程时间又称加工周期，它是从第一个零件 在第一台机器开始加工时算起，到最后一个零件 在最后一台机器上完成加工时为止所经过的时间。
• 例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当 按顺序S=（6，1，5，2，4，3）加工时，求Fmax。
机壳1 机壳2 机壳4 机壳3 机壳5 总数 平均数 0 8 14 17 32
加工 时间
8 6 3 15 12
结束 工作
8 14 17 32 44
流程 时间
8 14 17 32 44 115 23.0
预计顾客 取货时间
10 12 18 20 22
顾客实际 取货时间
10 14 18 32 44 118
• 根据工件到达系统的情况
–静态排序 –动态排序
• 根据参数的性质
–确定型排序 –随机型排序
4参数法 • • • • n/m/A/B 其中，n为工件数 m为机器数 A车间类型。在A的位置若标以标以“P”， 则表示流水作业排列排序问题；若标以 “G”，则表示一般单件作业排序问题。当 m=1，则A处为空白。 • B为目标函数，通常是使其值最小 • 例如：n/3/P/Cmax
提前 小时数
2
拖延 小时数
2
1 12 22 3 0.6 36 7.2
平均在制品库存=115/44=2.61个
平均总库存=118/44=2.68个
比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程 时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务 （平均延迟时间较少），它也提供了更低的总库存水平。 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。
有关符号
• • • • • • • • • • • Ji：工件i，i=1，2，…，n Mj：机器j，j=1，2，…，n pij为Ji在Mj上的加工时间 ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最 早时间 di为Ji的完工期限 Ci为Ji的完工时间 Cmax为最长完工时间 Fi为Ji的流程时间，即工件在车间的实际停留时间 Fmax为最长流程时间 Li为工件的延迟时间 Lmax为最长延迟时间
一般作业排序的目标 满足顾客或下一道工序的交货期要求 流程时间最短 准备时间最短或成本最小化 在制品库存最低发动机机壳，现在共有5个机壳 等待加工。只有一名技工在岗，做此项工作。现在已经估算 出各个机壳的标准加工时间，顾客也已经明确提出了他们所 希望的完工时间。下表显示了周一上午的情况，顾客的取货 时间用从周一上午开始，还有多少工作小时来计算。
【例】求如表所示的6/2/F/Fmax问题的最优解。
i 1 2 3 4 5 6
ai
bi
5
7
1
2
8
2
5
4
3
7
4
4.5
将零件2排第1位 将零件3排第6位 将零件5排第2位 将零件6排第3位 将零件4排第5位 将零件1排第4位
2 2 2 2 2 2
5 5 5 5
6 6 6
1
4 4
3 3 3 3 3
【例 题】
编制作业计划要解决的问题
• 由于每台机器都可能被分配了多项任务，就带来了 零件在机器上加工的顺序问题。 • 编制作业计划要解决先加工哪个工件、后加工哪个 工件的加工顺序问题
• 确定机器加工每个工件的开始时间和完成时间
• 例如;医院要安排病人手术，为此要安排手术室， 配备手术器械、手术医师和护士。
第一节 排序问题的基本概念
• 3.在制品库存（WIP）
• 在制品是对介于原材料和成品之间的生产过程中 的产品的称谓。一个工件正从一个工作地移向另 一个，由于一些原因被拖延加工，正在被加工或 放置于零件库中，都可以看作在制品库存。
• 4.利用率
• 用一台机器或一个工人的有效生产时间占总工作 时间的百分比来表示。
五、优先调度规则
• • • •
11.1 作业计划问题的基本概念 11.2 流水作业排序问题 11.3 单件作业的排序问题 11.4 生产作业控制
11 收入、费用和利润
学习目的与要求
要求掌握：
1. 最长流程时间的计算 2.约翰逊算法
3.一般流水作业排序问题的3种启发式算法
4. 相同零件的3种移动方式下机器加工周期的计算方法
教学重点与难点 重点
最长流程时间的计算
约翰逊算法
相同零件的3种移动方式下机器加工周期的计算方法
难点
一般流水作业排序问题的启发式算法
生产任务的最终落实
• MRP确定各车间的零部件投入出产计划，将全 厂性的产品出产计划变成了各车间的生产任务。 • 各车间要将车间的生产任务变成各个班组、各 个工作地和各个工人的任务。 • 将任务安排到工作地，牵涉到作业计划。
• 有5件任务都需要两步操作（先1后2）来完成，下表给出了相 应的时间： • （1）根据Johnson算法安排工作顺序； • （2）计算加工周期。 任务 A B C D 操作1所需时间（小 时） 3.0 2.0 1.0 3.0 操作2所需时间（小 时） 1.2 2.5 1.6 3.0
E
3.5
1.5
任务
i
Pi1
Pi 2 Pi 3 Pi 4
1 4
2 2
3 3
4 1
5 4
6 2
4
5 4
5
8 2
6
7 4
7
5 3
4
5 3
5
5 1
i pi pi
1
6 22 5 5
7
12
1 4 4 5
6
5 4
10
2
4
12
3
13
2
5
1
3
16
11
17
pi
pi
4 3
2
4 5
15
22
20
30
7 27 5
35
6 33 7
42
8
1 13
第十一章 制造业作业计划与控制
• 引言 • 通过MRP确定各车间的零部件投入出产计划， 从而将全厂性的产品出产计划变成了各车间生 产作业计划，将车间的生产任务变成各个班组、 各个工作地和各个工人的任务。只有将计划安 排到工作地和工人，任务才算真正落到实处。 将任务安排到工作地，牵涉到任务分配和作业 排序问题，这正是本章要讨论的。
3 6 8 12 15
结束 工作
3 9 17 29 44
流程 时间
3 9 17 29 44 102 20.4
预计顾客 取货时间
18 12 10 22 20
顾客实际 取货时间
18 12 17 29 44 120
提前 小时数
15 3
拖延 小时数
7 7 24 18 3.6 38 7.6
平均在制品库存=102/44=2.32个
4 21
3 25
2 32
3 38
4 46
二、两台机器排序问题
• 两个或更多的作业必须在两台机器上以相同的工序进行加 工，要使加工周期最短，约翰逊于1954年提出了一个有效 算法，那就是著名的Johnson算法。约翰逊算法包括以下 几个步骤： • （1）列出每个作业在两台机器上的加工时间。 • （2）选择最短的加工时间，如果有两个相同的值，则任 选一个。 • （3）如果最短的加工时间来自第一台机器，那么先完成 这个作业；如果来自第二台机器，那么这个作业就放在最 后完成。然后从加工时间矩阵中划去已排序工件的加工时 间。 • （4）对于剩余的作业重复第二步和第三步，直到整个排 序完成。
• 一、名词术语
• 排序：确定工件在机器上的加工顺序。 • 作业计划：不仅要确定工件的加工顺序，而且还 要确定机器加工每个工件的开始时间和完成时间。 通常情况下都是按最早可能开（完）工时间来编 制作业计划。 • 派工：按作业计划的要求，将具体生产任务安排 到具体的机床上加工。 • 赶工：实际进度已落后于计划进度时采取的行动。
平均总库存=120/44=2.73个
流程时间=等待时间+加工时间 平均在制品库存=各工件流程时间之和÷加工周期 平均总库存=各工件实际取货时间之和÷加工周期 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。
EDD规则排序结果
机壳加 开始 工次序 工作
发动机机壳 所需标准加工时间 （包括机器调整）
机壳1 机壳2 8 6
预计顾客取货时间 （从现在开始算起的所需工作 时间）
10 12
机壳3
机壳4 机壳5
15
3 12
20
18 22
SPT规则排序结果
机壳加 开始 工次序 工作
机壳4 机壳2 机壳1 机壳5 机壳3 总数 平均数 0 3 9 17 29
加工 时间
• 调度方法：
• 所谓调度方法，就是运用若干预先规定的优先顺 序规则，顺次决定下一个应被加工的工件的排序 方法。 • 一个工作地可选择的下一个工件会有很多种，因 此，按什么样的准则来选择，对排序方案的优劣 有很大影响。
常用的优先顺序规则：
• • • • • • • • FCFS规则 优先选择最早进入可排序集合的工件。 EDD规则 优先选择完工期限最紧的工作。 SPT规则 优先选择加工时间最短的工件。 SCR规则 优先选择临界比最小的工件。临界比为工作 允许停留时间和工件余下加工时间之比。 MWKR规则 优先选择余下加工时间最长的工件。 LWKR规则 优先选择余下加工时间最短的工件。 MOPNR规则 优先选择余下工序数最多的工件。 RANDOM规则 随机地挑选下一个工件。