第12章 排序与统筹方法

管理运筹学赵明霞 山西大学管理学院1

管

理

运

筹

学

第十二章 排序与统筹方法§1 车间作业计划模型

§2 统筹方法

2

管

理

运

筹

学

§1

车间作业计划模型

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

3

管

理

运

筹

学

一、一台机器、n个零件的排序问题例1.某车间只有一台高精度的磨床，常常出现很多零件同时要 求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加 工所需时间如下表所示。 零件 1 2 3 加工时间 (小时) 1.8 2.0 0.5 零件 4 5 6 加工时间 (小时) 0.9 1.3 1.5

应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件

在车间里停留的平均时间为最少？

4

管

理

运

筹

学

如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 +…+ Pj-1 + Pj =

Pi 1

j

i

不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使 得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问

题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停 留时间为Tj , Tj = Pii 1 j

5

管

理

运

筹

学

可知这六个零件的停留时间为：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

管

理

运

筹

学

二、两台机器、n个零件例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工 时间如表12-5所示。表12-5零件 1 2 3 车床 1.5 2.0 1.0 磨床 0.5 0.25 1.75 零件 4 5 车床 1.25 0.75 磨床 2.5 1.25

应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？管 理 运 筹 学7

解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为1,2,3,4, 5。我们

用图12-1中的线条图来表示各零件加工的开始时间与完 成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状 况的图形所构成。车床

1

2

3

4

5

磨床

1

2

3

4

5

0

10

图 12-18

管

理

运

筹

学

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

一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的 时间。

这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方 法。

9

管

理

运

筹

学

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

零件2 所在行。如表12-6中红色线条所示。零 件 1 2 3 车床 磨床 (第一工序) (第二工序) 1.5 2.0 1.0 0.5 0.25 1.75 零 件 4 5 车床 磨床 (第一工序) (第二工序) 1.25 0.75 2.5 1.25

接着，我们又找到最短加工时间为0.5,这一时间与磨床(第二工序)有关，我们把磨床加工时间为0.5的零件1放到除第五外的加工顺序的末 尾，即第四位加工，同时把 表中的零件1所在的行划去。如表12-6中黄

色线条所示。10

管

理

运

筹

学

下一个最短加工时间为0.75,这个加工时间是车床(第一工序)加工零件5的 所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的 行划去。如表12-6中蓝色线条所示。 同样，下一个最短加工时间为1,这是车床加工零件3的所需时间，故把零件3 排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。 这样就得到了最优加工顺序：5,3,4,1,2。一共只需7个小时就能完成全 部加工。 从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总 的时间最短的排序算法： 在加工所需时间表上选出最短加工时间tij,这是第i工序加工j零件所需时间，

当i=1时，将零件j的顺序尽量靠前， 若i=2时，将零件j的顺序尽量靠后。 在表上划去零件j的所在行，重复上述步骤。11

管

理

运

筹

学

§2

统筹方法

通过重组,打乱,优化等手段改变原本的固有办

事格式,优化办事效率的一种办事方法。 一种安排工作进程的数学方法。

它的实用范围极广泛，在企业管理和基本建设

中，以及关系复杂的科研项目的组织与管理中，

都可以应用。

华罗庚12

管

理

运

筹

学

统筹方法包括绘制计划网络图、进度安排、网络优化等环节。一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序 (或称为活动)进度表转换为统筹方法的网络图。 例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系

都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。工序代号 a b c d e 工序内容 产品设计与工艺设计 外购配套零件 外购生产原料 自制主件 主配可靠性试验管 理 运 筹

所需时间 (天) 60 15 13 38 8学

紧前工序 a a c b,d13

解:用网络图表示上述的工序进度表

网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表 示点的编号。弧表示一个工序(或活动),弧的方向是从工序开 始指向工序的结束，弧上是各工序的代号，下面标以完成此工序 所需的时间(或资源)等数据，即为对此弧所赋的权数.

1

a 60

2 13 c

b 15 3

4 d 38

e 8

5

图12-414

管

理

运

筹

学

例4、把例3的工序进度表做一些扩充，如表12-9,请画出其统 筹方法的网络图。

工序代号a b c d

所需时间(天)60 15 13 38

紧前工序- a a c

工序代号 所需时间(天) 紧前工序e f g h 8 10 16 5 b,d d d e,f, g

15