任务
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
• 调度方法：
• 所谓调度方法，就是运用若干预先规定的优先顺 序规则，顺次决定下一个应被加工的工件的排序 方法。
• 一个工作地可选择的下一个工件会有很多种，因 此，按什么样的准则来选择，对排序方案的优劣 有很大影响。
常用的优先顺序规则：
• FCFS规则 优先选择最早进入可排序集合的工件。 • EDD规则 优先选择完工期限最紧的工作。 • SPT规则 优先选择加工时间最短的工件。 • SCR规则 优先选择临界比最小的工件。临界比为工作
总数
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规则，可以给顾客提供更好的服务 （平均延迟时间较少），它也提供了更低的总库存水平。
选一个。
• （3）如果最短的加工时间来自第一台机器，那么先完成 这个作业；如果来自第二台机器，那么这个作业就放在最 后完成。然后从加工时间矩阵中划去已排序工件的加工时 间。
• （4）对于剩余的作业重复第二步和第三步，直到整个排 序完成。
【例】求如表所示的6/2/F/Fmax问题的最优解。
i
1
2
3
4
• 3.在制品库存（WIP）
• 在制品是对介于原材料和成品之间的生产过程中 的产品的称谓。一个工件正从一个工作地移向另 一个，由于一些原因被拖延加工，正在被加工或 放置于零件库中，都可以看作在制品库存。
• 4.利用率
• 用一台机器或一个工人的有效生产时间占总工作 时间的百分比来表示。
五、优先调度规则
工序完工后，立即送下道工序加工。 • 3.不允许中断。一个工件一旦开始加工，必须一直进
行到完工，不得中途停止插入其他工件。 • 4.每道工序只在一台机器上完成。 • 5.工件数、机器数和加工时间已知，加工时间与加工
顺序无关。 • 6.每台机器同时只能加工一个工件
有关符号
• Ji：工件i，i=1，2，…，n • Mj：机器j，j=1，2，…，n • pij为Ji在Mj上的加工时间 • ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最
近。LWKR法则，使工作量小的工件尽快完成。
第二节 流水作业排序问题
• 流水作业排序问题的基本特征是每个工件的加工 路线都一致。
• 加工路线一致，是指工件的流向一致，并不要求 每个工件必须经过加工路线上每台机器加工。
• 对于流水作业排序问题，工件在不同机器上的加 工顺序不尽一致。
• 排列排序问题：所有工件在各台机器上的加工顺 序都相同的情况。
四、作业排序方案的评价标准
• 1.工作流程时间
• 从工件可以开始加工至完工的时间，包括在各个机器 之间的移动时间、等待时间、加工时间以及由于机器 故障、部件无法得到等问题引起的延误时间等。
• 2. 加工周期
• 完成一组工作所需的全部时间。它是从第一个工件在 第一台机器上开始加工时算起，到最后一个工件在最 后一台机器上完工时为止所经过的时间。
4
二、两台机器排序问题
• 两个或更多的作业必须在两台机器上以相同的工序进行加 工，要使加工周期最短，约翰逊于1954年提出了一个有效 算法，那就是著名的Johnson算法。约翰逊算法包括以下 几个步骤：
• （1）列出每个作业在两台机器上的加工时间。 • （2）选择最短的加工时间，如果有两个相同的值，则任
一、最长流程时间Fmax的计算
• n/m/P/Fmax问题，n个零件要按相同的加工路线经 过m台机器加工，目标是使这批零件的最长流程时 间最短。
• 最长流程时间又称加工周期，它是从第一个零件 在第一台机器开始加工时算起，到最后一个零件 在最后一台机器上完成加工时为止所经过的时间。
• 例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当 按顺序S=（6，1，5，2，4，3）加工时，求Fmax。
顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。
EDD规则排序结果
机壳加 开始 加工 结束 流程 工次序 工作 时间 工作 时间
机壳1 0
8
8
8
机壳2 8 6 14 14
机壳4 14 3 17 17
机壳3 17 15 32 32
机壳5 32 12 44 44
所需标准加工时间 （包括机器调整）
8 6 15 3 12
预计顾客取货时间 （从现在开始算起的所需工作
时间）
10 12 20 18 22
SPT规则排序结果
机壳加 开始 加工 结束 流程 工次序 工作 时间 工作 时间
机壳4 0
3
3
3
机壳2 3
6
9
9
机壳1 9 8 17 17
机壳5 17 12 29 29
• 根据工件到达系统的情况
–静态排序 –动态排序
• 根据参数的性质
–确定型排序 –随机型排序
4参数法
• n/m/A/B • 其中，n为工件数 • m为机器数 • A车间类型。在A的位置若标以标以“P”，
则表示流水作业排列排序问题；若标以 “G”，则表示一般单件作业排序问题。当 m=1，则A处为空白。 • B为目标函数，通常是使其值最小 • 例如：n/3/P/Cmax
i
1
2
3
4
5
6
Pi1
4
2
3
1
4
2
Pi2
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
3
pi 113 4 21 3 25 2 32 3 38 4 46
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为最长延迟时间
三、排序问题的分类
• 根据机器数的多少
–单台机器的排序问题 –多台机器的排序问题
允许停留时间和工件余下加工时间之比。 • MWKR规则 优先选择余下加工时间最长的工件。 • LWKR规则 优先选择余下加工时间最短的工件。 • MOPNR规则 优先选择余下工序数最多的工件。 • RANDOM规则 随机地挑选下一个工件。
一般作业排序的目标
Ø满足顾客或下一道工序的交货期要求 Ø流程时间最短 Ø准备时间最短或成本最小化 Ø在制品库存最低 Ø机器设备或劳动力利用最大化
教学重点与难点 重点
最长流程时间的计算 约翰逊算法 相同零件的3种移动方式下机器加工周期的计算方法
难点
一般流水作业排序问题的启发式算法
生产任务的最终落实
• MRP确定各车间的零部件投入出产计划，将全 厂性的产品出产计划变成了各车间的生产任务。
• 各车间要将车间的生产任务变成各个班组、各 个工作地和各个工人的任务。
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）计算加工周期。