文档介绍：1
第十二章排序与统筹方法
§1 车间作业计划模型
§2 统筹方法
在本章中,我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同,但当我们面临必须完成若干项不能同时进行的工作时,它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作,使得效果最佳(例如完成全部工作所用时间最短或费用最少等等)。
2
§1 车间作业计划模型
车间作业计划是指一个工厂生产工序的计划和安排。
一、一台机器、n个零件的排序问题
二、两台机器、n个零件的排序问题
3
§1 车间作业计划模型
一、一台机器、n个零件的排序问题
,常常出现很多零件同时要求这台
磨床加工的情况,现有六个零件同时要求加工,这六个零件加工所需时间
如下表所示。
应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零
件在车间里停留的平均时间为最少?
零件
加工时间(小时)
零件
加工时间(小时)
1
2
3
4
5
6
4
§1 车间作业计划模型
例1解:如果我们用Pi表示安排在第i位加工的零件所需的时间,用Tj表示安排在第j位加工的零件在车间里总的停留时间,则有
Tj = P1 + P2 +…+ Pj-1 + Pj =
不同的加工顺序得到不同的各零件的平均停留时间,如何得到一个使得各零件的平均停留时间最少的排序呢?这就是我们最后要解决的优化问题,而且我们要设法找到一种简便的算法。
对于某种加工顺序,我们知道安排在第j位加工的零件在车间里总的停留时间为Tj , Tj =
可知这六个零件的停留时间为:
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.
那么各个零件平均停留时间为
从上式可知,对于一台机器n个零件的排序问题,只要系数越大,配上加工时间越少的,即按照加工时间排出加工顺序,加工时间越少的零件排在越前面,加工时间越多的零件排在越后面,可使各个零件的平均停留时间为最少。
5
§1 车间作业计划模型
二、两台机器、n个零件
,这些零件要求先在车床上车削,然后再在
磨床上加工,每台机器上各零件加工时间如表12-5所示。
表12-5
应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为
最少?
解:由于每个零件必须先进行车床加工,再进行磨床加工,所以在车床上加
工零件的顺序与在磨床上加工零件的顺序是一样的。
如果这些零件在车床上和磨床上加工顺序都为1,2,3,4,5。我们用图12-1
中的线条图来表示各零件加工的开始时间与完成时间,这种图是由一根时间轴和
车床、磨床在每个时间段的状况的图形所构成。
零件
车床
磨床
零件
车床
磨床
1
2
3
4
5
6
§1 车间作业计划模型
图 12-1
从上图中我们可以看出,加工时间的延长主要是由于磨床的停工待料
造成的,只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。
为了减少磨床的停工待料,我们应该一方面把在车床上加工时间越短的零
件越早加工,减少磨床等待的时间;另一方面把在磨床上加工时间越长的
零件越晚加工,以便充分利用前面的时间,这样我们就得到了使完成全部
零件加工任务所需总时间最少的零件排序方法。
1
2
3
4
5
1
车床
磨床
2
3
4
5
0
10
7
§1 车间作业计划模型
寻找例2的最优解:我们在表12-,它是第二道工序磨床
加工零件2的所需时间,由于这个时间与磨床有关,故我们把零件2放在加工顺序的末尾,即第五
位,并在表中划去零件2 所在行。如表12-6中红色线条所示。
接着,,这一时间与磨床(第二工序)有关,我们把磨床加
,即第四位加工,同时把表中的零件1所在
的行划去。如表12-6中黄色线条所示。
,这个加工时间是车床(第一工序)加工零件5的所需时间,故
把零件5排在加工顺序的第一位上,同时把表中的零件5所在的行划去。如表1