几个名词术语
• 排序——工件在机器上的加工顺序 • 派工——将生产任务安排到具体机床上加工—调度范围； • 赶工——实际进度落后于计划进度时采取的行动—调度范
围；
• 调度——发现实际进度落后于计划进度时而采取的调配资 源的行动。
• 机器——服务者 • 工件——服务对象 • 加工路线——工件加工的工艺过程 • 工序——加工路线上的每一个具体工作地（机器）。
第 十 章 作业排序与生产作业计划
第一节 作业排序的基本概念 第二节 流水作业排序问题 第三节 单件作业排序问题 第四节 多台设备作业排序
2020/10/28
1
第一节 作业排序的基本概念
引言
在确定了各车间的零部件投入、出产计 划、将全厂的生产计划变成了各车间的生产 任务后,各车间还应将零部件的投入、出产计 划变成车间的作业计划，即将车间的生产任 务变成各工段、班组、各工作地的生产任务。 编制车间生产作业计划，应该解决工件加工 顺序问题。这就是我们要讨论的作业排序问 题。采用排序理论与方法，可以得出工件加 工的最优或令人满意的顺序。
现只讨论几种有代表性的排序问题。
2020/10/28
12
第一节 作业排序的基本概念
三、排序问题的分类和表示法
排序问题常见的分类方法有按机器、工件、目标函数的特 征分类。
1. 按机器的种类和数量不同,可以分成 单台机器的排序问题 多台机器的排序问题
对于多台机器的排序问题,按工件加工路线的特征, 可以分成 单件作业排序问题 —— 加工路线不同
流水作业排序问题 —— 加工路线相同
2020/10/28
由于编制生产作业计划的主要问题是确定 各台机器上工件的加工顺序，并且一般都是 按最早可能开工时间或最早可能完工时间来 编制生产作业计划。所以，当工件的加工按 一定的时间确定了加工顺序后，作业计划也 就确定了。这就造成了人们通常不加区别的 使用“排序”与“编制作业计划”两个术语。
2020/10/28
4
在编制生产作业计划时常常出现一个工件在某道 工序加工完之后，加工它的下一道工序的机器还在 加工前一个工件，这时该工件不得不等待一段时间 才能开始在下一道工序的机器上加工。这种情况称 为“工件等待”。
当某台机器已加工完一个工件，而下一个工件尚
未到达。这种情况称为“机器空闲”。
2020/10/28
3
第一节 作业排序的基本概念
ri—— Ji 到达工序时间，即可以开始加工的最早时间；
j=1
di —— Ji 的完工期限；
ai—— Ji 在车间允许停留的时间（ Ji 进入车间到完工时刻之间的 时间间隔： ai = di －ri）；
Wij —— Ji 在第 j 道工序前的等待时间，
Ji 总的等待时间：
2020/10/28
m
Wi = ∑ Wij
当 Li > 0 时为正延迟, 即Ji 的实际完工时间超过了完 工期限;
当 Li < 0 时为负延迟, 即Ji 提前完工;
当 Li = 0 时为零延迟, 即Ji 按期完工。
Lmax —— 最长延迟时间, Lmax = max {Li} . 即在一批 工件中找出的最大延迟时间.
2020/10/28
9
第一节 作业排序的基本概念
2020/10/28
5
第一节 作业排序的基本概念
二、假设条件与符号说明
为了便于采用数学模型来分析研究排序问题，做下列假设：
1. 一个工件不能同时在几台不同的机器上被加工。 2. 采取平行移动方式移送被加工的工件。 3. 不允许中断。当一个工件一旦开始加工,必须一直进行到完
工,不得中途停止插入其它工件。 4. 工件在每道工序的加工只在一台机器上进行。 5. 工件数（或批量）、机器数已知，单件加工时间已知, 完
成加工的时间与加工顺序无关。 6. 每台机器同时只能加工一个工件。
2020/10/28
6
第一节 作业排序的基本概念
符号说明
• Ji —— 第 i 工件，i = 1,2,…,n ；
• Mj —— 第 j 台机器，j =1,2,…,m；
(i , j, k) —— Ji 的第j 道工序在Mk上进行；加工时间， Ji加工完的总加工时间；Pi = ∑ Pij
10
第一节 作业排序的基本概念
2. 按工件到达车间的情况不同,可以分成
静态的排序问题 —— 排序时所有工件都已到达,可以一次 对它们进行排序.
动态的排序问题 —— 排序时工件陆续到达,要随时安排它们 的加工顺序
3. 按目标函数的性质不同,也可划分不同的排序问题 使平均流程时间最短
单台机器的排序 使误期完工工件数最少 ……
Fmax —— 最长流程时间, Fmax = max{Fi}, 即一批工件中的最长流 程时间;
Li —— Ji 工件的延迟时间，
2020/10/28
Li = Ci －di = ri + Pi + Wi － di = (Pi + Wi ) － (di － ri ) = Fi －ai 8
第一节 作业排序的基本概念
j=1
7
第一节 作业排序的基本概念
Ci —— Ji 的完工时间
Ci = ri +∑( Pij + Wij ) = ri + Pi + Wi
• Cmax —— 最长完工时间,Cmax = max{Ci}, 即一批工件中的最长 完工时间;
• Fi —— Ji 的流程时间,即工件在车间的实际停留时间,
Fi = Ci －ri = Pi + Wi ;
多台机器的排序：不同目标排序问题
单目标排序问题：以往研究的对象
多目标排序问题：很少有人研究
2020/10/28
11
第一节 作业排序的基本概念
4. 另外，按参数的性质，可以划分为 确定型排序问题 —— 指加工时间和有关参数是已知 确定的量 随机型排序问题 ——加工时间和有关参数为随机变量
这两种排序问题的解法本质上不同。
2020/10/28
2
第一节 作业排序的基本概念
一、编制生产作业计划与排序的关系
编制生产作业计划与作业排序不同，排序只是确 定工件在机器上的加工顺序，可以用一组工件的代 号的排列来表示这组工件的加工顺序，而编制生产 作业计划不仅包括确定工件的加工顺序，而且包括 确定机器加工每个工件的开始时间和完成时间。所 以，只有生产作业计划才能指导工人的生产活动。