管理运筹学讲义 第8 章 网络计划

管理运筹学-管理科学方法中国人民大学出版社谢家平编著OM:SM2第8章网络计划Subtitle学习要点了解网络图中作业、结点、路线的概念理解绘制确定性箭线网络图的基本规则结点时间参数的计算及关键路线的确定开工时间、完工时间和时差参数及应用PERT问题的时间估计和完工概率的确定工期压缩、工期-费用优化的思路和方法工期-资源配置的原则和作业计划的安排明白关键路线法中有效监控进度的前提正确理解作业缓冲时间的有效设置方式OM:SM3第一节网络计划概述一、网络计划的发展历程关键路线法(CriticalPathMethod，CPM)计划评审技术(ProgramEvaluationandReviewTechnique，PERT)图示评审技术(GraphicEvaluationandReviewTechnique，GERT)风险评审技术(VentureEvaluationReviewTechnique，VERT)二、网络计划技术的特性网络计划技术只不过是反映和表达项目计划安排的一种方法，是被项目施工技术所决定的，它只能适应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。OM:SM4第二节网络图的绘制一、网络计划的图示形式•工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程在网络图中用箭线“→”表示，前面直接相连工序称紧前工序，直接相连的后继工序为紧后工序。•结点(事项)：相邻工序的分界点一般用圆圈来表示，每个结点编上顺序号，结点既不消耗人力、物力，也不占用时间。•网络图由工序、事项及时间参数所构成的有向图即为网络图。箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络结点表示工序,箭线为工序间相互关系的网络图，称结点式网络OM:SM5第二节网络图的绘制一、网络计划的图示形式1、箭线式网络图21A25B343C55D5Et－作业时间iN－作业名称j2、结点式网络图t－作业时间N－作业名称iNti－作业序号122543355560OM:SM6第二节网络图的绘制二、箭线式网络图的规则•工序表示的规定一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。•不允许出现缺口与回路网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。•虚工序虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。•方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。•编号的规定编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。编号时不允许箭头编号小于箭尾编号。OM:SM7第二节网络图的绘制三、箭线式网络图举例1、先绘制网络草图绘制网络草图的方法是顺推法，即以始结点开始，首先确定由始结点引出的作业，然后根据作业间的逻辑关系，确定每项作业的紧后作业。2、整理网络图布局•审查作业的逻辑关系和虚作业的必要性，去掉多余的虚作业。•然后对网络图布局进行合理安排和整理，突出整齐性和美观性。3、检查结点的编号•参照作业明细表中的逻辑关系，按照基本原则，检查网络图有无错误;•若无错误，对结点进行顺序编号。OM:SM8第二节网络图的绘制三、箭线式网络图举例某工程的工程一览表工序abcdefg紧前工序------aa,cbb,d,e工序时间63445108124536badcegf36445810OM:SM9第三节关键路线法一、结点的时间参数•结点的最早时间tE(j)tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算。)},()({max)(0)1(jititjttEiEE•结点的最迟时间tL(j)指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。从终点开始，从右向左，逆箭线方向逐个计算。)},()({min)()()(jitjtitntntLjLELOM:SM10第三节关键路线法一、结点的时间参数计算结点时间参数124536badcegf548364100366111996611190OM:SM11第三节关键路线法二、作业的时间参数•最早可能开工时间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)在不影响工程如期完工的前提下，作业最迟必须完工的时刻。tLF(i,j)=tLS(i,j)+t(i,j)=tL(j)OM:SM12第三节关键路线法三、时差与关键路线•时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。•总时差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)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。r(i,j)=tE(j)-tE(i)-t(i,j)•总时差为零的工序称为关键工序；关键工序组成关键路线。tEStEFtLStLFtEStEFtLStLFR(i,j)r(i,j)OM:SM13第三节关键路线法三、时差与关键路线路线路线的组成路线长度1①→④→⑥3+10=132①→④→⑤→⑥3+0+8=113①→②→⑤→⑥6+4+8=184①→②→③→⑤→⑥6+0+5+8=195①→③→⑤→⑥4+5+8=17124536badcegf548364100366111996611190OM:SM14第三节关键路线法四、时间参数算例计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键作业，将其连接起来就是关键路线。(,)tij(,)EStij(,)EFtij(,)LStij(,)LFtij(,)Rij(,)rij作业关键作业a6b3c4d4e5f10g800066311a---e-g06210606961111191906276911634101113190021000OM:SM15第四节计划评审技术一、作业时间估计•工序时间的三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。•加权平均就是工序时间t22)664abbmat（，方差工序时间•工程期望工期等于关键路线上各道工序的时间之和。22)6()64(iiiiiiiEabbmaT，方差工期•设规定的工程完工时间为Tk，则完工时间的概率为EkTTx)(二、计算期望工期OM:SM16第四节计划评审技术三、PERT应用举例某项目的作业流程及其时间估计若合同规定工期为20，求如期完工的概率；若要求有90%的把握如期完工，求可接受的合同工期的为多少。作业紧前作业作业时间估计作业时间乐观时间悲观时间可能时间期望方差a-35441/9b-24331/9ca,b13221/9da3114516/9ec,d2109816/9fa71310101ge,f2106616/9OM:SM17第四节计划评审技术三、PERT应用举例1234a3b2c45d8e10f566g0449172323179740•参数计算工程期望工期TE=23，关键工序的方差2=49/9，则(x)=-1.29，查表知P(x)=9.9%P(x)=90%，查表知(x)=1.3，则可接受的合同工期为TE+(x)=26OM:SM18第五节网络计划优化一、缩短工程工期①改进工艺和技术装备，压缩关键工序的作业时间②合理组织平行作业、交叉作业•平行作业指两道以上相互独立的工序同时进行•交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序③利用时差，合理调配资源等途径实现OM:SM19第五节网络计划优化二、工期-费用优化1、工期与成本之间关系工期的缩短与费用是密切相关的工程费用最低的完工时间(最低成本日程)时间费用极限完工时间正常完工时间直接费用间接费用最优完工时间工程总费用OM:SM20第五节网络计划优化二、工期-费用优化寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用最少的某些关键工序采取措施，缩短其作业时间。时间直接费用极限完工时间正常完工时间极限完工作业时间正常完工作业时间正常完工费用赶进度极限完工费用费率费用赶单位时间增加的直接--)(OM:SM21第五节网络计划优化2、工期-费用优化案例某工程作业流程及其费用统计资料作业紧前作业作业时间（天）作业直接费用（万元）费率正常完工极限完工正常完工极限完工A-3388-B-5316191.5C-5420233DB6320231EB5258.61.2FE331010-GD439112HA5220282合计88间接费用2万元/天OM:SM22第五节网络计划优化方案I：各道作业正常完工工程费用=正常完工直接费用+间接费用=88+2×15=118万元。23a5b6d45h4g5e563f0351110150531011121515cOM:SM23第五节网络计划优化方案2：关键路线d上赶进度工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+2×1+2×13=116万元。23a5b4d45h4g5e563f0359101305389101315cOM:SM24第五节网络计划优化方案3：关键路线b上赶进度工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+2×1+2×1.5+2×11=115万元。23a3b4d45h4g5e563f03378110336781115cOM:SM25第五节网络计划优化方案4：关键路线b、e上赶进度工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+2×1+2×1.5+1×(1+1.2)+2×11=115.2万元。23a3b3d45h4g4e563f03367100338671015cOM:SM26第五节网络计划优化三、工期-资源优化1、资源平衡准则在压缩工程时间及费用的同时，要分别考量每道作业所需资源的用量与供应能力及时间限制，以便确定每道作业可压缩时间的限度及其进度安排。优先保证关键路线上关键作业对资源的需求量。对非关键作业要资源，利用时差调整非关键作业的开工时间和完工时间，以达到与关键作业在占用资源的时间上错开，拉平资源需要量的高峰。当资源绝对受限制时，在保证不推迟或尽量少推迟工程完工时间的前提下，全面统筹安排，最大限度地利用资源。OM:SM27第五节网络计划优化三、工期-资源优化2、资源平衡举例每天只有13台设备可供使用，计划10天内完成，试合理安排生产进度。工序abcdefg紧前工序----aab,ce,da作业时间3123415每天所需设备数135826125OM:SM28第五节网络计划优化三、工期-资源优化1233a1bc243d4e10f55g035910109530•所需工作日：3×13+1×5+2×8+3×2+4×6+1×12+5×5=127•10天内完成，则平均每天所需机器12.7台•现有机器13台，适当安排各工序的开工和完工，10天可以完成工程。OM:SM29第五节网络计划优化三、工期-资源优化3、制定初始方案以最早开工时间，安排初始进度如表工序相关结点