应用运筹学 第八章 项 目 管 理 （网络计划技术） 浙江大学管理学院 杜红 博士 副教授.

Presentation on theme: "应用运筹学 第八章 项 目 管 理 （网络计划技术） 浙江大学管理学院 杜红 博士 副教授."— Presentation transcript:

1 应用运筹学 第八章 项 目 管 理 （网络计划技术） 浙江大学管理学院 杜红 博士 副教授

2 第八章 项目管理（网络计划技术） 项目管理的背景 项目网络的绘制 网络时间的计算 关键线路的确定 网络计划的调整

3 项目管理背景 项目：一系列特定的能自行控制的工作，有 明确的起始与结束时间。 项目管理：计划、组织和控制资源（人员、
设备和物料），使其满足项目的 技术、成本和时间等要求。 项目控制 报告机制：项目进展的信息收集处理系统。 甘特图、成本分解图、时间进度表… 组织机制：项目的组织形式。 组织结构（职能、矩阵）、项目经理、…

4 项目管理背景 网络计划：通过绘制项目网络图与网络计算, 统筹安排工程项目和专项任务。 关键路线技术：运用关键路线制定网络计划.
CPM (Critical Path Method) 关键路线法 PERT (Program Evaluation and Review Technique ) 计划评审技术 适用性：生产技术复杂、工作项目繁多且联系紧 密的一些跨部门的工作计划。如：新产 品研制、大型工程项目、生产技术的准 备，设备大修计划等流程性工程

5 项目管理背景 网络计划制定的条件 网络计划的编制 组成项目的各项活动都可以作为实体加以识别 （有清晰的开始和结束时间，相互独立）
项目活动序列的关系可以被确定和网络化 存在资源调整的可能性 网络计划的编制 工程任务分析（工序划分、关系及时间估计） 绘制网络图形（实、虚箭线、结点、线路） 计算时间参数（最早、最晚开始与结束时间） 确定关键线路（总时差为零的工序为最长线路） 网络优化调整（工期、时间－费用、资源分析）

6 网络图的绘制 网络图的构成 实箭线：表示一道具体的工序。箭头方向表示工序进行方向，箭尾位置表示工序开始，箭头位置表示工序结束。
虚箭线：表示一道虚工序，虚工序仅仅表示工序与工序之间的关联关系，不需要消耗时间和资源。 工序名称或代码 工序时间 工序名称或代码

7 网络图的绘制 网络图的构成 结点：又称事项、事件等。表示一个工序的开始或结束。用圆圈表示，在圈内注上该结点的序号。整个网络图的开始事项称起始结点，最后工序结束事项为结束结点。只有当某一结点的所有紧前工序都完成后，它的紧后工序才能开始 （A是B的紧前工序，B是A的紧后工序） 线路：从起始结点沿箭头方向连续不断地到达终点的通路。线路有多条，线路的长度为各工序的时间和，最长的为关键线路。 A B 1 2 3

8 网络图的绘制 绘制网络图的准备工作 确定目标：以时间要求还是资源费用要求为主 工程分解：列出全部分解后的工序及代号清单
工序关系：确定每一道工序的紧前工序是哪些 工序时间：确定每一道工序的完成所需的时间 一时估计法：仅估计一个完成工序的最大时间D 三时估计法：乐观时间 a、悲观时间b、最可能时间m

9 网络图的绘制 网络图绘制规则 方向、时序与结点编号
网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间（某一个或若干个工序开始或结束时间），一般按结点的时间顺序编号（从左到右，从上到下），箭尾结点编号应小于箭头结点编号。始结点编号为1。 网络图中不能出现缺口和回路 二个结点之间只能有一个直接的工序 两条箭线不能有同样的始末结点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。

10 网络图的绘制 网络图绘制规则 平行作业 有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。 交叉作业 对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。

11 网络图的绘制 网络图绘制规则 始点和终点 为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始结点或一个终结点表示时，需用虚工序把它们与始结点或终结点连接。 网络图布局 尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。

12 网络图的绘制 虚工序应用 工序 紧前 A B C D -- A,B 3 2 1 1 2 4 5 1 4 3 2 6 5 A A B B A

13 网络图的绘制 虚工序应用 工序 紧前 A B C D -- A,B 3 2 1 1 2 4 2 1 3 5 6 2 1 4 3 A B A

14 网络图的绘制 虚工序应用（平行与交叉） A:修路基 B:铺轨道 2 1 2 3 1 4 5 3 A=A1+A2+A3 B=B1+B2+B3
12 12 4 12 A3 4 3 A:修路基 B:铺轨道 A1 A2 A3 1 2 4 6 A=A1+A2+A3 B=B1+B2+B3 B3 B1 B2 3 5 7 8

15 网络图的绘制 例8－1：某化工厂管道安装的工程进度表: 工程项目 分解 工序 代号 紧前 时间 器材调查 停用管道 搭脚手架 拆除旧管道阀门
装备阀门 装备管道 组装管道 安装管道 A B C D E F G H --- B,C D,E,G 8 12 35 225 200 40 32 工程项目 分解 工序 代号 紧前 时间 安装阀门 焊接管道 装配管道 和阀门 包扎阀门 拆脚手架 压力试验 整理现场 I J K L M N P D,E H,I K,L M,N 8 24 4 6

16 网络图的绘制 例8－1：某化工厂管道安装的网络图 先画出没有紧前工序的工作A,在A后画出紧前工序为A 的各工作,即B,C,E,F。 B C

17 网络图的绘制 例8－1：网络图的绘制 在表中查出B,C为D的紧前工序，F为G的紧前工序，则在F工序后画出G，在B,C工序后面画出D。 B D
A B C E F D G

18 网络图的绘制 例8－1：网络图的绘制 画出H,I,J的工序如下： H紧前： D、E、G I紧前： D、E J紧前： H、I B D I J
C A E F H 除 J 外已没有 紧后工序 G H

19 网络图的绘制 例8－1：网络图的绘制 画出K,L工序，K,L的紧前工序均为J。 B K D I J C A L E H F G

20 网络图的绘制 例8－1：网络图的绘制 在K,L后画出M,N,P： M紧前： K、L N紧前： K P紧前： M、N B K N D I J
C P A L M E H F G

21 网络图的绘制 练习：画出以下网络图 工序 工序代号 所需时间 紧后工序 产品设计 A 60 B,C,D,E 外购配套件 B 45 L
下料、锻件 C 10 F 工装制造1 D 20 G,H 木模、铸件 E 40 H 机械加工1 18 工装制造2 G 30 K 机械加工2 15 机械加工3 25 装配调试 35 --

22 网络图的绘制 练习答案： B 45 F 3 C 18 10 A D G K L 1 2 4 6 7 8 30 25 35 60 20 E H
40 15

23 时间参数的计算 符号约定 i j K E(i) L(i) E(j) L(j) D(i,j) S(i) S(j) E(j) ESij LSij
L(n)=E(n) EFij LFij

24 时间参数的计算 结点（事项）时间 结点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，结点参数主要只有两个：最早实现时间（最早时间）和最迟实现时间（最迟时间）。 最早时间：以该结点结束的工作最早可能结束的时间，或以该结点开始的工作最早可能开始的时间。E(1)=0, E(n)为工程时间，从左往右计算。 最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),L(0)=0，从右往左计算。

25 时间参数的计算 结点（事项）时间计算 结点最早时间E(j)的计算 E(1)=0
E(j)=max[E(i)+D(i,j)], i=2,3,4,…… E(7)=5 7 E(9)=MAX[E(7)+6,E(8)+7)] =13 6 9 E(8)=6 7 8

26 时间参数的计算 结点（事项）时间计算 结点最迟时间L(i)的计算 L(n)=E(n)
L(i)=MIN[L(j)-D(i,j)], j=n-1,n-2,…… L(10)=70 L(9)=MIM[L(10)-20, L(11)-12)] =50 10 20 9 L(11)=89 12 11

27 时间参数的计算 工序时间参数计算 一个工序可以从箭尾结点的最早时间开始作业，也可以适当推迟开始，但须在箭头结点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。 最早开始时间: ESij=E(i) 最早结束时间：EFij=ESij+D(i,j) 最迟结束时间：LFij=L(j) 最迟开始时间：LSij=LFij-D(i,j)

28 时间参数的计算 时差及计算 结点时差：最迟与最早时间差 S(i)=L(i)－E(i)
工序总时差：不影响工期(最早结束时间）的该工序可松动的时间（可以推迟开始的时间）. Sij = LSij － ESij = LFij － EFij = L(j) － E(i) － D(i,j) （总浮动） 工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间. Rij = E(j) － EFij （自由浮动）

29 时间参数的计算 工序及时差关系 工序 A 工序A 的紧后工序 LS EF LF ES D ES LS EF LF 总时差SA 单时差RA
(自由浮动) 工序A 的紧后工序 总时差SA

30 关键线路的确定 关键线路 关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。 关键线路的确定
破圈法：在圈中去掉最短的一个工序。 图上作业法：标注结点时间，结点时差为0的结点组成关键线路。 表上作业法：计算工序时间，总时差为0的工序组成关键线路。

31 关键线路 A-D-G-K-L ( 1-2-4-6-7-8), 长度为 170
例8-2：关键线路的确定 破圈法： B 45 F 3 C 18 10 A D G K L 1 2 4 6 7 8 30 25 35 60 20 E H 5 40 15 关键线路 A-D-G-K-L ( ), 长度为 170

32 关键线路的确定 图上标注法 1 5 3 8 7 6 4 2 A H E L K G D F C B 60 45 18 10 20 40 15
30 25 35 117 70 60 135 170 60 135 170 80 110 80 110 120 100

33 关键线路的确定 表上作业法 工序 D ES LS EF LF S 关键否 A 60 是 B 45 90 105 135 30 C 10
是 B 45 90 105 135 30 C 10 107 70 117 47 20 80 E 40 100 120 F 18 88 G 110 H 15 115 K 25 L 35 170

34 分布式活动周期时间参数计算 项目评审技术 例8-3 ：实例10.7，教材P307 实例10.8，教材P308 六分之一原则
整个项目的周期服从正态分布 均值为关键线路上所有活动的期望周期和 方差为关键线路上所有活动周期方差和 例8-3 ：实例10.7，教材P307 实例10.8，教材P308

35 网络图的调整及优化 缩短工程计划工期问题 保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。 压缩关键工序的工序时间
在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。 在非关键工序上尽量挖掘潜力 利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。 采用平行或交叉作业

36 例8－3：缩短计划工期 某工程有关的工序关系及时间如下： 工序代号 所需时间 紧后工序 A 2 B,C,D B 3 E C 5 F,H D
4 G 6 H F L,J 1 L M J --

37 例8－3：缩短计划工期 画出网络图： E 3 6 6 H B 3 4 A C F J M 1 2 4 7 9 10 2 5 2 4 3 D
L 4 5 G 5 8 1

38 关键线路 A-B-E-H-M ( 1-2-3-6-9-10), 长度为 18
例8－3：缩短计划工期 计算时间参数，确定关键线路： 11 5 11 5 E 3 6 6 H 2 B 15 18 3 4 2 8 10 15 18 7 9 A C F M 1 2 4 7 J 9 10 2 5 2 4 3 L D 6 9 5 4 G 5 8 9 10 1 关键线路 A-B-E-H-M ( ), 长度为 18

39 例8－3：缩短计划工期 现要求将整个计划工期缩短3天。 具体做法如下： 首先从关键线路上想办法，能否缩短3天？
也要考虑其它非关键线路上工时缩短的情况。 具体做法如下： 将图中的最后一个节点的最迟时间设定为15 倒退计算法求出各工作的时差 找出所有时差为负值的工序 对其中的关键工序进行协调，缩短工作时间，使总时间为15天 重新计算时间，如仍有负时差工序，再考虑缩短该工序的时间，直到没有负时差为止。

40 例8－3：缩短计划工期 将第10节点的最迟时间设定为15，计算各工序时差 E 3 6 6 H B 4 3 A C F M 1 2 4 7 J
11 5 E 3 6 -3 6 H －3 －1 B 12 15 15 -3 -3 4 3 2 5 7 18 7 9 15 15 A C F M 1 2 4 7 J 9 10 -2 -2 -1 -3 2 -3 5 2 4 3 L D 6 -2 9 5 4 G 5 8 6 15 12 7 1 18

41 例8－3：缩短计划工期 从图中可以看出： 在原关键线路上各工序的总时差均为－3，因此 需要在原来的关键线路上缩短3天。
除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。 共有以下几条需要缩短： 第一条：1－2－3－6－9－10 缩短3天 第二条：2－4－7－8－ 缩短2天 第三条：7－ 缩短1天 必须满足以上条件才有可能缩短3天 先考虑关键线路缩短3天，经协调使B、M、E各减1天： B和M工序各缩短为2天，E工序缩短为5天 重新计算时间

42 负时差线路： 1-2-4-7-8-9-10, 每个工序总时差为－1
例8－3：缩短计划工期 关键路线工序时间缩短后，重新计算时间： 9 4 9 4 E 3 6 5 6 H －1 1 B 13 15 3 2 4 2 6 8 14 16 7 9 A C F M 1 2 4 7 J 9 10 -1 -1 -1 2 -1 5 2 4 3 2 L D 6 -1 9 5 1 4 G 5 8 7 8 1 1 负时差线路： , 每个工序总时差为－1

43 关键线路有两条： 1-2-4-7-8-9-10 、 1-2-3-6-9-10
例8－3：缩短计划工期 负时差工序C时间缩短1天后，重新计算时间： 9 4 9 4 E 3 6 5 H 2 B 13 15 2 4 2 6 8 13 15 6 8 A C F M 1 2 4 7 J 9 10 1 2 4 5 2 4 2 L D 6 8 5 1 4 G 5 8 7 8 1 1 关键线路有两条： 、

44 网络图的调整及优化 缩短工程计划工期问题 保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。 压缩关键工序的工序时间
在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。 在非关键工序上尽量挖掘潜力 利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。 采用平行或交叉作业

45 例8－3：缩短计划工期 将第10节点的最迟时间设定为15，计算各工序时差 E 3 6 6 H B 4 3 A C F M 1 2 4 7 J
11 5 E 3 6 -3 6 H －3 －1 B 12 15 15 -3 -3 4 3 2 5 7 18 7 9 15 15 A C F M 1 2 4 7 J 9 10 -2 -2 -1 -3 2 -3 5 2 4 3 L D 6 -2 9 5 4 G 5 8 6 15 12 7 1 18

46 例8－3：缩短计划工期 从图中可以看出： 在原关键线路上各工序的总时差均为－3，因此 需要在原来的关键线路上缩短3天。
除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。 共有以下几条需要缩短： 第一条：1－2－3－6－9－10 缩短3天 第二条：2－4－7－8－ 缩短2天 第三条：7－ 缩短1天 必须满足以上条件才有可能缩短3天 先考虑关键线路缩短3天，经协调使B、M、E各减1天： B和M工序各缩短为2天，E工序缩短为5天 重新计算时间，如果还有负时差，再缩短，再计算时间，直到没有负时差为止。

47 网络图的调整及优化 工程的时间-费用优化 费用分析： 费用＝直接费用＋间接费用 直接费用：直接生产工人工资、资源直接消
耗等直接与完成工序有关的费用 一般情况下，作业时间越短，直接费用越多 间接费用：管理人员的工资、办公费等，需 按施工时间长短分摊 一般情况下，作业时间越短，分摊间接费用越少

48 网络图的调整及优化 费用与完工时间的关系 工 程 费 用 总费用 直接费用 间接费用 极限时间 T’ 正常时间

49 网络图的调整及优化 时间-费用优化分析方法： 最低成本日程：费用最低的工程完工时间T’ 直接费用变动率g：缩短单位时间增加的直接费用
T’计算程序（教材P315) 按正常时间画出网络图，找到关键线路计算成本时间 在关键线路上找出g最小的工序，压缩活动时间 重复上一步，直到总费用上升为止

50 例8－4：教材P315，实例10.12 画出网络图，计算网络时间： B C 2 5 7 7 5 A 3 D 5 E F G J 1 3 6
17 5 10 15 3 B C 2 5 7 7 5 A 24 3 D 5 8 14 24 8 14 E F G J 1 3 6 8 9 8 8 6 2 22 22 H I 12 6 4 16 12

51 例8－4：教材P315，实例10.12 关键路径为 E-F-G-J,周期为24周，正常总成本为正常成本的加总，总计为221000，超过要求时间6周，罚金成本为21000，总成本为242000。 计算压缩每项工序后的单位加急成本g(单位：千英镑/周）: A B C D E F G H I J A-B-C-D与H-J的总浮动分别为2和4，在它们成为新的关键线路之前，关键线路 E-F-G-J上能压缩的最大时间是2周，找出其中的 g 值最小的工序是 E，E最多能缩短3周，因此对 E 减少2周是可行的。

52 例8－4：教材P315，实例10.12 此时，时间计算结果如下： B C 2 5 7 7 5 A 3 D 5 E F G J 1 3 6 8
A 22 3 D 5 6 12 22 6 12 E F G J 1 3 6 8 9 8 8 6 6 2 20 20 H I 12 6 4 14 12

53 例8－4：教材P315，实例10.12 计算E压缩2周后成本的变化： 加急成本增加：2×g=2×2000＝4000
处罚成本减少：2×3500＝7000 还可以继续压缩。 关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为E和B, E最多只能压缩1周，B虽能压缩3周，但如压缩时间超过1周后，它就不再是关键线路，因此先考虑B也压缩1周的情况，此时总时间为21周。加急成本增加为2000＋1000＝3000，处罚成本节省3500。因此，还可以继续压缩。

54 例8－4：教材P315，实例10.12 此时，时间计算结果如下： B C 2 5 7 7 6 5 A 3 D 5 E F G J 1 3 6
9 14 3 9 14 3 B C 2 5 7 7 6 5 A 21 3 D 5 5 11 21 5 11 E F G J 1 3 6 8 9 8 5 6 6 2 19 19 H I 12 6 4 注意：此时H-I的总时差为1 13 12

55 例8－4：教材P315，实例10.12 关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为G和B, G最多只能压缩2周，B还能压缩2周，但如压缩时间超过2周后，H-I-J的时间要大于它们，就不再是关键线路，因此考虑B和G各压缩1周的情况，此时总时间为20周。加急成本增加为1000＋2500＝3500，处罚成本节省3500。因此，已不能再压缩，找到的最低成本时间为20周。 成本节省 总正常成本22100， 加急成本增加：4000＋3000＋3500＝10500； 延误2周的处罚成本：2×3500＝7000； 总成本238500； 总成本节省：242000－238500＝3500。

56 例8－4：教材P315，实例10.12 此时，时间计算结果如下： B C 2 5 7 6 5 5 A 3 D 5 E F G J 1 3 6
13 3 8 13 3 B C 2 5 7 6 5 5 A 20 3 D 5 5 11 20 5 11 E F G J 1 3 6 8 9 5 6 7 8 2 18 18 H I 12 6 4 此时三条线路均为关键线路 12 12

57 作业：画网络图并计算时间

58 网络图的调整及优化 时间－资源优化 尽量合理地利用现有资源，并缩短周期 时间－资源优化方法 优先安排关键工序所需要的资源；
利用非关键工序的总时差，错开工序开工时间，拉平资源需要量的高峰； 在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当地推迟完工时间

59 例8－2：关键线路的确定 1 5 3 8 7 6 4 2 A H E L K G D F C B 60 45 18 10 20 40 15
30 25 35 117 70 60 135 170 60 135 170 80 110 80 110 120 100

60 网络图的调整及优化 例8－4：在例8-2的基础上考虑以下资源： 工序 作业时间 需要人数 总时差 D F G H k 20 18 30 15
25 58 22 42 39 26 47

61 每个工序都从最早时间开始： 70 F 22 3 C 18 60 10 80 110 135 D 58 G 42 K 26 2 4 6 7 20 30 25 100 H 39 5 工 人 数 15 42＋39 ＝81人 58＋22 ＝80人 65 26＋39 ＝65 22＋42 ＝64人 58人 42人 26人 时间 60 70 80 88 100 110 115 135

62 开始时间适当调整后的结果： 47 F 22 3 18 D 58 G 42 K 26 2 4 6 7 20 30 25 20 H 39 5 工 人 数 15 F推迟10 H推迟10 65 26＋39 ＝65人 K H 22＋42 ＝64人 F G 58人 D 42人 G 26人 K 时间 60 70 80 98 100 110 125 135