运筹学课件--第8章 网络计划

1、管理运筹学-管理科学方法,李军,桂林电子科技大学商学院,2,Sub title,OR:SM,第8 章 网络计划 内容提要 第一节 网络图的绘制 第二节 关键路线法 结点的时间参数 作业的时间参数 时差与关键路线 第三节 计划评审技术 第四节 网络计划优化 缩短工程工期 工期-费用优化 工期-资源优化 第五节 缓冲时间设置,3,OR:SM,OR:SM,第8 章 网络计划 教学目标： 通过本章的学习，掌握网络图的绘制方法，掌握时间参数 的计算方法，并能够找出关键路线；能够对实际的项目进行 时间与资源的优化与调整。 教学要求：,知识要点 绘制网络图,能力要求 （1）了解网络图的基本 概念：工序、事件

2、、路线 （2） 绘制网络图的规则 （3）计算网络图的时间 参数 （4）找出关键路线 （1） 时间优化,相关知识,4,网络计划优化 （2） 费用优化 （3） 资源综合优化,费用的构成,OR:SM,OR:SM,第8 章 网络计划 网络计划的发展历程 关键路线法(Critical Path Method，CPM ) 计划评审技术(Program Evaluation and Review Technique，PERT ) 图示评审技术(Graphic Evaluation and Review Technique，GERT ) 风险评审技术(Venture Evaluation Review Tec

3、hnique，VERT ) 网络计划技术的特性 明确表达各项工作的逻辑关系 通过时间参数计算，确定关键工作和关键线路 掌握机动时间，进行资源合理分配 运用计算机辅助手段，调整与控制,5,OR:SM,OR:SM,第一节,网络图的绘制,一、网络计划的图示形式 工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程 在网络图中用箭线“” 表示， 前面直接相连工序称紧前工序， 直接相连的后继工序为紧后工序。 结点(事项)：相邻工序的分界点（每一箭头始端和末端各有一个结 点，表示前一个作业的结束和后一个作业的结束，即两个事件。） 一般用圆圈来表示，每个结点编上顺序号， 结点既不消耗人力、物力，也不

4、占用时间。 网络图 由工序、事项及时间参数所构成的有向图即为网络图。 箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络 结点表示工序,箭线为工序间相互关系的网络图，称结点式网络,6,OR:SM,OR:SM,第一节,网络图的绘制,一、网络计划的图示形式,1、箭线式网络图 N作业名称 i t作业时间 2、结点式网络图,j,1,A 2,2,B 5 C 3,3 4,D 5 E 5,5,i N t,i作业序号 N作业名称 t作业时间,1 2,2 5,3 5,6,0,7,4 3,5 5,OR:SM,OR:SM,第一节,网络图的绘制,二、箭线式网络图的规则 工序表示的规定 一条箭线和它的相关事项只能

5、代表一道工序，不能代表多道工序，两个结点之 间只能有一条箭线相连。 不允许出现缺口与回路 网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可 以到达终点。 虚工序 虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。 不消耗时间、费用和资源，一般用虚箭线表示。 方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。 编号的规定 编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。,8,OR:SM,OR:SM,二、箭线式网络图的规则 箭线不允许出现循环。 图中234就是一个循环。,2,4,5,1 3 两相邻

6、结点之间只允许有一条箭线相连。作业A和B是 两个并行的作业，在计算机系统中，作业A和B均用（1， 2）表示，无法区别这两个作业。此时，可借助于虚作业 来表示。,A,1,A,3,1,B,3,B,2,C,9,OR:SM,OR:SM,二、箭线式网络图的规则（续） 箭头结点的编号（j）要大于箭尾结点的编号（i）。编号,可以不连续编。例如：,3,4,一个完整的网络图只能有一个起点和一个终点。,错误,正确, 箭线首尾都应有一结点，不能从一箭线中间引出另一箭 线。 5,10,3,4,OR:SM,OR:SM, 双代号,最早开 始时间,最早结 束时间,11,i 事件序号,活动描述 工作持续时间 双代号网络图的表

7、示方法,j 事件序号,OR:SM,OR:SM,一、双代号网络图的表示方法 双代号网络图的三要素指箭线、节点和线路。 A、箭线（指工作、工序、作业、活动） 资源、时间和空间 紧前工作、紧后工作 和平行工作,12,OR:SM,OR:SM,一、双代号网络图的表示方法 虚工作表示工作之间的先后逻辑关系，不耗用资源，也不占用 时间。符号表示: B、节点：表示工作之间的联系（起始节点，终止节点，中间节点） 开始 完成 i “时点” C、线路：线路的长度，即线路所需要的时间。（关键路线总 持续时间最长的线路；非关键线路除了关键线路之外的线 路。）,13,OR:SM,OR:SM,绘制网络图的步骤（双代号） 第

8、一步：找出所有从节点1开始的活动。画出它们结束 的节点，并在节点1与他们的每一个结束节点之间画一条 箭线。将活动字母代号或名称写在相应的箭线上方，历 时估算写在箭线的下方。 第二步：继续从左至右绘制网络图，寻找分叉点与交会 点。 第三步：继续绘制网络图，直到图中包括了所有的活动。 双代号网络图中所有的箭头应该指向右方，不应当有箭 线交叉。,14,OR:SM,OR:SM,第一节,网络图的绘制,三、箭线式网络图举例 某工程的工程一览表,工序 紧前工序 工序时间,a - 6,b - 3,c - 4,d a 4,e a,c 5,f b 10,g b,d,e 8,4,b,3,10,f,1,a 6,2,d

9、 4,5,g 8,6,4,c,e,5,3,15,OR:SM, L,OR:SM,第二节,关键路线法,一、结点的时间参数 结点的最早时间tE(j) tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。 从始点事项开始，自左向右，顺着箭线方向逐个计算 。 t E (1) 0 t E ( j ) max t E ( i ) t ( i , j ) i 结点的最迟时间 tL(j) 指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响 后续工序按时开工，以至推迟整个工程的完工时间。 从终点开始，从右向左，逆箭线方向逐个计算。 t L ( n ) t E ( n ) t ( i ) min

10、t L ( j ) t ( i , j ) j,16,OR:SM,OR:SM,第二节 一、结点的时间参数,关键路线法,计算结点时间参数,3,4,9,b,3,10,f,0 0,1,a 6,6,2,6,d 4,5,11,g 8,6,19 19,4,c,3,e,5,11,17,6,6,OR:SM,OR:SM,补充双代号绘图题,工作 A B C D E F,紧前工作 - A A B C B,C,时间 4 3 2 1 5 7,工作 G H I J K L,紧前工作 D D,F E,F G,H H,I J,K,时间 6 3 8 9 6 4,要求：画出网络图并计算各节点最早时间和最迟时间,18,OR:SM,

11、OR:SM,第二节,关键路线法,二、作业的时间参数 最早可能开工时间tES(i, j) 一个作业必须在其各紧前作业都完工后才能开工， 作业最早可能开工时间等于其箭尾事项的最早时间。 tES(i, j)= tE(i) 最早可能完工时间 tEF(i, j) 从最早可能开工时间开工，完成本作业的时间 。 tEF(i, j)= tES(i, j) +t(i, j) 最迟必须开工时间 tLS(i, j) 在不影响工程如期完工的前提下，作业最迟必须开工的时刻。 等于它的箭头事项的最迟时间减去本作业的作业时间 tLS(i, j)= tL( j) - t(i, j) 最迟必须完工时间 tLF(i, j) 在不

12、影响工程如期完工的前提下，作业最迟必须完工的时刻 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j),19,OR:SM,OR:SM,第二节,关键路线法,三、时差与关键路线 时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动 使用的一段时间。 总时差R(i, j)：不影响其紧后工序最迟必须开工的前提下，本工序最早 可能完工时间可以推迟的时间。 R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) 单时差r(i, j)：不影响其紧后工序最早可能开工的前提下

13、，本工序最早 可能完工时间可以推迟的时间。 r(i, j)= tE( j) -tE(i) -t(i, j) 总时差为零的工序称为关键工序；关键工序组成关键路线。,tES,tLS,tEF,tLF,20,r(i,j),tES R(i,j),tLS,tEF,tLF,OR:SM,1,3,OR:SM,第二节 三、时差与关键路线,关键路线法,路线,路线的组成 ,路线长度 3+10=13,2, ,3+0+8=11 6+4+8=18,3,4,9,4 5, ,6+0+5+8=19 4+5+8=17,b,3,10,f,0 0,1,a 6,6,2,6,d 4,5,11,g 8,6,19 19,4,c,3,e,5,1

14、1,21,6,6,OR:SM,OR:SM,第二节,关键路线法,四、时间参数算例 计算作业最早开始时间、最迟开始时间、最早结束时间、 最迟结束时间以及时差，从表中寻找总时差与单时差都为零 的作业，即为关键作业，将其连接起来就是关键路线。,作业,t (i, j),tES (i, j) tEF (i, j),tLS (i, j) tLF (i, j),R(i, j),r (i, j),关键 作业,a b c d e f g,6 3 4 4 5 10 8,0 0 0 6 6 3 11,6 3 4 10 11 13 19,0 6 2 7 6 9 11,6 9 6 11 11 19 19,0 6 2 1

15、0 6 0,0 0 2 1 0 0 0,a - - - e - g,22,OR:SM,OR:SM,例 一个项目由九个作业所组成，每个 作业的作业时间如表所示。,作业 时间,A 10,B 15,C 12,D 20,E 18,F 8,G 16,H 10,I 20,（天） 作业的先后顺序为：A、B、C三个作业同时开始；A作业 结束后，D和E作业开始；D作业结束后，H作业开始； B 作业结束后，E作业开始；C作业结束后，G作业开始； E 和F作业均结束后，I作业开始；H、I和G作业结束后，项目 结束。,解：第一 步：先做 网络图,1,A 10 B 15,2 3,D 20 E 18 F 8,5 6,H

16、10 I 20,7,23,C 12,4,G 16,OR:SM,OR:SM,网络时间参数计算实例 第二步：计算正向线路所需时间，即每项作业的最早开 始时间ES和最早结束时间EF。（从起点向后推算） 1、最早开始时间：起点ES=0 其他任意一项作业的ES = max（其任何一项紧前作业的 ES+该紧前作业的作业时间）,2,10 10,D 20,5,30,0,A 10,18,E,H 10,1,0,B 15,3,15,F 8,6,28,I 20,7,0 C,24,12,4,12,G 16,OR:SM,10,OR:SM,网络时间参数计算实例 2、最早结束时间：任意一项作业的EF = 该作业的ES+该 作

17、业的作业时间）,10,2,D 30 10 20,5,30,0,A 10,18,E,28,H 10,40,1,0 0,B 15 15,3,15,F 23 8,6,28,I 48 20 28,7,C,12,12,12,G 16,4 正向线路图,25,OR:SM,I,OR:SM,网络时间参数计算实例 第三步：计算反向线路所需时间，即每项作业的最迟开 始时间LS和最迟结束时间LF。（从终点向前推算） 1、最迟结束时间：终点LF = max（终点所有紧前作业的 EF） 其他任意一项作业的LF = min（其任何一项紧后作业的 LF-该紧后作业的作业时间）,2,D 20 38,5,A 10,10,18,E

18、,H 10,0,1,B 15 20,3,28 F 8 28,6,48 20 48,7,26,12,C,32,4,G 16,48,OR:SM,OR:SM,网络时间参数计算实例 2、最迟开始时间：任意一项作业的LS = 该作业的LF-该 作业的作业时间）,2,D 18 20 38,5,A 10,10,10,18,E,38,H 10,1,0 5,B 15 20,3,20,28 F 8 28,6,I 28 20,48 48,7,20,12,C,G,48,16,32,4,32,反向线路图,27,OR:SM,OR:SM,网络时间参数计算实例,ES,EF,作业的时间参数的图表示法,LS,LF,10 18,3

19、0 38,30,40,0 0,10 10 A,10,2,D 20 E 18,5,10,38 H,48,1,B 15,3,F 8,6,I 20,7,C,15,23,12,20,28,G,16,0,12,12,28,20,32,4,32,48,28,OR:SM,OR:SM,网络时间参数计算实例 第四步：计算各作业的松弛时间。 1、作业松弛时间：TF = 该作业的LF-该作业的ES-该作 业的作业时间 2、作业的自由松弛时间：TL = 后续作业的ES-该作业的 EF,作业名,时间参数（天）,称 A B C D E F G H I,t 10 15 12 20 18 8 16 10 20,ES 0 0

20、0 10 10 15 12 30 28,EF 10 15 12 30 28 23 28 40 48,LS 0 5 20 18 10 20 32 38 28,LF 10 20 32 38 28 28 48 48 48,TF 0 5 20 8 0 5 20 8 0,29,OR:SM,ij,OR:SM,网络时间参数计算实例 第五步：求关键路线。 1、关键路线是从开始到结束最长的路线。 2、关键路线上所有作业的松弛时间为0。,A,E,I,3、复杂项目建立线性规划模型求解,Max,f ( x ) , i j,t ij X,约束条件： X 1 j 1 X in 1 X kj ,X ik 0 , k 1,

21、k n,Xij=1或0 Xij=1的作业构成的 路线为关键路线,30,X,ij, 0,OR:SM,),ai 4mi bi b ai 2,6,6,Tk TE,OR:SM,第三节,计划评审技术,一、作业时间估计 工序时间的三种可能估计： 最乐观时间：在最理想的情况下完成工序所需时间a； 最悲观时间：在最不利的情况下完成工序所需时间b； 最可能时间：在正常情况下完成工序所需时间m。 加权平均就是工序时间t,工序时间t 二、计算期望工期,a 4m b 6,，方差 2 （,b a 2 6, 工程期望工期等于关键路线上各道工序的时间之和 。 工期TE ( )，方差 2 ( i ) i i 设规定的工程完工

22、时间为Tk，则完工时间的概率为 ( x) ,31,OR:SM,OR:SM,第三节,计划评审技术,三、PERT应用举例 某项目的作业流程及其时间估计,作业,紧前作业,乐观时间,作业时间估计 悲观时间,可能时间,作业时间 期望 方差,a b c d e f g,- - a,b a c,d a e,f,3 2 1 3 2 7 2,5 4 3 11 10 13 10,4 3 2 4 9 10 6,4 3 2 5 8 10 6,1/9 1/9 1/9 16/9 16/9 1 16/9,若合同规定工期为20，求如期完工的概率；若要求有90%的把握如 期完工，求可接受的合同工期的为多少。,32,OR:SM,

23、OR:SM,第三节 三、PERT应用举例,计划评审技术,4,4,0 0 1,a 4,2,d 5,f 10,e,17 17 5,g 6,23 23 6,b,8, 参数计算,3,4,3,7,c 2,4 9,9, 工程期望工期 TE=23 ，关键工序的方差2 =49/9，则 (x)=-1.29，查表知 P(x)=9.9% P(x)=90% ，查表知 (x)=1.3，则可接受的合同工期为TE+ (x) =26,33,OR:SM,OR:SM,网络计划方法可以告诉我们什么？ 项目的预期完工时间 按规定时间完工的概率及其影响因素 关键作业有哪些？它们在项目执行中是不能耽误的。 非关键作业有哪些？它们活动的余

24、地多大？ 各作业要求的开始和结束时间。 了解影响项目进度的因素，在此基础上进行资源的安排,34,OR:SM,OR:SM,第四节,网络计划优化,一、缩短工程工期 改进工艺和技术装备，压缩关键工序的作业时间 合理组织平行作业、交叉作业 平行作业指两道以上相互独立的工序同时进行 交叉作业指将紧前工序完成的部分任务分期分批地转 入下道工序 利用时差，合理调配资源等途径实现,35,OR:SM,OR:SM,第四节,网络计划优化,二、工期-费用优化 1、工期与成本之间关系 工期的缩短与费用是密切相关的 工程费用最低的完工时间(最低成本日程),费用,直接费用,工程总费用 间接费用,36,极限完 工时间,最优完

25、 工时间,正常完 工时间,时间,OR:SM,OR:SM,第四节,网络计划优化,二、工期-费用优化 寻求最低成本日程的思路：从网络计划的关键工序着手，对增加 直接费用最少的某些关键工序采取措施，缩短其作业时间。 直接 费用,极限完 工时间,正常完 工时间,时间,37,赶单位时间增加的直接费用(费率) ,赶进度极限完工费用 - 正常完工费用 正常完工作业时间 - 极限完工作业时间 OR:SM,OR:SM,第四节,网络计划优化,2、工期-费用优化案例 某工程作业流程及其费用统计资料,作业,紧前作业,作业时间（天） 正常完工 极限完工,作业直接费用（万元） 正常完工 极限完工,费率,A B C D E

26、 F G H,- - - B B E D A,3 5 5 6 5 3 4 5,3 3 4 3 2 3 3 2,8 16 20 20 5 10 9 20,8 19 23 23 8.6 10 11 28,- 1.5 3 1 1.2 - 2 2,38,合计 间接费用,88 2万元/天,OR:SM,OR:SM,第四节,网络计划优化,方案I：各道作业正常完工,a 3,3,2,10,h 5,0 0,1,b 5,5 3 5,d 6 e,11,4,11,g 4,6,15 15,5,c 5,10,5,12,f 3,工程费用=正常完工直接费用+间接费用=88+215=118万元。,39,OR:SM,OR:SM,第

27、四节,网络计划优化,方案2：关键路线d上赶进度,a 3,3,2,8,h 5,0 0,1,b 5,5 3 5,d 4 e,9,4,9,g 4,6,13 13,5,c 5,10,5,10,f 3,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+213=116万元。,40,OR:SM,OR:SM,第四节,网络计划优化,方案3：关键路线b上赶进度,3,6,a 3,2,h 5,0 0,1,b 3,3 3 3,d 4 e,7,4,7,g 4,6,11 11,5,c 5,8,5,8,f 3,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+21.5+211=

28、115万元。,41,OR:SM,OR:SM,第四节,网络计划优化,方案4：关键路线b、e上赶进度,a 3,3,2,8,h 5,0 0,1,b 3,3 3 3,d 3 e,6,4,6,g 4,6,10 10,4,c 5,7,5,7,f 3,工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+21.5+1(1+1.2)+211=115.2万元。,42,OR:SM,2,G,20,OR:SM,时间成本优化的基本原理应 用的补充例1：,步骤：1、E减1天 2、I减2天 3、B、E各减1天 4、K减2天,1,A 1,2,C 10,4,E 6,5,F 5,6,H 8,7,J 10,8,

29、K 6,9,8,B,3,D 8,I,关键路线：A,C,E,F,I,K(48天） 要求：42天内完成，若完成可获1000元奖励,作业 成本斜率 可能缩短 天数,A 0,B 50 1,C 75 1,D 150 2,E 25 3,F 0,G 0,H 150 1,I 50 6,J 150 2,K 150 2,43,OR:SM,OR:SM,缩减结果:有多条关键路线,缩减时间的 作业 E I B E K 合计,缩减天数 1 2 1 1 2 6,成本斜率 （元/天） 25 50 50 25 150,赶工代价 25 100 50 25 300 500,奖励 1000 1000,G 2,1,A 1,2,C 10

30、,4,E 3,5,F 5,6,H 8,7,J 10,8,K 4,9,44,7,B,3,D 8,I 18,OR:SM,OR:SM,例2：要求将工期缩短到17天,解：1、求关键路线 2、改进：,活动 正常时间,赶工时间,成本斜率（元/天）,（1）c少1天，关键路 线长变为19天,a b c d e f,6 10 5 4 9 2,6 8 4 1 7 1, 500 300 700 600 800,（2）e少1天，关键路 线长为18天（为什么 不少2天？） （3）现有两条关键路 线：a、b、f 和 c、d、 e、f。 （4）缩短f 1天（b少 1天500元+e少1天600,还已知：间接成本为每天1000

31、元,元1100元） 3、结果：项目周期17 天。,a,2,b,1,C,6,10,e,5,f 2,6,5,3,d 4,4,9,45,OR:SM,OR:SM,第四节,网络计划优化,三、工期-资源优化 资源平衡准则： 在压缩工程时间及费用的同时，要分别考量每道作业所需资源 的用量与供应能力及时间限制，以便确定每道作业可压缩时间的 限度及其进度安排。 优先保证关键路线上关键作业对资源的需求量。 对非关键作业要资源，利用时差调整非关键作业的开工时间和 完工时间，以达到与关键作业在占用资源的时间上错开，拉平资 源需要量的高峰。 当资源绝对受限制时，在保证不推迟或尽量少推迟工程完工时 间的前提下，全面统筹安

32、排，最大限度地利用资源。,46,OR:SM,3 3,g,0,5,1,0,f,1,e,0,OR:SM,第四节,网络计划优化,每天只有13台设备可用，计划10天完成，试合理安排生产进度,工序 紧前工序 作业时间 每天所需设备数,a - 3 13,b - 1 5,c a 2 8,d a 3 2,e b,c 4 6,f e,d 1 12,g a 5 5,2 a 3 10 c 2 d 5 10 3 b 1 3 4 4 5 5 9 9 所需工作日：313+15 +28 +32 +46 +112 +55=127,47,10天完成，则平均每天所需机器12.7台，现有机器13台，适当安排可以完工 OR:SM,1

33、2,OR:SM,第四节,网络计划优化,三、工期-资源优化 3、制定初始方案 以最早开工时间，安排初始进度如表,工 序,相关 结点,作业 最早 时间 开工 时间,总 时 差,1,2,3,4,工程进度 5 6,7,8,9,10,a b c, ,3 1 2,0 0 3,0 4 0,13 5,13,13,8,8,d,3,3,3,2,2,2,e,4,5,0,6,6,6,6,f,1,9,0,12,g,5,3,2,5,5,5,5,5,48,每天所需人数合计,18 13 13 15 15 13 11 11 6,OR:SM,OR:SM,第四节,网络计划优化,三、工期-资源优化,4、调整开工时间,第一次调整,工

34、序,相关 结点,作业 最早 时间 开工 时间,总 时 差,1,2,3,4,工程进度 5 6,7,8,9,10,a b c, ,3 1 2,0 0 3,0 4 0,13,13,13,5 8,8,d,3,3,3,2,2,2,e,4,5,0,6,6,6,6,f,1,9,0,12,g,5,3,2,5,5,5,5,5,每天所需人数合计,13 13 13 13 15 13 13 11 11 12,非关键作业b延至第4天开工，非关键作业d和g延至第5天开工。,49,OR:SM,OR:SM,第四节,网络计划优化,三、工期-资源优化,4、调整开工时间,第二次调整,工 序,相关 结点,作业 最早 时间 开工 时间,总 时 差,1,2,3,4,工程进度 5 6,7,8,9,10,a b c, ,3 1 2,0 0 3,0 4 0,13,13,13,5 8,8,d,3,3,3,2,2,2,e,4,5,0,6,6,6,6,f,1,9,0,12,g,5,3,2,5,5,5,5,5,每天所需人数合计,13 13 13 13 13 13 13 13 11 12,将非关键作业d延至第6天开工,50,OR:SM,OR:SM,第五节,缓冲时间设置,具体的思路是：削减每道作业的预估时间，不为单道作业设 置安全缓冲时间，而将节省的时间建立一个任务缓冲（某项任 务的总体安全时间）,51,OR:SM,OR:SM,第五节,缓