韩伯棠管理运筹学(第三版)_第十二章_排序与统筹

运筹学计划统筹 绩效最优第十二章 排序与统筹方法

第九章

排序与统筹方法

在本章中， 在本章中 ， 我们将介绍车间作业计划模型和统 筹方法。 这两个问题尽管处理的方法有所不同， 筹方法 。 这两个问题尽管处理的方法有所不同 ， 但 当我们面临必须完成若干项不能同时进行的工作时， 当我们面临必须完成若干项不能同时进行的工作时 ， 它们都将帮助我们应该按照怎样的次序、 它们都将帮助我们应该按照怎样的次序 、 怎样的时 间表来做这些工作， 使得效果最佳( 间表来做这些工作 ， 使得效果最佳 ( 例如完成全部 工作所用时间最短或费用最少等等) 工作所用时间最短或费用最少等等)。

第一节 车间作业计划模型 第二节 统筹方法2

§1 车间作业计划模型

车间作业计划是指一个工厂生产工序 的计划和安排。 的计划和安排。 一、一台机器、n个零件的排序问题 一台机器、 个零件的排序问题 二、两台机器、n个零件的排序问题 两台机器、 个零件的排序问题

§1 车间作业计划模型一、一台机器、n个零件的排序问题 一台机器、 某车间只有一台高精度的磨床， 例 1.某车间只有一台高精度的磨床， 常常出现很 某车间只有一台高精度的磨床 多零件同时要求这台磨床加工的情况，现有六个零件 多零件同时要求这台磨床加工的情况， 同时要求加工，这六个零件加工所需时间如下表所示。 同时要求加工，这六个零件加工所需时间如下表所示。 加工时间(小时) 加工时间(小时) 零件 加工时间(小时) 零件 加工时间(小时) 1 1.8 4 0.9 2 2.0 5 1.3 3 应该按照什么样的加工顺序来加工这六个零件， 0.5 6 1.5 应该按照什么样的加工顺序来加工这六个零件， 才能使得这六个零件在车间里停留的平均时间为最少？ 才能使得这六个零件在车间里停留的平均时间为最少？

§1 车间作业计划模型例1解：如果我们用 i表示安排在第 位加工的零 解 如果我们用P 表示安排在第i位加工的零 件所需的时间， 表示安排在第j位加工的零件在车 件所需的时间，用Tj表示安排在第 位加工的零件在车 间里总的停留时间， 间里总的停留时间，则有j

Tj = P1 + P2 +…+ Pj-1 + Pj = ∑ P ii=1

不同的加工顺序得到不同的各零件的平均停留时 间，如何得到一个使得各零件的平均停留时间最少的 排序呢？这就是我们最后要解决的优化问题， 排序呢？这就是我们最后要解决的优化问题，而且我 们要设法找到一种简便的算法。 们要设法找到一种简便的算法。 对于某种加工顺序，我们知道安排在第j位加工的 对于某种加工顺序，我们知道安排在第 位加工的j

零件

在车间里总的停留时间为T 零件在车间里总的停留时间为 j , Tj =

∑Pi =1

i5

§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. 那么各个零件平均停留时间为

6 p1 + 5 p 2 + 4 p 3 + 3 p 4 + 2 p 5 + p 6 6从上式可知，对于一台机器n个零件的排序问题 个零件的排序问题， 从上式可知 ， 对于一台机器 个零件的排序问题 ， 只 要系数越大，配上加工时间越少的， 要系数越大，配上加工时间越少的，即按照加工时间排出 加工顺序，加工时间越少的零件排在越前面， 加工顺序，加工时间越少的零件排在越前面，加工时间越 多的零件排在越后面，可使各零件的平均停留时间最少。 多的零件排在越后面，可使各零件的平均停留时间最少。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 应该如何安排这五个零件的先后顺序才能使完 成这五个零件的总的加工时间为最少？ 成这五个零件的总的加工时间为最少？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中的线条图来表示各零件加工的开始时间与完成 中的线条图来表示各零件加工的开始时间与完成 时间， 这种图是由一根时间轴和车床、 时间 ， 这种图是由一根时间轴和车床 、 磨床在每个 时间段的状况的图形所构成。 时间段的状况的图形所构成。8

车 1 床 1.5 磨 床

2 2.0 1 0.5

3 4 5 1.0 1.25 0.75 2 3 0.25 1.75 4 2.5 5 1.25

10 图 12-1 从上图中我们可以看出， 从上图中我们可以看出 ， 加工时间的延长主要是 由于磨床的停工待料造成的， 由于磨床的停工待料造成的，只要减少磨床的停工待料 的时间就能减少整个加工任务的总

时间。 的时间就能减少整个加工任务的总时间。 为了减少磨床的停工待料， 为了减少磨床的停工待料，我们应该一方面把在车 床上加工时间越短的零件越早加工， 床上加工时间越短的零件越早加工，减少磨床等待的时 另一方面把在磨床上加工时间越短的零件越晚加工， 间；另一方面把在磨床上加工时间越短的零件越晚加工， 以便充分利用前面的时间， 以便充分利用前面的时间，这样我们就得到了使完成全 部零件加工任务所需总时间最少的零件排序方法。 部零件加工任务所需总时间最少的零件排序方法。 0

§1 车间作业计划模型车床 磨床 零 第一工序) 第二工序) 件 (第一工序 (第二工序 第一工序 第二工序 1 1.5 0.5 2 2.0 0.25 3 1.0 1.75 车床 磨床 零 第一工序) 第二工序) 件 (第一工序 (第二工序 第一工序 第二工序 4 1.25 2.5 5 0.75 1.25

寻找例2的最优解： 寻找例 的最优解：我们在上表中找到所列出的最 的最优解 短加工时间是0.25,它是第二道工序磨床加工零件 的所 它是第二道工序磨床加工零件2的所 短加工时间是 它是第二道工序磨床加工零件 需时间，由于这个时间与磨床有关，故我们把零件2放 需时间，由于这个时间与磨床有关，故我们把零件 放 在加工顺序的末尾，即第五位，并在表中划去零件2 在加工顺序的末尾，即第五位，并在表中划去零件 所 在行。如表中红色线条所示。 在行。如表中红色线条所示。10

§1 车间作业计划模型车床 磨床 零 第一工序) 第二工序) 件 (第一工序 (第二工序 第一工序 第二工序 1 1.5 0.5 2 2.0 0.25 3 1.0 1.75 车床 磨床 零 第一工序) 第二工序) 件 (第一工序 (第二工序 第一工序 第二工序 4 1.25 2.5 5 0.75 1.25

接着，我们又找到最短加工时间为0.5, 接着，我们又找到最短加工时间为 ，这一时间与磨 第二工序)有关，我们把磨床加工时间为0.5的零 床(第二工序)有关，我们把磨床加工时间为 的零 放到除第五外的加工顺序的末尾， 件 1放到除第五外的加工顺序的末尾 ， 即第四位加工 ， 放到除第五外的加工顺 …… 此处隐藏：3358字，全部文档内容请下载后查看。喜欢就下载吧 ……