第7章 网络计划技术.ppt

第1页,第7章计划评审方法和关键路线法,7.1PERT网络图7.2PERT网络图的计算7.3关键路线和网络计划的优化7.4完成作业的期望时间和在规定时间内实现事件的概率,第2页,计划评审方法(programevalutionandreviewtechique,简写为PERT)和关键路线法(criticalpathmethod,简写为CPM)是网络分析的一个组成部分广泛应用于系统分析和项目管理.,PERT最早应用于美国海军北极星导弹的研究系统.,CPM主要研究大型工程的费用与工期的相互关系.,计划评审方法的优点：,(1)能够直观清晰的反映计划各部门之间的相互联系与制约，便于掌握计划的全盘情况；,(2)反映了某一部门或某一项工作在全局中的地位和影响，便于发现薄弱环节并进行控制、管理；,(3)可利用计算机进行数据推理运算，便于进行整个方案的分析比较.,第3页,7.1PERT网络图,1.基本概念2.建立PERT网络图的准则和注意事项3.PERT网络图的合并与简化,PERT网络图是在一个图上标注表示时间参数的进度计划图，实质上就是有时序的有向赋权图。,第4页,在PERT网络中，从最初事件到最终事件的由各项作业连贯组成的一条路。,1.基本概念,作业：,指任何消耗时间或资源的行动，用箭线表示.,事件：,标志某项作业的开始或结束,用圆圈表示.,(1)事件本身不消耗时间或资源，或相对于作业讲消耗量可以小到户忽略不计.,(2)某一事件的实现，标志着在它前面各项作业(紧前作业)的结束，又标志着在它之后的各项工作(紧后作业)的开始.,路线：,关键路线：,各项作业累计时间最长的路,用双箭线表示.,1,2,作业A,事件为作业A的起点事件；,事件为作业A的终点事件；,作业标记为(i,j),整个PERT网络图开始(结束)的事件称为最初(终)事件；,第5页,2.建立PERT网络图的准则和注意事项,1.任何作业用唯一的箭线表示，其终点事件(箭头事件)的编号必须大于其起点事件(箭尾事件)的编号.,若一项作业需分段进行，它应细分为不同作业，并用相应不同的箭线表示.,2.两个事件之间只能画一条箭线，表示一项作业.,对具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业.,3,5,3,5,4,3.唯一的最初事件和最终事件.,4.不允许出现回路.,3,5,4,第6页,5.各项作业之间的关系及它们在PERT网络图上的表示：,(1)作业a结束后可以开始作业b和c.,a,b,c,(2)作业c在作业a和b都结束后才能开始,a,b,c,(3)作业a和b都结束后可以开始作业c和d,b,c,a,d,(4)作业c在作业a结束后即可进行，但作业d必须在a和b都结束后才能开始.,a,b,c,d,6.PERT网络图的画法一般是从左到右，从上到下，可通过调整布局尽量避免箭线之间的交叉.,第7页,3.PERT网络图的合并与简化,PERT网络图的划分(用途)：,综合网络图、局部网络图和基层网络图,网络图的简化:,把图中的一组作业简化为一个“组合”的作业,网络图的合并:,把若干个局部网络归并成一个网络.,3,5,4,5,2,6,7,5,6,8,9,10,7,4,8,4,5,7,(a),(b),网络a和b的合并,3,5,4,5,2,6,7,6,8,9,10,7,4,4,5,7,8,3,5,7,10,6,(c),(d),网络c的简化,19,12,4,引出交界事件,进入交界事件,5,第8页,例1某项工程由11项作业组成(分别用代码A,B,C,K表示),其中完成时间及相互关系如下表所示,试画出该项目的箭线图.,7.2PERT网络图的计算,画箭线图的步骤,第1步:画出表示项目开始事件的节点.,第2步:找出没有紧前作业的作业,以开始事件的节点为起始节点,分别画出表示这些作业的箭线,如右图所示:,解：,0,0,2,4,6,C,A,B,第9页,第3步:对于有紧前作业的作业,依次找出其紧前作业结束事件的节点,并依此节点为起始节点画出表示该作业的箭线.,为了表示几个紧前作业同时结束事件,在图中引入虚拟作业的概念,这种作业只是表示事件的前后关系,不消耗时间和资源,如下图所示:,0,2,4,6,C,A,B,D,8,E,10,12,F,14,16,G,18,H,20,I,22,24,J,26,28,K,30,第10页,第4步:引入最后节点表示项目结束事件,所有没有后续箭线的节点通过虚拟作业与项目结束节点连接,如下图所示：,第5步：删除虚拟工作，或者对节点进行合并，把对应的虚拟工作去掉，并对节点重新编号，图形进一步简化为下图,0,2,4,6,C,A,B,D,8,E,10,12,F,14,16,G,18,H,20,I,22,24,J,26,28,K,30,32,0,2,4,6,C,A,B,D,E,8,F,10,G,H,14,I,12,J,K,第11页,在箭线图编制过程中迎注意以下几个问题：,(1)在箭线图中,除起点和终点外,其间各项工作都必须前后衔接,不可有中断的缺口.,(2)网络图中,如果有循环现象,将造成逻辑上的错误,致使某项工作永远无起点或终点.,(3)虚拟工作的应用,(4)节点编号一般采用偶数顺序进行，原因是当中间需要添加节点时有预留编号。,虚拟工作除了使工作间的关系表达清晰外,尚用于以下场合：1.表示两个工作可以同时开始，或可以同时并行实施，待两者完成后，再开始另一工作。2.表达整个计划的完成或开始。,为了表达个别工作与其前项工作的关系,可以设计虚拟工作.,第12页,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,20,0,为整个网络的最初事件,14,为整个网络的最终事件,记为tES(i,j),记为tEF(i,j),作业的最早开始时间:,作业的最早结束时间:,它的各项紧前作业最早结束时间中的最大一个值,它的最早开始时间加上该项作业的计划时间,假定,第13页,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,20,完成全部作业的最短周期为,第14页,记为tLF(i,j),它的各项紧后作业最迟开始时间中的最小一个,假定要求全部作业必须在51天内结束，故有,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,20,作业的最迟结束时间:,最迟开始时间tLS(i,j),事件0的最迟实现事件是,第15页,时差,作业的总时差R(i,j),作业的自由时差F(i,j),R(i,j):网络上多于一项作业共同拥有的机动时间,并非为某项作业单独拥有.,F(i,j):指不影响它的各项紧后作业最早开工时间条件下，该项目作业可以推迟的开工的最大时间限度,它是一项作业独自拥有的机动时间.,或,第16页,关键路线,自由时差,第17页,7.3关键路线和网络计划的优化,关键路线的特点：,这条线路上所有作业的总时差为零。,上题中的关键路线为：,(0,4),(4,8),(8,10),(10,14),关键路线的意义：,1.决定全盘计划所需的最少时间.,2.起关键作用，是整个工程的控制环节.,缩短关键路线的持续时间的途径实现：,(1)检查关键路线上各项作业的计划时间是否订的恰当，如果订得过长，可适当缩短；,(2)将关键路线上的作业进一步分细，尽可能安排多共位或平行作业；,(3)抽调非关键路线上的人力、物力支援关键路线上的作业；,(4)有时也通过重新制定工艺流程，也就是用改变网络图结构的办法来达到缩短时间的目的。,第18页,假如例1所列的工程要求在49天完成。为了加快进度，下表列出了例1中可缩短工时的所有工作，表明这些作业计划完成时间，最短完成时间以及比原计划缩短一天的费用。问应如何安排，使额外增加的总费用最小.,例2,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,20,计算步骤,列出所有可能缩短工期的作业,计算缩短单位工时所增加的费用,找出关键路线上缩短单位时间增加费用最小的工作,将该项工作缩短时间的值控制取下列三者的最小值：1.工期要求尚需缩短的时间2.该项作业最多可缩短的时间3.到出现新关键路线时可缩短的时间,计算并累计增加的费用,是否满足工期要求,停,是,否,第20页,解：,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,20,关键路线上的作业B、G、K,作业K,工期要求缩短2天，,作业K缩短最多可缩短4天，,作业(12,14)的自由时差只有1天，,即工期缩短1天将出项新的关键路线，,可调整的时间=min2,4,1,故先将作业K的完成时间缩短至19，,比原计划额外增加费用500元。,工期缩短后的PERT网络图如右下图：,0,2,4,6,11,5,10,4,4,8,15,10,21,35,14,25,12,15,19,缩短一天的费用最少，,第21页,重复前面的步骤，,0,2,4,6,11,5,10,4,4,8,1