生产与运作管理
Production & Operations Management
华中科技大学管理学院
The School of Management，HUST
陈荣秋 马士华
Rongqiu Chen and Shihua Ma
华中科大管理学院陈荣秋马士华
第11章 制造业作业计划与控制Scheduling and Controlling for Manufacturing
作业计划问题的基本概念
流水作业排序问题
单件作业的排序问题
生产作业控制
华中科大管理学院陈荣秋马士华
编制作业计划要解决的问题
工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间
学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课
。。。
华中科大管理学院陈荣秋马士华
作业计划问题的基本概念
编制作业计划要解决的问题
编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。
由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。
华中科大管理学院陈荣秋马士华
作业计划问题的基本概念（续）
有关的名词术语
编制作业计划或日程安排(Scheduling)
排序(Sequencing)
派工(Dispatching)
控制(Controlling)
赶工(Expediting)
“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动
华中科大管理学院陈荣秋马士华
作业计划问题的基本概念（续）
“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”
“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件
“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束
“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题
华中科大管理学院陈荣秋马士华
常用的符号
华中科大管理学院陈荣秋马士华
排序问题的分类
华中科大管理学院陈荣秋马士华
排序问题的分类
Flow Shop
华中科大管理学院陈荣秋马士华
排序问题的分类
Job Shop
Job A
Job B
华中科大管理学院陈荣秋马士华
排序问题的表示方法
华中科大管理学院陈荣秋马士华
流水作业排序问题
流水车间(Flow shop):工件的加工路线都一致，典型的如流水线
最长流程时间的计算
两台机器排序问题的最优算法
多台机器排序问题的启发式算法
Work Center #1
Work Center #2
Output
华中科大管理学院陈荣秋马士华
最长流程时间的计算
（练习）
工件代号i
1 2 3 4 5 6
Pi1 4 6 4 5 8 3
Pi2 3 5 3 9 7 1
Pi3 7 9 2 6 5 8
Pi4 5 4 9 6 2 3
6/4/p/Fmax，加工顺序为1,4,6,3,5,2，求Fmax
华中科大管理学院陈荣秋马士华
最长流程时间的计算
工件代号i
1 4 6 3 5 2
Pi1 4 5 3 4 8 6
Pi2 3 9 1 3 7 5
Pi3 7 6 8 2 5 9
Pi4 5 6 3 9 2 4
4 9 12 16 24 30
7 18 19 22 31 36
14 24 32 34 39 48
19 30 35 44 46 52
华中科大管理学院陈荣秋马士华
两台机器排序问题的 最优算法
约翰森法则
如果Min(ai, bj) < Min (aj, bi),则工件i应该排在工件j之前。
约翰森算法
（1）从加工时间矩阵中找出最短加工时间；
（2）若最短加工时间出现在机器M1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2 上，则对应工件应该尽可能往后排。
华中科大管理学院陈荣秋马士华
两台机器排序问题的 最优算法（续）
然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。
（3）若所有工件都已排序，停止。否则，转步骤（1）。
华中科大管理学院陈荣秋马士华
将工件2排在第1位 2
将工件3排在第6位 2 3
将工件5排在第2位 2 5 3
将工件6排在第3位 2 5 6 3
将工件4排在第5位 2 5 6 4 3
将工件1排在第4位 2 5 6 1 4 3
最优加工顺序为S=(2,5,6,1,4,3), Fmax =28
I 1 2 3 4 5 6
Ai 5 1 8 5 3 4
Bi 7 2 2 4 7 4
两台机器排序问题的 最优算法（续）
华中科大管理学院陈荣秋马士华
两台机器排序问题的 最优算法（续） 举例
工件号 1 2 3 4 5 6
ai 5 1 8 5 3 4
bi 7 2 2 4 7 4
工件最优顺序：2 5 6 1 4 3
1 3 4 5 5 8
2 7 4 7 4 2
4 8 13 18 26
3 11 15 22 26 28
ai
bi
最优顺序下的加工周期为28
华中科大管理学院陈荣秋马士华
有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的加工时间
A
B
C
D
E
操作2所需时间（小时）
操作1所需时间（小时）
任务
（1）根据Johnson算法安排工作顺序
（2）用甘特图表示出任务的进行情况
华中科大管理学院陈荣秋马士华
多台机器排序问题的 启发式算法
关键工件法
1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；
2. 对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa ,若pi1>pim 则按pim不增的顺序排成一个序列Sb;
3. 顺序（Sa,C,Sb）即为所求顺序。
华中科大管理学院陈荣秋马士华
多台机器排序问题的 启发式算法（续） 举例
工件i 1 2 3 4
Pi1 2 1 6 3
Pi2 4 8 2 9
Pi3 5 4 8 2
11 13 16 14
C
Sa (2,1)
Sb(4)
所求顺序：
（2,1,3,4）
华中科大管理学院陈荣秋马士华
一般n/m/P/Fmax问题的启发式算法
Palmer法
CDS法
华中科大管理学院陈荣秋马士华
练习
书345-346页，第2、3、4题
华中科大管理学院陈荣秋马士华
相同零件不同移动方 式下加工周期的计算
当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同
三种典型的移动方式
顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工
平行移动方式：单个零件加工完成后，立即移动到下道工序加工
平行顺序移动方式：两者混合
华中科大管理学院陈荣秋马士华
顺序移动方式
加工周期
时间
工序
1
2
3
4
顺序移动方式
华中科大管理学院陈荣秋马士华
平行移动方式
工序
1
2
3
4
时间
加工周期
华中科大管理学院陈荣秋马士华
平行顺序移动方式
特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：
时间
工序
1
2
3
4
加工 周期
华中科大管理学院陈荣秋马士华
单件作业排序问题
任务分配问题
单件作业排序问题的描述
优先派工准则
求解一般n/m/G/Fmax问题的启发式方法
华中科大管理学院陈荣秋马士华
任务分配问题
在生产运作管理工作中，管理人员经常面临的一个问题是：如何根据有限的资源(人力、物力、财力等)，进行工作任务分配，以达到降低成本或提高经济效益的目的。如：
有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才能使总的上课费用最低？
又如：运输任务的分配问题。有n条航线的运输任务指派给n艘船去完成，不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线，并且一条航线只能由一条船去完成。如何分配任务，才能使总的费用最小？
。。。
这类问题是常见的任务分配问题，也叫指派问题，它的目标是如何进行合理的任务分配，使总的费用最小。
华中科大管理学院陈荣秋马士华
任务分配问题
任务分配问题可以用一般的整数规划求解方法进行求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏统一的求解方法。
本课程采用匈牙利法求解任务分配问题。
华中科大管理学院陈荣秋马士华
匈牙利法求解任务分配问题
可以证明，对于分配问题，在其费用矩阵Cij中，各行、各列均减去一个常数，Cij改变以后的最优解，仍为原问题的最优解。
利用这个性质，通过对Cij的行、列进行加减常数的计算，把一些矩阵元素变为0，在Cij为0的元素上进行分解，就可得到原问题的最优解。
该方法应用了匈牙利数学家Konig矩阵性质定理，因此这种方法被称为匈牙利法。
华中科大管理学院陈荣秋马士华
匈牙利法求解任务分配问题
第一步 将原分配问题的效率矩阵进行变换得使各行各列中都出现0元素,其方法如下:
⑴ 率矩阵的每行元素中减去该行的最小元素，
⑵ 从所得效率矩阵的每列中减去该列的最小元素。
第二步 进行试分配,求初始分配方案,做法如下:
⑴ 只有一个0元素的行(或列)开始,给这个元素加圈，记为◎然后划去该0元所在列(或行)的其他0元,记为⊙，
⑵ 有一个0元素的列(或行)中0元素加圈，记为◎，然后划去该0元所在行(或列)的其他0元,记为⊙ ，
进行①,②两步,直到所有0元素都被⊙或◎为止，
◎元素的数目m等于矩阵的阶数n,那么这个分配问题的最优解已得到,此时只要令◎处的变量Xij=1,其余Xij为0,即为所求的最优解,否则,若m<n,则转入第三步。
华中科大管理学院陈荣秋马士华
匈牙利法求解任务分配问题
第三步 寻找覆盖所有0元素的最少直线,以确定该矩阵中能找到的最多的独立0元素的个数.为此，我们按以下步骤进行:
⑴ 对没有◎的行打√号，
⑵ 对已经有√号的行中所有含⊙的列打√号，
⑶ 再对打有√号的列中含有◎元素的行打√号，
⑷ 重复⑵, ⑶,直到得不出新的打√号的行,列为止，
⑸ 对没有打√号的行画横线,有打√的列画纵线,就得到覆盖所有0元素的最少直线数。
令这些直线数为L,若L<n,说明必须再变换当前的矩阵,才能找到n个独立0元素.则转第四步;
华中科大管理学院陈荣秋马士华
第四步 调整 ,使之增加一些0元素,具体做法如下:
⑴ 在没有被直线段覆盖的元素中,找出最小元素
⑵ 在没有被直线段覆盖的元素中,减去最小元素
⑶ 横线和纵线交叉处的元素加上这个最小元素
⑷ 被一条直线覆盖(横线或纵线)的元素不变。
得新的缩减矩阵 ,再转第二步.
华中科大管理学院陈荣秋马士华
练习
求如下系数矩阵所对应的任务分配问题
华中科大管理学院陈荣秋马士华
答案
最优任务分配方案为：x13=x22=x34=x41=1，
最优值为48。
华中科大管理学院陈荣秋马士华
单件作业排序问题的描述
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
加工描述矩阵D和加工时间矩阵T对应
华中科大管理学院陈荣秋马士华
优先派工准则
按什么样的法则来选择可安排的工序，对作业计划的优劣有很大影响。
迄今，人们已提出了100多个优先派工法则，下面列出4个进行比较：
① FCFS(First Come First Served)法则 优先选择最早进入可排工序集合的工件。
② SPT(Shortest Processing Time)法则 优先选择加工时间最短的工序。
③ EDD(Earliest Due Date)法则 优先选择完工期限紧的工件。
④ LPT(Longest Processing Time )法则 优先选择加工时间最长的工件。
华中科大管理学院陈荣秋马士华
优先派工准则（续）
例：有6项任务A，B，C，D，E ，F要完成。每项任务所需时间和完工期限如下表所示。分别按
（1）FCFS，（2）SPT，（3）EDD和（4）LPT法则，来确定完成任务的先后次序及相应的指标。
7
16
4
17
15
18
2
8
4
10
5
12
A
B
C
D
E
F
完工期限（天）
所需时间（天）
任务
华中科大管理学院陈荣秋马士华
优先派工准则（续）
如果任务下达的顺序是A-B-C-D-E-F，按FCFS法则，任务的流程时间就是每件任务的等待时间加上加工时间。
54
120
41
累计
0
0
10
7
14
23
7
16
4
17
15
18
2
10
14
24
29
41
2
8
4
10
5
12
A
B
C
D
E
F
延迟时间
完工期限
流程时间
加工时间
任务次序
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按照FCFS法则，可以得到下列结果：
① 平均流程时间=累计流程时间/任务数=120/6=20天
② 利用率=累计加工时间/累计流程时间=41/120=%
③ 系统中平均在制品数量=累计流程时间/累计加工时间=120/41=件任务
④ 平均延迟时间=延迟时间总和/任务数 =54/6=9天
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按SPT法则，处理任务的的流程时间就是每件任务的等待时间加上加工时间。
40
108
41
累计
0
2
0
3
12
23
7
4
15
16
17
18
2
6
11
19
29
41
2
4
5
8
10
12
A
C
E
B
D
F
延迟时间
完工期限
流程时间
加工时间
任务次序
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按照SPT法则，得到下列结果：
① 平均流程时间=108/6=18天
② 利用率=41/108=38%
③ 系统中平均在制品数量=108/41=件任务
④ 平均延迟时间=40/6=天
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按EDD法则，处理任务的先后次序是C-A-E-B-D-F，如下表所示。
38
110
41
累计
0
0
0
3
12
23
4
7
15
16
17
18
4
6
11
19
29
41
4
2
5
8
10
12
C
A
E
B
D
F
延迟时间
完工期限
流程时间
加工时间
任务次序
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按照EDD法则，得到下列结果：
① 平均流程时间=110/6=天
② 利用率=41/110=%
③ 系统中平均在制品数量=110/41=件任务
④ 任务平均延迟时间=38/6=天
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按LPT法则，处理任务的先后次序是F-D-B-E-C-A，如下表所示。
108
179
41
累计
0
5
14
20
35
34
18
17
16
15
4
7
12
22
30
35
39
41
12
10
8
5
4
2
F
D
B
E
C
A
延迟时间
完工期限
流程时间
加工时间
任务次序
华中科大管理学院陈荣秋马士华
优先派工准则（续）
按照LPT法则，得到下列结果：
① 平均流程时间=179/6=天
② 利用率=41/179=%
③ 系统中平均在制品数量=179/41=件任务
④ 任务平均延迟时间=108/6=18天
华中科大管理学院陈荣秋马士华
优先派工准则（续）
9
18
38
20
18
FCFS
SPT
EDD
LPT
平均延迟时间（天）
平均在制品数
利用率（%）
平均流程时间（天）
方法
（1）按照LPT法则进行作业排序，各项指标最差。
（2）按SPT法则可使工件的平均流程时间最短，使平均在制品数量最少。
（3）FCFS法则对工件较公平，这一点在对顾客服务中尤其重要，但在多数情况下都不具有优势。
（4）EDD法则可使工件的平均延迟时间最小，其它指标也不错。
华中科大管理学院陈荣秋马士华
求解一般n/m/G/Fmax问题的启发式方法
（1）两种作业计划的构成
能动作业计划
无延迟作业计划
（2）三类启发式算法
运用优先派工法则
随即抽样法
概率调度法
华中科大管理学院陈荣秋马士华
（1）两种作业计划的构成
符号说明
每安排一道工序称为一“步”
{St}:t步之前已排序工序构成的部分作业计划；
{Ot}:t步可排序工序的集合；
Tk为{Ot}中工序Ok的最早可能开始时间；
T’k为{Ot}中工序Ok的最早可能完成时间。
华中科大管理学院陈荣秋马士华
（1） 两种作业计划的构成（续）
能动作业计划的构成
（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。
（2）求T* = min{T’k},并求出T*所出现的机器M*。如果M*有多台，则任选一台。
（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj< T* 。
（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot} ，使t=t+1.
（5）若还有未安排的工序，转步骤（2）；否则，停止。
华中科大管理学院陈荣秋马士华
能动作业计划的构成
2,3,2
M2
13
13
8
2,3,2
6
1,3,2
M2
8
8
12
7
7
1,3,2
2,3,2
5
2,2,1
M1
7
8
7
7
3
1,3,2
2,2,1
4
1,2,3
M3
M1
7
7
7
3
3
1,2,3
2,2,1
3
2,1,3
M3
3
6
3
2
0
1,2,3
2,1,3
2
1,1,1
M1
2
2
3
0
0
1,1,1
2,1,3
1
Oj
M*
T*
T`k
Tk
{Ot}
t
华中科大管理学院陈荣秋马士华
能动作业计划的甘特图
2,3,2
1,1,1 2,2,1
1,3,2
2,1,3 1,2,3
3 7
7 8 13
2 3 7
0
时间
机器
M1
M2
M3
华中科大管理学院陈荣秋马士华
两种作业计划的构成（续）
无延迟作业计划的构成
（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。
（2）求T* = min{Tk},并求出T*所出现的机器M*。如果M*有多台，则任选一台。
（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T* 。
（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot} ，使t=t+1.
（5）若还有未安排的工序，转步骤（2）；否则，停止。
华中科大管理学院陈荣秋马士华
无延迟作业计划的构成
1,3,2
M2
12
13
12
1,3,2
6
2,3,2
M2
M2
7
7
8
12
7
7
1,3,2
2,3,2
5
2,2,1
M1
3
8
7
7
3
1,3,2
2,2,1
4
1,2,3
M3
M1
3
3
7
7
3
3
1,2,3
2,2,1
3
2,1,3
M3
0
6
3
2
0
1,2,3
2,1,3
2
1,1,1
M1
M3
0
0
2
3
0
0
1,1,1
2,1,3
1
Oj
M*
T*
T`k
Tk
{Ot}
t
华中科大管理学院陈荣秋马士华
无延迟作业计划的甘特图
2,3,2
1,1,1 2,2,1
2,1,3 1,2,3
3 7
7 12 13
2 3 7
0
时间
机器
M1
M2
M3
1,3,2
华中科大管理学院陈荣秋马士华
练习
有一个2/3/G/Fmax的问题，其加工描述矩阵D和加工时间矩阵T分别如下所示，请构成一个能动作业计划和无延迟作业计划。
D=
1,1,1 1,2,3 1,3,2
2,1,3 2,2,2 2,3,1
T=
3 5 2
2 4 3
华中科大管理学院陈荣秋马士华
（2）三类启发式算法
优先调度法则
构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划
计算量小
已经提出100多种优先调度法则
华中科大管理学院陈荣秋马士华
优先调度法则
FCFS（first come, first served）选择最早进入可排序集合的工序
SPT( shortest processing time）选择加工时间最短的工序
EDD（earliest due date）选择完工期限最紧的工序
SCR(smallest critical ratio)选择临界比最小的工件
MWKR(most work remaining)选择余下加工时间最长的工件
LWKR(least work remaining)选择余下加工时间最短的工件
MOPNR(most operations remaining)选择余下工序数最多的工件
RANDOM 随机挑选一个工件
Rush
Top Priority
华中科大管理学院陈荣秋马士华
（2）三类启发式算法（续）
随机抽样法
从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。
概率调度法
将优先调度法则与随机抽样法结合
对不同工件将优先调度法则分配不同的挑选概率，效果较好
华中科大管理学院陈荣秋马士华
实行生产作业控制的原因
生产计划和生产作业计划在实施过程中由于以下原因，往往造成实施情况与计划要求偏离
加工时间估计不准确。
随机因素的影响。
加工路线的多样性。
企业环境的动态性。
。。。
华中科大管理学院陈荣秋马士华
实行生产作业控制的条件
要有一个标准。标准就是生产计划和生产作业计划。
要取得实际生产进度与计划偏离的信息。
要能采取纠正偏差的行动。
华中科大管理学院陈荣秋马士华
不同生产类型生产控制的特点
单件小批生产
对于单件小批生产，排队时间是主要的，它大约占工件加工提前期的80-95% 。排队时间越长，在制品库存就越高。如果能够控制排队时间，也就控制了工件在车间的停留时间。要控制排队时间，实际是控制排队队长的问题。因此，如何控制排队的队长，是生产控制要解决的主要问题。
华中科大管理学院陈荣秋马士华
不同生产类型生产控制的特点
大量大批生产
大量大批生产的产品是标准化的，通常采用流水线或自动线的组织方式生产。因此，控制问题比较简单。主要通过改变工作班次，调整工作时间和工人数来控制产量。
华中科大管理学院陈荣秋马士华
生产作业控制（续） 生产作业控制的主要工具
实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：
调度单
日报、月报
例外报告、异常报告
输入/输出（Input/output control，I/O）报告
华中科大管理学院陈荣秋马士华
生产作业控制（续） 漏斗模型
模型介绍
德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。
漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。
华中科大管理学院陈荣秋马士华
利用“漏斗模型”进行生产控制
华中科大管理学院陈荣秋马士华
注：曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。如果运输时间不变，输入曲线与上道工序的输出曲线相对应。
华中科大管理学院陈荣秋马士华
生产作业控制（续） 控制规则
在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间
实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：
若希望保持在制品库存量，就要使单位时间内的平均输入等于平均输出。
若希望改变在制品库存量，可暂时增加或减少输入。
若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。
要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。
华中科大管理学院陈荣秋马士华
