C 20 D 12
4 3
代号
A B C
后续作业
B、C D
炒菜
D
12min
A:淘米 B:洗切菜 C:煮饭 D:炒菜
1
A 2
2
B 7
C 20
D 12
4
3
由上图可看出关键路径为A－C或1－2－4， 长度为22。但复杂的图形就不易看出。
客来沏茶
PERT解法：i 最早完成时间, j 最晚完成时间。 7.5 0 0 洗杯盖2 7 7 端茶0.5
㈡关键路径问题 1、节点v的后继元素Γ (v)={x|x∈V且vx∈E}
+
2、节点v的先驱元素Γ-(v)={x|x∈V且xv∈E}
3、从发点起求最早完成时间(TE):是指活动最早 可能完成的时间 TE(vi)=
max){TE (v j ) w ji } v (v
j i
4、从收点起求最迟完成时间(TL):是指活动最迟 必须完成的时间 TL(vi)= j ij v j (vi ) 5、ES(vi)=TL(vi)-TE(vi)叫缓冲时间。缓冲时 间是0的节点组成关键路径。
一、网络计划方法的产生
㈠起源：网络计划方法是项目计划管理的重要方法。它 起源于美国。当时，有两种网络计划方法：关键路线法 和计划评审技术。 1957年，美国杜邦化学公司用关键路线法(Critical Path Method)。当年就节约100万美元，为该公司用于 该项目研究费用的5倍以上。 1958年，美国海军当局在研制北极星导弹潜艇时， 第一次采用了BuzzAllen提出的计划评审技术(Program Evaluation and Review Technique),主要承包商200多 家，转包商10000家。23个系统网络，每两周检查一次， 原定6年，提前两年完成，节约经费10—15％。 60年代耗时11年阿波罗登月计划3000亿$,42万人,2 万家公司,120所大学,600台计算机,700万零件,终于在 1969年7月，阿波罗11号船长阿姆斯特朗登上月球。
F 5
5 14 14 H 6
I 3
7 20 20
收点
最早完成时间(TE)；
几个概念
最晚完成时间(TL)； 缓冲时间(ES)； 各顶点的缓冲时间为0的(由发 点到收点的)通路叫关键路径。
关键路径问题
117 3 70 c 0 a 60 10 80 d 1 60 2 20 4 0 60 80 e 40 b 45 f 18 g 110 i 30 6 25 110 120 h 5 15 100
关键路径(统筹方法)
国外起源于上世纪50年代，60-70年 代我国开始应用和推广。钱学森、华 罗庚等都曾为此做了大量工作。
华罗庚的例子：有客来访，要请他饮 茶，于是要做几件事：洗茶杯、洗杯 盖、烧开水、泡茶到端茶。
本问题的几道“工序”有次序, 时间: 洗杯盖 2 烧水5 泡茶2 洗杯1 虚0 端茶0.5
紧后活动
B,C D E,F G,I G,I H J I,K J L 无 无
活动时间(周) 3 4 6 8 8 5 3 6 3 5 8 3
例题
活动编号 作业时间 ET(i) LT(j) ES(i,j) EF(i,j) LS(i,j) LF(i,j)
①
②
③
④
⑤=③
⑥=⑤+②
⑦=④-②
⑧=④
1— 2 2— 3 2— 4 3— 5 3— 6 4— 5 4— 7 5— 8 6— 8 7— 8
4 8 2 5 3 6 8 15 4 6
0 4 4 12 12 6 6 17 15 14
4 12 11 17 28 17 26 32 32 32
0 4 4 12 12 6 6 17 15 14
4 12 6 17 15 12 14 32 19 20
0 4 9 12 25 11 18 17 28 26
4 12 11 17 28 17 26 32 32 32
H 1
制作比赛用具
搬运用具 联系运动场 布景运动场
G
H I J
H
J J 结束
7
1 1 1
客来沏茶
网络图的画法
项目 代号 后续作业 时间 A 淘米 B、C 2分 D 洗切菜 B 7分 C 煮饭 结束 20分 D 炒菜 结束 12分
用带箭头的线段表示每项作 业或任务，标有数字的圆圈 表示作业的开始和结束，把 工期标于箭头上。
1
项目
淘米 洗切菜 蒸饭
A 2
2
B 7
时间
2min 7min 20min
例题
发点
7 12 3
D 8 9 9 E 4 8
① ②的先驱元素是___ ② ④的先驱元素是___ ⑤的先驱元素是___ ④
⑨的后继元素是___ ⑩
⑧的后继元素是___ ⑨
B 4
0 0 1 A 3 2 3 3 C 6
17 20 6
G 3
23 23 8
J 28 28 L 9 5 3 K 8
31 31 10
运动会
3 A 5 B 10 2 I 1 1
C 10 E 3 G 7
4 D 1 F 1 J 1 7
5
8
6
作业名称 研究方案 制定比赛程序表 印刷比赛程序表 分发比赛 B C D E F
后续作业 B、I C、E、G D 结束 F 结束
作业长度 5 10 10 1 3 1
7.5
烧水5 泡茶2 洗杯1 5 5 虚0
1 5
最佳次序：先 烧开水，等待水开 之时洗杯、盖，水 烧开后泡茶，端茶。
关键路径问题
TQC(全面质量管理)中的重要问题： 有向图：每条边有方向(即边v1v2 与 边v2v1是区别的)的图。 工序之间的次序关系用有向图表示 叫PERT(计划评审技术)图。 避免窝工，掌握工程进展中关键工 序，提高工程速度的技术——关键 路径。
135j 170 7 35 8 135 170
124678
学校准备开一个运动会,作业 明细表如下,请画出网络图
作业名称 研究方案 制定比赛程序表 印刷比赛程序表 分发比赛程序表 预定奖品 验收奖品 制作比赛用具 搬运用具 联系运动场 布景运动场 作业代号 后续作业 作业长度 A B C D E F G H I J B、I C、E、G D 结束 F 结束 H J J 结束 5 10 10 1 3 1 7 1 1 1
min
{TL(v ) w }
㈢绘制方法
• 某机械厂管理信息系统开发活动清单
编号
A B C D E F G H I J K L
活动描述
系统分析和总体设计 输入和输出设计 模块1详细设计 输入和输出程序设计 模块1程序设计 模块2详细设计 输入和输出及模块1测试 模块2程序设计 模块1测试 系统总调试 文档编写 系统测试