13
第2节流水作业排序问题
• 流水作业排序问题的特征是每个工件的加工路线 都是一样的，常见的目标函数有时间表长和加权 总完工时间。
• 我们说加工路线一致，是指工件的流向一致，并 不要求每个工件必须经过加工路线上每台机器加 工。
• 如果某些工件不经某些机器加工，则设相应的加 工时间为零。对于流水作业排序问题，工件在不 同机器上的加工顺序不尽一致。 若所有工件在各台机器上的加工顺序都相同， 这就是排列排序问题（permutation schedule）。
0+1=1 0
1+2=3 0
3+3=6 6-5=1
6+4=10 10-8=2
10+5=15 15-6=9
35
12
35÷5=7 12÷5=2.4 12
排序准则 任务排序
E
A
D
交 则
货期最
早规
C
B
合计
平均
D
A
最短松弛 规则
时间
E B
C
合计
平均
续前表
加工时间 交货期
1
4
3
5
5
6
2
7
485ຫໍສະໝຸດ 6351
4
4
8
2
14
一、时间表长的计算
对于给定n个工件、m台机器的排列排序问题
Fm|prmu|Cmax,设工件顺序为J1,J2,…,Jn,其中Jj为排 第i位加工的工件的代号,以Cij表示工件Jj在机器Mi 上的完工时间,pij表示工件Jj在Mi上的加工时间 (i=1,2,…,m;j=1,2,…,n),那么:
5
排序的目标可以概括为以下几点： 1.满足交货期的要求 2.实现提前期最小化 3.实现设备的准备时间和准备成本最小化 4.充分利用设备和劳动力
6
二、排序问题的分类和表示方法
1.按工件到达车间的情况，可以分成静态 排序和动态排序
2.按机器的种类和数量不同，可以分为单 台机器排序和多台机器排序
3.按目标函数的性质不同，也可划分不同 的排序问题
• 最优准则：就是以什么为目标函数。
8
三、作业排序的优先规则
（1）先到先服务规则（first come first served, FCFS）：按订单送到的先后顺序进行加工，优先 选择最早进入排序集合的工件。
（2）最短加工时间规则（shortest processing time,SPT）：优先选择加工时间最短的工件。
排序准则 任务排序
A
B
先到先 则
服务规
C D
E
合计
平均
E
C
最短加工时间 A
规则
B
D
合计
平均
加工时间 交货期
3
5
4
8
2
7
5
6
1
4
1
4
2
7
3
5
4
8
5
6
通过时间 延误时间
0+3=3
0
3+4=7
0
7+2=9
9-7=2
9+5=14 14-6=8
14+1=15 15-4=11
48
21
48÷5=9.6 21÷5=4.2
4
第1节作业排序问题的基本概念
一、作业排序的基本概念 • 作业排序是指合理安排生产运作的各项活动作业、
生产运作资源使用、生产运作设施配置的时间表 等。 • 作业排序在生产车间就是具体地确定每台设备、 每个人员每天的工作任务和工件在每台设备上的 加工顺序。 • 作业排序要解决先加工哪个工件后加工哪个工件 的加工顺序问题，还要解决同一设备上不同工件 的加工顺序问题。
3
引例
• 某铅酸蓄电池生产厂主打产品是应用于叉车、牵引车的大 型铅酸蓄电池。铅酸蓄电池主要由电池槽、电池盖、正负 极板、稀硫酸电解液、隔板及附件构成。
• 由于公司是德国全资子公司，所有设备都是从德国采购回 来的，各个车间设备的生产能力和效率不同，再加上还有 很多附属件需要加工，如电池盒铁箱需要喷漆，组装完成 后需要注酸和充电，然后入库待运，所以公司出现了设备 忙闲不均的现象，生产效率低下，并且经常出现由于某一 工序导致全线停产的事故。问题究竟出在哪里？ 如何具体地组织生产活动，安排作业顺序，对生产活 动进行调整与控制，是保证生产任务按期完成的基础，也 是作业排序与控制需要研究和解决的问题。
运营管理
Operations Management
第11章制造业作业计划与控制
学习目标
1．理解制造业作业计划的基本概念； 2．掌握流水作业排序问题的求解算法； 3．掌握单件作业排序问题的求解算法； 4．了解生产作业控制的主要内容和工具。
2
学习内容
第1节 作业排序问题的基本概念 第2节 流水作业排序问题 第3节 单件作业排序问题 第4节 生产作业控制
7
通过时间 延误时间
0+1=1
0
1+3=4
0
4+5=9
9-6=3
9+2=11 11-7=4
11+4=15 15-8=7
40
14
40÷5=8 14÷5=2.8
0+5=5 0
5+3=8
8-5=3
8+1=9
9-4=5
9+4=13 13-8=5
13+2=15 15-7=8
50
21
50÷5=10 21÷5=4.2
（3）交货期优先规则（earliest duedate,EDD）： 优先选择交货期最早的工件。
（4）最大工作量规则（most work remaining,MWKR）：优先选择余下加工时间最 长的工件。
9
（5）最小工作量规则（least work remaining,LWKR）：优先选择余下加工时间最 短的工件。
4.按参数的性质，可以划分为确定型排序 问题和随机型排序问题
7
本章排序问题的描述：三参数表示法
三个参数为:α,β,γ,分别代表特定的机器环境、工 件特征和最优准则,它们是排序问题的三个组成部 分。
• 机器环境：描述机器的数量、类型、不同机器之 间的关系以及环境
• 工件特征：描述一般可用工件的性质,加工要求和 限制,资源的种类,数量和对加工的影响等来描述。
10
例：某工作中心需完成五项任务,它们的到达次序 依次为A、B、C、D、E,加工时间、交货期和计 算出的松弛时间如下表所示。要求:按照不同的准 则进行排序,并作效果比较。
工作中心任务数据表
任务 （按到达次序）
加工时间
交货期 （从现在算起）
松弛时间
A
3
5
2
B
4
8
4
C
2
7
5
D
5
6
1
E
1
4
3
11
解:按照不同准则进行排序的结果及其有关评价指标的计算如下表所示。
（6）随机排序规则（random,RAN）：由主管或操 作工随意选择一件他们喜欢的进行加工。
（7）后到先服务规则（last come first served,LCFS）：因为后来的工单放在先来的上面， 操作人员通常先加工上面的工单。
（8）临界比规则（smallest critical ratio,SCR）： 工件允许停留时间与工件剩余加工时间之比最小。