网络计划图的绘制.

5.1网络计划图的绘制5.2时间参数计算与关键路线确定5.3网络图的调整及优化第五章网络计划（工程计划问题）1.问题的一般题法：设有一项工程，可分为若干道工序，已知各工序间的先后关系以及各工序所需时间t。问：（1）工程完工期T？（2）工程的关键工序有哪些？（3）若工序时间T具有随机性，则期望完工期TE=?完工期为某天的可能性多大？（4）费用优化和资源平衡。2.解法关键路径法（CPM方法）计划评审法（PERT方法）相同点：不同点：PERT法：注重于对工程安排的评价与审查。CPM方法：注重于时间、成本和资源的优化；均是用网络表示工程项目，以确定关键路线。5.1网络计划图的绘制1.绘图顺序：按工序先后从左至右2.网络图的组成要素：用表示。ij（1）弧（箭线）：表示工序，（2）顶点（结点）：表示相邻工序时间分界点，称为事项，i用表示（3）相邻弧：表示工序的前后衔接关系，称为紧前（或紧后）关系。如iAkjBA是B的紧前工序，B是A的紧后工序。（4）虚工序（虚箭线）：为表示工序前后衔接关系的需要而增加的。用表示。ij3.绘图规则：（1）图中不能有缺口，多重边和回路。123456起点终点（缺口：有几个总开工事项或几个总完工事项）处理方法：在5、6之间加道虚工序（2）网络图中的事项要从左至右统一编号，每道工序的箭尾事项号应小于箭头事项号。12正确21错误（3）尽量避免箭杆交叉。1234567处理方法：先画草图，再整理。12354674.绘图步骤：（1）确定目标（以谁为主）时间资源费用（2）工程任务的分解和分析；分析工程由哪些工序组成并列出全部工序及代号清单。（3）确定各工序之间先后顺序及衔接关系；要确定每道工序开工之前有哪些工序必须先期完成。（4）确定各工序时间。要确定每道工序的完成所需时间。例1（P130例）某工厂进行技术改造的工作表如下：工序代号工序名称紧前工序工作时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C，A20F设备安装D，E4G设备调试F21A(2)3B(3)2C（2.5）4D（6）E（20）5F（4）6G（2）5.2时间参数计算与关键路线确定—CPM方法一、求完工期T（标号从前往后）1.标出各事项的最早开始时间tE(i)i20表示第i个事项最早在第20天才开始。（1）给始点标10（2）给任意事项标jtE(j)（3）终点的tE(n)即为完工期T（最快的完工期）n)(jtE),()(maxjititE=max{以为箭头（终点）的各箭的箭尾+箭长tij}j8510L(3)K(6)25173131=max{25+6,17+3}表示第10项工序最早在第31天开始。之所以取最大，因为在第20天，L工序已完成，但k工序未完成。tE(n)二、求关键路（标号从后往前）1.标出各事项的最迟开始时间tL(i)（1）给终点标号nT（2）给任一事项标号itL(i)tL(i)=min{tL(j)-t(i,j)}i=min{以为箭尾（起点）的各箭的箭头-箭长tij}567K(6)L(3)10484=min{10-6,8-3}表示第5道工序最晚第4天开始。之所以取最小，保证前面最长的工序能完工。2.计算各工序的时差ijR(i,j)=的-tij-的ji表示这道工序的松弛时间。如ijA(3)2125R(i,j)=25-3-21=1表示A工序最晚开工时间在第25天，最早开工时间在第21天，工时为3天，故有1天的松弛量。3.关键工序：工序时差为0的工序（R(i,j)=0）如：ijA(3)222525-3-22=0表示A工序的开工和结束时间不能延后，否则整个工期延后一关键工序。4.关键路：由关键工序组成的由起点到终点的路。例2求例1的关键工序及关键路。132456A（2）B（3）E（20）D（6）F（4）G（2）C（2.5）05.5325.529.531.505.5325.529.531.5关键工序：B-C-E-F-G关键路：（不一定唯一）123456总工期T=31.5（周）注：1.关键工序箭头箭尾均有=反之不成立。说明关键工序最长。2.关键工序之和=完工期T例3（P136）某项课题研究工作分解的作业表如下。根据此表绘制此项科研工作的网络图，计算时间参数，并确定关键路线。工序代号工序紧前工序工序时间A系统提出和研究问题无4B研究选点问题A7C准备调研方案A10D收集资料工作安排B8E挑实地训练工作人员B，C12F准备收集资料用表格C7G实地调查D，E，F5H分析准备调查报告G4I任务结束H0E(12)124536789A(4)B(7)C(10)B’(0)C’(0)D(8)F(7)G(5)H(4)I(0)04141411263135350414263135351414关键工序：A-C-E-G-H-I关键路：124567895.3网络图的调整及优化5.3.1缩短工程工期问题——工期优化所谓工期优化，就是在编制网络计划时，如何加快工程进度，缩短工程的工期。一般可以从以下两个方面进行：（1）压缩关键工序的工序时间：对关键工序增加新设备，采用新工艺，新技术等措施；或对工序时间较长的关键工序采用平行作业或交叉作业等措施，以达到提高工效、缩短关键工序时间的目的。（2）在非关键工序上尽量挖掘潜力：利用非关键工序的时差进行合理调度，抽调人力、物力支援关键工序，缩短关键工序时间。5.3.2工程的时间费用分析—工期-成本优化（费用优化）所谓工期成本优化，就是在编制网络计划中，如何使工程的完成既快又省。一.费用构成1.直接费用：工资、设备、原材料等（直接与完成工序有关的费用）CDA(压缩时间)B(正常完成时间)时间直接费用称为直接（赶工）费用率：ABCD（表示缩短工序一天，工期增加的直接费用）即直接费用率=—平均单位时间的赶工费用赶工时间正常时间正常费用赶工时费用2.间接费用：管理费等（不直接参加生产的费用）间接费用AB称单位时间的间接费用为间接费用率。总费用=直接费用+间接费用工期直接费用间接费用总费用费用t*（最小工期时间）二.求最低成本工期方法：1.求出正常工期和关键工序（用CPM方法）2.比较间接费用率、直接费用率（1）若直接费用率≥间接费用率则正常工期为最低成本工期。（2）若直接费用率有间接费用率的则在关键工序上压缩，先压缩直接费用率最小的方案，并确定该方案可能缩短的时间。Δt=min{α,β}α=min{压缩工序的正常时间-赶工时间}β=min{所有非关键工序的时差}（3）按照工作的新工时，重新计算网络计划的关键路线及关键工序。（4）计算直接费用率。不断重复，直到使总费用上升为止。（直接费用间接费用）注：若压缩引起出现新的关键路线时，若压需同时压（因为不同时压，则工期不能缩短，工期=关键工序上工时之和）例4设某工程有关资料如表：工序紧前工序工序时间直接费用率可压天数A-3--BA731CA443DC562间接费用率为5求最低成本工期。解：（1）求工期及关键工序。1324A（3）C（4）B（7）D（5）0731212730工期：T=12关键工序：A-C-D（2）因为直接费用率不全5，故应在关键工序上压缩先压缩C（直接费用率最小）压一天能节省费用为5-4=1α=3（C的可压天数），β=R24=2故Δt=2压缩方案：C压缩2天，可减少费用（5-4）*2=2此时网络图为：1324A（3）C（2）B（7）D（5）0531010530关键路有两条：A-BA-C-D工期T=10若再各压缩1天则应压缩B、C（同时压）此时的直接费用率将是3+4=75故最低成本工期为10天。注：（1）有时资料未给可压缩时间，但给了正常工作时间及最短工作时间。则压缩时间=正常工作时间-最短工作时间。（2）当网络图中工作很多，关键路线又不止一条，用观察法来确定缩短工时所需直接费用增加最少的方案比较困难，这时可以使用求网络最大流的标号法来解决。方法：将问题化为：在全部以关键工序组成的网络上，每边容量使用本工作的直接费用率（若本工作已不能缩短工时，容量应标）求网络的最大流，当求出最大流时所得到的最小割，就是增加直接费用最少的方案。1243)0,()0,3()0,6()0,4(],[1v],[1v],3[2v1243)3,()3,3()0,6()0,4(],[1v],[1v],4[2v],4[3v)4,6(1243)7,()3,3()4,4(],[1v],[1v工作组合（2，4）（2，3）为费用最低方案。BC三.求规定工期的最小成本方案间接费用是确定了的，无需考虑，只需考虑直接费用尽量小。方法：1.求出正常工期和关键路线2.在关键工序上压，先压缩直接费用率最小的，压缩天数也应为Δt=min{α,β}.当出现多于一条的关键路线时要同时压，直到满足规定为止。例5建筑公司要装水管线的工程，有关资料：工作紧前工作正常情况应急情况时间（天）费用（元）时间（天）费用（元）a-11.7240--ba3.2752110ca25.24500157200da18.048017600ed9.05408710fb,c7.7166051800ge,f16.84000145700hg7.2160051775ie,f12.850091298（1）按正常情况，画出施工网络图，找出关键路，求完工期。（2）现提出这项工程要60天完成，求使总应急费用最小的方案。18246735a(11.7)b(3.2)c(25.2)d(18.0)b’(0)f(7.7)e(9.0)g(16.8)h(7.2)i(12.8)011.729.714.936.944.661.468.668.661.444.635.636.936.911.70正常工期TE=68.6天关键工序a-c-f-g-h解：（1）（2）将每道工序的直接费用率计算如下：工作abcdefghi可压工期—1.210.2112.72.82.23.8直接费用率—29.17264.7112017044.4607.1479.55367.891）先压f,α=2.7;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故β=3.2。因此,Δt=2.718246735a(11.7)b(3.2)c(25.2)d(18.0)b’(0)f(5.0)e(9.0)g(16.8)h(7.2)i(12.8)011.729.714.936.941.958.765.965.958.741.932.936.936.911.70工期TE=65.9关键工序：a-c-f-g-h2）再压h,α=2.2;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故β=3.2.因此，Δt=2.218246735a(11.7)b(3.2)c(25.2)d(18.0)b’(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.936.941.958.763.763.758.741.932.936.936.911.70工期TE=63.7关键工序：a-c-f-g-h3）再压c,α=3.7;而Rb=22,Rd=3.2,Re=3.2,Ri=9.0故β=3.2.因此，Δt=3.218246735a(11.7)b(3.2)c(22)d(18.0)b’(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.933.738.755.560.560.555.538.729.733.733.711.70工期TE=60.560关键工序：a-d-e-g-ha-c-f-g-h4）可同时压c,e各0.5天,α=0.5;而Rb=18.8,Rc=3.0故β=3.0.因此，Δt=0.518246735a(11.7)b(3.2)c(21.5)d(18.0)b’(0)f(5.0)e(8.5)g(16.8)h(5.0)i(12.8)011.729.714.933.238.255.0606055.038.229.733.233.211.70工期TE=60关键工序：1）a-c-f-g-h2）a-d-e-g-h所以，工期