12
§1 车间作业计划模型
零 车床
磨床 零 车床
磨床
件 (第一工序) (第二工序) 件 (第一工序) (第二工序)
1
1.5
2
2.0
3
1.0
0.5
4
1.25
2.5
0.25 5 0.75
1.25
1.75
同样，下一个最短加工时间为1，这是车床加 工零件3的所需时间，故把零件3排在第二位上， 同时把零件3所在的行划去。如表中黑色线条 所示。
10
§1 车间作业计划模型
零 车床
磨床 零 车床
磨床
件 (第一工序) (第二工序) 件 (第一工序) (第二工序)
1
1.5
2
2.0
3
1.0
0.5
4
1.25
2.5
0.25 5 0.75
1.25
1.75
接着，我们又找到最短加工时间为0.5，这一时间与磨 床（第二工序）有关，我们把磨床加工时间为0.5的零 件1放到除第五外的加工顺序的末尾，即第四位加工， 同时把表中的零件1所在的行划去。如表中黄色线条 所示。
应该如何安排这五个零件的先后顺序才能使完 成这五个零件的总的加工时间为最少？
7
§1 车间作业计划模型
零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75
解：由于每个零件必须先进行车床加工，再进行磨床加工， 所以在车床上加工零件的顺序与在磨床上加工零件的顺序是 一样的。如果这些零件在车床上和磨床上加工顺序都为1，2， 3，4，5。我们用图12-1中的线条图来表示各零件加工的开始 时间与完成时间，这种图是由一根时间轴和车床、磨床在每 个时间段的状况的图形所构成。
6
§1 车间作业计划模型
二、两台机器、n个零件 例2. 某工厂根据合同定做一些零件，这些零件要
求先在车床上车削，然后再在磨床上加工，每台机 器上各零件加工时间如下表所示。
零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75
零件 加工时间（小时） 零件 加工时间（小时）
1
1.8
4
0.9
2
2.051.3来自30.56
1.5
应该按照什么样的加工顺序来加工这六个零件， 才能使得这六个零件在车间里停留的平均时间为最少？
4
§1 车间作业计划模型
例1解：如果我们用Pi表示安排在第i位加工的零 件所需的时间，用Tj表示安排在第j位加工的零件在车 间里总的停留时间，则有
8
车 1 2 3 45
床 1.5 2.0 1.0 1.25 0.75
磨 床
1
23
45
0.5 0.25 1.75 2.5 1.25
0
图 12-1
10
从上图中我们可以看出，加工时间的延长主要是
由于磨床的停工待料造成的，只要减少磨床的停工待料
的时间就能减少整个加工任务的总时间。
为了减少磨床的停工待料，我们应该一方面把在车
那么各个零件平均停留时间为
6 p1 5 p2 4 p3 3 p4 2 p5 p6 6
从上式可知，对于一台机器n个零件的排序问题，只要系数 越大，配上加工时间越少的，即按照加工时间排出加工顺序， 加工时间越少的零件排在越前面，加工时间越多的零件排在越 后面，可使各零件的平均停留时间最少。
11
§1 车间作业计划模型
零 车床
磨床 零 车床
磨床
件 (第一工序) (第二工序) 件 (第一工序) (第二工序)
1
1.5
2
2.0
3
1.0
0.5
4
1.25
2.5
0.25 5 0.75
1.25
1.75
下一个最短加工时间为0.75，这个加工时 间是车床（第一工序）加工零件5的所需时间， 故把零件5排在加工顺序的第一位上，同时把 表中的零件5所在的行划去。如表中蓝色线条 所示。
第一节 车间作业计划模型 第二节 统筹方法
2
§1 车间作业计划模型
车间作业计划是指一个工厂生产工序 的计划和安排。 ➢一、一台机器、n个零件的排序问题 ➢二、两台机器、n个零件的排序问题
3
§1 车间作业计划模型
一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨床，常常出现很
多零件同时要求这台磨床加工的情况，现有六个零件 同时要求加工，这六个零件加工所需时间如下表所示。
1
1.5
2
2.0
3
1.0
0.5
4
1.25
2.5
0.25 5 0.75
1.25
1.75
寻找例2的最优解：我们在上表中找到所列出的最 短加工时间是0.25,它是第二道工序磨床加工零件2的所 需时间，由于这个时间与磨床有关，故我们把零件2放 在加工顺序的末尾，即第五位，并在表中划去零件2 所 在行。如表中红色线条所示。
§1 车间作业计划模型
可知这六个零件的停留时间为：
T1 + T2 + T3 + T4 + T5 + T6 ＝ P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) +(P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) ＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6.
j
Tj = P1 + P2 +…+ Pj-1 + Pj = Pi i 1
不同的加工顺序得到不同的各零件的平均停留时 间，如何得到一个使得各零件的平均停留时间最少的 排序呢？这就是我们最后要解决的优化问题，而且我 们要设法找到一种简便的算法。
对于某种加工顺序，我们知道安排在第j位加工的
j
零件在车间里总的停留时间为Tj ， Tj = Pi i1 5
第九章
排序与统 筹方法
运筹学
1
第九章 排序与统筹方法
在本章中，我们将介绍车间作业计划模型和统筹方法。 这两个问题尽管处理的方法有所不同，但当我们面临必须完 成若干项不能同时进行的工作时，它们都将帮助我们应该按 照怎样的次序、怎样的时间表来做这些工作，使得效果最佳 （例如完成全部工作所用时间最短或费用最少等等）。
床上加工时间越短的零件越早加工，减少磨床等待的时
间；另一方面把在磨床上加工时间越短的零件越晚加工，
以便充分利用前面的时间，这样我们就得到了使完成全
部零件加工任务所需总时间最少的零件排序方法。
§1 车间作业计划模型
零 车床
磨床 零 车床
磨床
件 (第一工序) (第二工序) 件 (第一工序) (第二工序)