网络图绘制与关键路径.ppt

《网络图绘制与关键路径.ppt》由会员分享，可在线阅读，更多相关《网络图绘制与关键路径.ppt（38页珍藏版）》请在三一办公上搜索。

1、1,甘特图例子,2,甘特图优缺点,优点：每项活动时间定位非常准确；图形简单、清晰；缺点：活动之间关系不够清晰；活动的重要度不够明确；对大型复杂项目，甘特图显得不太适用,3,单代号网络图法,单代号网络图法（PDM,Precedence Diagramming Method、节点法、顺序图法）大多数项目管理软件所采用,软件项目中PDM更通用,4,活动之间的逻辑关系,A结束后B才开始（FS）一种活动结束后，另一种活动才能开始这是应用最普遍的一种关系例如：软件的分析，设计，编码活动,B开始前A必须开始（SS）后续活动不需要等待前导活动结束后才开始 这经常表示某种并行，但具有一定依赖关系的活动例如：软件

2、的测试活动，往往依赖开发活动的结果，但又独立于开发活动,5,活动之间的逻辑关系,A结束前B必须结束（FF）例如：热水器安装（B）厨房粉刷（A）,A开始后B才结束（SF）这是一种最特殊的活动逻辑先后关系，即后续活动的结束依赖于前导活动的开始 日常的生活中，例如：找到新的工作后，才可能放弃原来的工作；许多人再找到新爱后才会放弃旧爱,6,单代号网络计划图的绘制与计算,一、单代号网络计划图的构成.节点：用圆圈或方框表示，一个节点表示一项具体的工作。.箭线：只表示工作之间的相互关系。箭线的箭头方向表示工作的前进方向。.代号：一项工作只能有一个代号。箭头节点的号码应大于箭尾节点的号码。,7,单代号网络图法

3、特点,1）单代号搭接网络图必须正确表述已定的逻辑关系。2)单代号搭接网络图中，严禁出现循环回路。3)单代号搭接网络图中，严禁出现双向箭头或无箭头的连线。4)单代号搭接网络图中，严禁出现没有箭尾节点的箭线和没有箭头节点的箭线。5)绘制网络图时，箭线不宜交叉。6)单代号搭接网络图只应有一个起点节点和一个终点节点。当网络图中有多项起点节点或多项终点节点时，应在网络图的两端分别设置一项虚工作，作为该网络图的起点节点(St)和终点节点(Fin),8,单代号网络图法特点,1)工作之间的逻辑关系容易表达，绘图较简单；2)网络图便于检查和修改；3)由于工作持续时间表示在节点之中，没有长度，故不够形象直观；4)

4、表示工作之间逻辑关系的箭线可能产生较多的纵横交叉现象。,9,例：绘制如下表工作关系的单代号网络计划图,始,B,F,I,H,G,E,C,A,D,终,10,双代号网络图法,箭线式网络图(Arrow Diagramming Method)以箭线表示活动，每个活动都由两个数字来定义。节点代表关系虚活动我国应用比较多，国内采用该方法的软件较多,11,双代号网络图图例,12,如何编制进度计划,0 建立企业和项目资源库1 设置项目日历、资源日历2 设置项目的主要里程碑点3 在WBS下列出工作清单（Task，Activity）4 估计每个Task的工期5 计算每个Task之间的逻辑关系6 加载完成每个Task

5、所需要的资源和资源数量7 进度计算后，看开工/完工里程碑是否符合合同或业主要求，看资源负荷是否过大？8 需要调整吗？9 调整的方法：压缩关键路径上Task的工期：多投入资源以缩短工期，分解工期较长的作业10 合适了吗？合适了，则把第一份计划保存为目标计划（Baseline）11 公布第一版计划，通知项目干系人,13,关键路线：CPM从项目开始到结束占用时间最长的路线工作总时差为零的工作，也就是其开始时间或结束时间没有任何机动余地的工作。项目的总工期是由关键路线的工作总时间决定的 CPM上任一节点若不按期完成，则整个计划的完工 若要缩短项目的计划完工期限，应当设法缩短某个或某些关键工作的作业时间

6、 某个项目关键路线可能不止一条,14,正推法(Forward pass),按照时间顺序计算最早开始时间和最早完成时间的方法,称为正推法.首先建立项目的开始时间项目的开始时间是网络图中第一个活动的最早开始时间从左到右，从上到下进行任务编排当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期公式:ES+Duration=EF,15,正推法实例,Start,LF,LS,EF,ES,Duration=7Task A,1,8,LF,LS,EF,ES,Duration=3Task B,1,4,LF,LS,EF,ES,Duration=6Task C,8,14,LF,LS,EF,E

7、S,Duration=3Task D,4,7,LF,LS,EF,ES,Duration=3Task G,14,17,LF,LS,EF,ES,Duration=3Task E,7,10,LF,LS,EF,ES,Duration=2Task H,17,19,LF,LS,EF,ES,Duration=2Task F,4,6,Finish,当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期,16,逆推法(Backward pass),按照逆时间顺序计算最晚开始时间和最晚结束时间的方法,称为逆推法.首先建立项目的结束时间项目的结束时间是网络图中最后一个活动的最晚结束时间从右到

8、左，从上到下进行计算当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期公式:LF-Duration=LS,17,逆推图示,Start,LF,LS,EF,ES,Duration=7Task A,1,8,1,8,LF,LS,EF,ES,Duration=3Task B,1,4,8,11,LF,LS,EF,ES,Duration=6Task C,8,14,8,14,LF,LS,EF,ES,Duration=3Task D,4,7,11,14,LF,LS,EF,ES,Duration=3Task G,14,17,14,17,LF,LS,EF,ES,Duration=3

9、Task E,7,10,14,17,LF,LS,EF,ES,Duration=2Task H,17,19,17,19,LF,LS,EF,ES,Duration=2Task F,4,6,12,14,Finish,当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期,CP:A-C-G-H,Cp Path:18,18,课堂练习,作为项目经理，你需要给一个软件项目做计划安排，经过任务分解后得到任务A，B，C，D，E，F，G，假设各个任务之间没有滞后和超前，下图是这个项目的PDM网络图。通过历时估计已经估算出每个任务的工期，现已标识在PDM网络图上。假设项目的最早开工日期

10、是第天，请计算每个任务的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间，同时确定关键路径，并计算关键路径的长度.,19,课堂练习,确定以及的长度？,20,课堂练习-答案,4,4,10,4,12,12,19,19,24,12,20,24,27,27,24,24,24,16,19,19,12,12,6,12,4,4,0,CP:A-E-C-D-G,CP Path:27,21,1、边表示活动的网(Activity On Edge Network，简称为AOE网)为带权有向无环图，其中：顶点表示事件，边表示活动，边的权值表示活动持续的时间。,其中：AOE网中顶点表示的事件实际上体现了一种状态，即

11、该顶点的所有入边表示的活动均已完成，出边表示的活动可以开始。,关键路径程序实现,一、基本概念,22,2、源点、汇点：表示实际工程的AOE网应该只有一个入度为0的顶点和一个出度为0的顶点，前者称作为源点，后者称作为汇点。,研究的问题：对于表示工程计划的AOE网，需要研究的问题是：,完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？,23,3、关键路径：由于AOE网中的若干活动是可以并行进行的，所以完成工程的最短时间是从源点到汇点的最长路径的长度，即最长路径上各边权值之和。从源点到汇点的最长路径称为关键路径。,24,事件vj可能的最早发生时间ve(j)应为从源点到顶点vj 的 最长路径长

12、度 弧表示的活动ai的最早开始时间e(i)等于ve(j)。在不推迟整个工程完成的前提下，事件vk允许的最迟发生 时间vl(k)应等于汇点vn的最迟发生时间vl(n)减去 vk到vn的最长路径长度。弧表示的活动ai的最迟开始时间l(i)等于vl(k)减去弧的权值。,4、ve(j)、e(i)、vl(k)、l(i),25,ve(5)=11,vl(2)=11-8=3e(1)=0l(1)=vl(2)-3=0,26,5、关键活动：对活动ai而言，l(i)-e(i)为其在不延误整个工程工期情况下，可以延迟的时间。若e(i)=l(i)则称活动ai为关键活动。,关键路径上的所有活动都是关键活动。缩短或延误关键活

13、动的持续时间将提前或推迟整个工程的完工时间。,27,二、如何求AOE网的关键活动,1、分析：由关键活动的定义可知，只要求出了某个活动的e(i)和l(i)，便可判断该活动是否为关键活动。而为了求AOE网中活动的e(i)和l(i)，首先需求网中所有事件的ve(j)和vl(j)。,e(i)=ve(j)l(i)=vl(k)-dut(),因为：若活动ai由表示，其权值记为dut()，则有如下关系：,28,求ve(j)和vl(j)需分两步进行：,(1)从ve(1)=0开始向前递推 ve(j)=maxve(i)+dut()属于以vj为头的弧的集合，2=j=n,ve(1)=0ve(2)=3ve(3)=maxv

14、e(1)+2,ve(2)+2=5ve(4)=maxve(1)+1,ve(3)+3=8ve(5)=maxve(2)+8,ve(4)+3=11,29,(2)从vl(n)=ve(n)开始向后递推 vl(i)=minvl(j)-dut()属于以vi为尾的弧的集合，1=i=n-1,vl(5)=11vl(4)=vl(5)-3=8vl(3)=vl(4)-3=5vl(2)=minvl(3)-2,vl(5)-8=3vl(1)=minvl(2)-3,vl(3)-2,vl(4)-1=0,30,e(i)=ve(j)l(i)=vl(k)-dut(),31,2、求关键活动的算法：,(1)对AOE网进行拓扑排序，并按排序的

15、次序求各顶点事件的ve值,若网有回路，则算法终止，否则执行步骤(2);(2)按拓扑排序的逆序求各顶点事件的vl值;(3)根据各顶点事件的ve值和vl值，求各活动ai的e(i)和l(i)。若e(i)=l(i)，则ai为关键活动。,32,3、算法描述：Stack TopologicalOrder(ALGraph G,Stack T)int i,j,k,count;Stack S;ArcNode*p;FindInDegree(G,indegree);InitStack(,33,int CriticalPath(ALGraph G)Stack T;int i,j,k,dut,ee,el;ArcNode

16、*p;int vln;T=TopologicalOrder(G,T);for(i=0;inextrc)k=p-adjvex;dut=p-info;if(vlk-dutnextrc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf();,34,双代号时标网络计划,双代号时标网络计划的概念双代号时标网络计划的时间参数计算,35,双代号时标网络计划的概念,1.基本符号：实箭线：水平投影长度表示工作的持续时间 虚箭线：虚工作 波形线：工作自由时差,36,双代号时标网络计划的概念,2.绘制规则按最早时间绘制；各工作的时间参数由其在时标表上的水平位置表示；各工作持续时间由其水平投影长度表示；自由时差由波形线表示。,37,时标网络计划的时间参数计算,1.关键路线：没有波形线的路线2.时间参数的确定计算工期工作最早时间工作最迟时间工作总时差工作自由时差,38,1、请绘制网络图、确定关键路线；绘制各工序在最早时间开始时标网络图,综合作业,