华中科技大学管理学院
生产作业排序
一、基本概念
二、最长流程时间
三、n/2/F/Fmax问题的算法
四、一般n/m/P/ Fmax问题的启发式算法
五、单件车间排序问题
华中科技大学管理学院
一、基本概念
1、排序
• 排序就是要将不同的工作任务安排一个执行
的顺序，使预定的目标最优化。
• 实际上就是要解决如何按时间的先后，将有
限的人力、物力资源分配给不同工作任务，
使预定目标最优化的问题。
华中科技大学管理学院
一、基本概念
排序中常用的几个概念
• 工件（Job）：服务对象；
• 机器（Machine、Processor）：服务者。
如：
• n个零件在机器上加工，则零件是工件，设备
是机器；
• 工人维修设备，出故障的设备是工件，工人
是机器。
华中科技大学管理学院
一、基本概念
所以，作业排序也就是要确定工件在机器上
的加工顺序，可用一组工件代号的一种排列
来表示。
如可用（1，6，5，4，3，2）表示加工顺序：
J1—J6—J5—J4—J3—J2。
华中科技大学管理学院
一、基本概念
2、作业计划（Scheduling）
• 作业计划与排序不是一回事，它不仅要确定
工件的加工顺序，而且还要确定每台机器加
工每个工件的开工时间和完工时间。
• 如果按最早可能开（完）工时间来编排作业
计划，则排序完后，作业计划也就确定了。
华中科技大学管理学院
一、基本概念
3、排序问题的分类与表示
1）单台机器与多台机器的排序问题。
2）流水车间与单件车间排序问题。
华中科技大学管理学院
一、基本概念
流水车间排序问题的基本特征：
• 每个工件的加工路线都一样。如车—铣—磨。
这里指的是工件的加工流向一致，并不要求
每个工件必须在每台机器上加工。如有的工
件为车—磨，有的为铣—磨。
• 不仅加工路线一致，而且所有工件在各台机
器上的加工顺序也一样，这种排序称为排列
排序（同顺序排序）。如工件排序为：J1—J3
—J2，则表示所有机器都是先加工J1，然后加
工J3，最后加工J2。
华中科技大学管理学院
一、基本概念
单件车间排序问题的基本特征：
• 每个工件都有其独特的加工路线，工件没有
一定的流向。
华中科技大学管理学院
一、基本概念
3）表示方法
一般正规的表示方法为：n/m/A/B
n：工件数；m：机器数；
A：车间类型（F、P、G）；B：目标函数
华中科技大学管理学院
一、基本概念
4）一般来说，排列排序问题的最优解不一定
是相应流水车间排序问题的最优解，但一般
是比较好的解。而对于仅有2台或3台机器的
情况，则排列排序问题的最优解一定是相应
流水车间排序问题的最优解。
华中科技大学管理学院
一、基本概念
4、排序问题的假设条件
• 一个工件不能同时在几台不同的机器上加工。
• 工件在加工过程中采取平行移动方式。
• 不允许中断。
• 每道工序只在一台机器上完成。
• 每台机器同时只能加工一个工件。
• 工件数、机器数和加工时间已知，加工时间与加工
顺序无关。
华中科技大学管理学院
二、最长流程时间
• 最长流程时间（加工周期）：从第一个工件
在第一台机器上加工起到最后一个工件在最
后一台机器上加工完毕为止所经过的时间。
• 假定所有工件的到达时间都为0，则Fmax等
于排在末位加工的工件在车间的停留时间。
华中科技大学管理学院
二、最长流程时间
计算Fmax的几个假定条件：
• 机器M1不会发生空闲；
• 对其它机器，能对某一工件加工必须具备2个
条件：机器必须完成排前一位的工件的加工；
要加工的工件的上道工序已经完工。
华中科技大学管理学院
二、最长流程时间
华中科技大学管理学院
二、最长流程时间
i
pi1
pi2
pi3
pi4
6 1 5 2 4 3
2
5
5
1
4
4
5
4
4
4
5
3
2
5
8
2
1
7
5
3
3
6
7
4
2 6 10 12 13 16
7 11 15 20 27 33
12 17 22 30 35 42
13 21 25 32 38 46
华中科技大学管理学院
三、n/2/F/Fmax问题的算法
Johnson算法：
• 假定：ai为工件Ji在机器M1上的加工时间，
bi为工件Ji在机器M2上的加工时间，每个
工件按M1—M2的路线加工。
华中科技大学管理学院
三、n/2/F/Fmax问题的算法
Johnson算法的步骤：
• 从加工时间矩阵中找出最短的加工时间。
• 若最短时间出现在M1上，则对应的工件尽可能
往前排。
• 若最短时间出现在M2上，则对应的工件尽可能
往后排。
• 若最短时间有多个，则任选一个。
• 划去已排序的工件。
• 若所有工件都已排序，则停止，否则重复上述
步骤。
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
对于一般的n/m/P/Fmax问题，可以用分支
定界法求得最优解，但计算量很大。实际
中，可以用启发式算法求近优解。
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
1、Palmer法
• 计算工件斜度指标i ：
m : 机器数
pik ：工件i在机器k上的加工时间。
i=1,2,,n
• 排序方法: 按i从大到小的顺序排列。
• 按排序的顺序计算Fmax
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
2、关键工件法：
• 计算Pi= Pij ，找出Pi最长的工件，将之作为
关键工件C。
• 对其余工件，若Pi1≤Pim ，则按Pi1由小到大排
成序列SA。若Pi1> Pim ，则按Pim由大到小排成
序列SB。
• 顺序（SA，C，SB）即为近优解。
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
得到的加工顺序为 (1，2，3，4)
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
3、CDS法：
• CDS法是Johnson算法的扩展方法，从M-1个排序中
找出近优解。
华中科技大学管理学院
四、一般n/m/P/ Fmax问题的
启发式算法
• L＝1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax＝28
• L＝2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax＝29
• 取顺序(1，2，3，4）为最优顺序。
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
1、问题描述
• (i，j，k)：表示工件i的第j道工序是在机器k上进行。
• 加工描述矩阵D：每一行描述一个工件的加工，每一
列的工序序号相同。
D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
• 加工时间矩阵T：与D相对应。
D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
T=
4 6 3
5 7 4
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
• 加工顺序矩阵S：每一行与机器相对应，每一列与工
件相对应。
D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
S=
1,1,1 2,2,1
1,3,2 2,3,2
2,1,3 1,2,3
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
• 用方块图表示：
D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
S=
1,1,1 2,2,1
1,3,2 2,3,2
2,1,3 1,2,3
T=
4 6 3
5 7 4
1,1,1
2,1,3 1,2,3
2,2,1
1,3,2 2,3,2
M1
M2
M3
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
2、能动作业计划的构成
• 各工序都按最早可能开(完)工时间安排且任何一台机
器的每段空闲时间都不足以加工一道可加工工序。
• 符号说明：
– {Ot} 第t步可以排序的工序的集合
– {St} t步之前已排序的工序构成的部分作业计划
– Tk {Ot}中工序Ok的最早可能开工时间
– T’k {Ot}中工序Ok的最早可能完工时间
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
能动作业计划的构成步骤：
①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合。
②求最小的最早完工时间 T*= min{T’k },并找到出现T
*
的机器M*，若有多台，任选一台。
③从{Ot}中跳出满足以下两条件的工序Oj
–需要机器M*加工；
–Tj < T
*
④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后
工序放入{Ot}中，使t=t+1。
⑤若还有未安排的工序，转步骤②；否则，停止。
华中科技大学管理学院
一个实例： D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
T=
2 4 1
3 4 5
i
1
{Ot} Tk T’k T* M* Oj
1,1,1 0 2 2 M1 1,1,1
2,1,3 0 3
2 1,2,3 2
6
3 M3 2,1,32,1,3 0 3
3 1,2,3 3 7 7 M3 1,2,3
2,2,1 3 7
4 1,3,2 7
8
7 M1 2,2,12,2,1 3 7
5 1,3,2 7
8 8 M2 1,3,2
2,3,2 7 12
6 13 M2 2,3,22,3,2 8 13
华中科技大学管理学院
得到加工顺序矩阵： S=
1,1,1 2,2,1
1,3,2 2,3,2
2,1,3 1,2,3
1,1,1
2,1,3 1,2,3
2,2,1
1,3,2 2,3,2
M1
M2
M3
2
3 7
7
3
8 13
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
3、无延迟作业计划的构成
• 没有任何延迟出现的能动作业计划。所谓“延迟”，
指有工件等待加工时，机器出现空闲，即使这段空闲
时间不足以完成一道工序。
• 构成步骤：
华中科技大学管理学院
五、单件车间排序问题（n/m/G/Fmax）
无延迟作业计划的构成步骤：
①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合。
②求最小的最早完工时间 T*= min{Tk },并找到出现T
*
的机器M*，若有多台，任选一台。
③从{Ot}中跳出满足以下两条件的工序Oj
–需要机器M*加工；
–Tj = T
*
④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后
工序放入{Ot}中，使t=t+1。
⑤若还有未安排的工序，转步骤②；否则，停止。
华中科技大学管理学院
一个实例： D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,1 2,3,2
T=
2 4 1
3 4 5
i
1
{Ot} Tk T’k T* M* Oj
1,1,1 0 2 0 M1 1,1,1
2,1,3 0 3
2 1,2,3 2
6
0 M3 2,1,32,1,3 0 3
3 1,2,3 3 7 3 M3 1,2,3
2,2,1 3 7
4 1,3,2 7
8
3 M1 2,2,12,2,1 3 7
5 1,3,2 7
8 7 M2
2,3,22,3,2 7 12
6 12 M2 1,3,22,3,2 12 13
0 M3
3 M1
7 M2
华中科技大学管理学院
得到加工顺序矩阵： S=
1,1,1 2,2,1
2,3,2 1,3,2
2,1,3 1,2,3
1,1,1
2,1,3 1,2,3
2,2,1
1,3,22,3,2
M1
M2
M3
2
3 7
7
3
12 13
华中科技大学管理学院
4、启发式算法：
• 能动作业计划和无延迟作业计划尽管不一定是最优作
业计划，但一般是较好的作业计划，特别是无延迟作
业计划能提供令人满意的解。
• 一般能动作业计划和无延迟作业计划都有多个，可用
启发式方法从中选择结果较好的作业计划。
• 一般来说，以构成无延迟作业计划的步骤为基础的启
发式算法比以构成能动作业计划的步骤为基础的启发
算法的效果要好。
五、单件车间排序问题（n/m/G/Fmax）
华中科技大学管理学院
优选调度法则：
• SPT(Shortest Processing Time)法则：优先选择加工时间最短的
工序。
• FCFS(First Come First Served)法则：优先选择最早进入可排工
序集合的工件。
• EDD(Earliest Due Date)法则：优先选择完工期限紧的工件。
• MWKR(Most Work Remaining)法则：优先选择余下加工时间最
长的工件。
• LWKR(Least Work Remaining)法则：优先选择余下加工时间最
短的工件。
• MOPNR(Most Operations Remaining)法则：优先选择余下工序
数最多的工件。
五、单件车间排序问题（n/m/G/Fmax）
华中科技大学管理学院
优选调度法则：
• 按SPT法则可使工件的平均流程时间最短，从而减少
在制品量。
• FCFS法则来自排队论，它对工件较公平。
• EDD法则可使工件最大延误时间最小。
• SCR也是保证工件延误最少的法则。
• MWKR法则使不同工作量的工件的完工时间尽量接
近。LWKR法则，使工作量小的工件尽快完成。
• MOPNR法则与MWKR法则类似，只不过考虑工件在
不同机器上的转运排队时间是主要的。
五、单件车间排序问题（n/m/G/Fmax）
