管
理
运
筹
学
26
§2 统筹方法
解：据表12-10,绘制网络图如图12-8。
b 45 c
3
10 d 20 e
f 18
1
a
60
2
4
g 30
6 5
h
i 25
7
j 35
8
40
15
图12-8 如图12-8 ,①-②-③-⑦-⑧就是一条关键路线，我们要干完所有的工序 就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最 长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路
图12-10
其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情
况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF), 显然对同一工序有 LS=LF-t
管 理 运 筹 学
29
§2 统筹方法
运用此法则，可以从收点开始计算出每个工序的LF与LS，如图12-11 所示。
b[60,105] 45[90,135] c[60,70]
工序代号 a b c d e 工序内容 产品设计与工艺设计 外购配套零件 外购生产原料 自制主件 主配可靠性试验 所需时间（天) 60 15 13 38 8 紧前工序 a a c b,d
管
理
运
筹
学
19
§2 统筹方法
解:用网络图表示上述的工序进度表 网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相
工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所在
的行划去。如表12-6中黄色线条所示。 下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故 把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所
解：我们把工序ｆ扩充到图12-4发生了问题，由于ｄ是ｆ的紧前工 序，故ｄ的结束应该是ｆ的开始，所以代表ｆ的弧的起点应该是④，
由于工序ｂ的结束也是④，所以工序ｂ也成了工序ｆ的紧前工序，与
题意不符。 为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，
用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。
160[0,60] 2
a[0,60]
10[107,117] d[60.80] g[80,110]
3
f[70,88] 18[117,135]
20[60,80]
i[110.135] 4 30[80,110] 625[110,135]
7
j[135,170] 35[135,170]
8
e[60.100] 40[80,120]
线。
管 理 运 筹 学
27
§2 统筹方法
• 下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间 （ES )和最早结束时间（EF) ，设一个工序所需的时间为t，这对于同一 个工序来说，有 EF=ES+t。
工序a的最早 开始时间
工序a的最早 完成时间
1
a[0，60]
管 理 运 筹 学
4
§1
二、两台机器、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
1
a 60
2
13 c
b 15 d 38
图12-5
管 理 运 筹
5
e
8
f 4 10
6
3
学
22
§2 统筹方法
在网络图上添加ｇ、ｈ工序得网络图12-6。
1
a 60
2 13 c
b
15
d 38
图12-6
5 8 f
e
6 g 16 h 5 7 10
3
4
在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加 了一个点和虚工序如图12-7。
管
理
运
筹
学
8
§2 统筹方法 用网络图编制的计划称为网络计划，网络计 划技术由计划协调技术（Program Evaluation and Review Technique 简写为 PERT）与关键路径法（Critical Path Method 简写为CPM）组成。
管
理
运
筹
学
9
基本概念
管
理
运
筹
学
10
60 图12-9
1
管
理
运
筹
学
28
§2 统筹方法
b[60,105] 45 f[70,88] 18
c[60,70]
1
a[0,60] 60
2
10 d[60.80] 20
3
4
g[80,110] 30
6
i[110.135] 25
7
j[135,170] 35
8
e[60.100] 40
5
h[100,115] 15
第十二章 排序与统筹方法
在本章中，我们将介绍车间作业计划模型和 统筹方法。这两个问题尽管处理的方法有所不同， 但当我们面临必须完成若干项不能同时进行的工 作时，它们都将帮助我们应该按照怎样的次序、 怎样的时间表来做这些工作，使得效果最佳（例 如完成全部工作所用时间最短或费用最少等等）。
§1 车间作业计划模型 §2 统筹方法
应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间 为 最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。
如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1
中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。
管 理 运 筹 学
25
§2 统筹方法
表12-10
工序代号 a b c d e f g h i j 工序内容 生产线设计 外购零配件 下料、锻件 工装制造1 木模、铸件 机械加工1 工装制造2 机械加工2 机械加工3 装配调试 所需时间（天） 60 45 10 20 40 18 30 15 25 35 紧前工序 / a a a a c d d,e g b,i,f,h
5
h[100,115]
15[120,135
接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间 的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序 的时差，对每个工序来说其时差记为Ts有 Ts=LS-ES=LF-EF
i 1
可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6 ＝ P 1 + ( P 1 + P 2 ) + (P 1 + P 2 + P 3 ) + (P 1 + P 2 + P 3 + P 4 ) + (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个零件的排序问题，只要系数越大，配上加工时 间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工 时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。
2、每个工序的开始时间与结束时间。 3、关键路线及其应用的关键工序。
4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时
间可以推迟多久。 例5、某公司装配一条新的生产线，具体过程如表12-10,求：完成此 工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和 非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以 推迟多久。
示。
管 理 运 筹 学
7
§1
车间作业计划模型
同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故 把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条 所示。 这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能 完成全部加工。 从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部 任务总的时间 最短的排序算法。 在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所 需 时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量 靠后。在表上划去零件j的所在行，回到步骤1。
管
理
运
筹
学
1
§1
车间作业计划模型
车间作业计划是指一个工厂生产工序的计划和安排。
一、一台机器、n个零件的排序问题
二、两台机器、n个零件的排序问题
管
理
运
筹
学
2
§1
车间作业计划模型
一、一台机器、n个零件的排序问题
例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台
磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间
位，并在表中划去零件2 所在行。如表 表12-6 12-6中红色线条所示。