第2章 网络图绘制与关键路径

1甘特图例子2甘特图优缺点优点：每项活动时间定位非常准确；图形简单、清晰；缺点：活动之间关系不够清晰；活动的重要度不够明确；对大型复杂项目，甘特图显得不太适用3单代号网络图法单代号网络图法（PDM,PrecedenceDiagrammingMethod、节点法、顺序图法）大多数项目管理软件所采用,软件项目中PDM更通用4活动之间的逻辑关系A结束后B才开始（FS）一种活动结束后，另一种活动才能开始这是应用最普遍的一种关系例如：软件的分析，设计，编码活动ABB开始前A必须开始（SS）后续活动不需要等待前导活动结束后才开始这经常表示某种并行，但具有一定依赖关系的活动例如：软件的测试活动，往往依赖开发活动的结果，但又独立于开发活动AB5活动之间的逻辑关系A结束前B必须结束（FF）例如：热水器安装（B）厨房粉刷（A）A开始后B才结束（SF）这是一种最特殊的活动逻辑先后关系，即后续活动的结束依赖于前导活动的开始日常的生活中，例如：找到新的工作后，才可能放弃原来的工作；许多人再找到新爱后才会放弃旧爱ABAB67单代号网络图法特点1）单代号搭接网络图必须正确表述已定的逻辑关系。2)单代号搭接网络图中，严禁出现循环回路。3)单代号搭接网络图中，严禁出现双向箭头或无箭头的连线。4)单代号搭接网络图中，严禁出现没有箭尾节点的箭线和没有箭头节点的箭线。5)绘制网络图时，箭线不宜交叉。6)单代号搭接网络图只应有一个起点节点和一个终点节点。当网络图中有多项起点节点或多项终点节点时，应在网络图的两端分别设置一项虚工作，作为该网络图的起点节点(St)和终点节点(Fin)8单代号网络图法特点1)工作之间的逻辑关系容易表达，绘图较简单；2)网络图便于检查和修改；3)由于工作持续时间表示在节点之中，没有长度，故不够形象直观；4)表示工作之间逻辑关系的箭线可能产生较多的纵横交叉现象。910双代号网络图法箭线式网络图(ArrowDiagrammingMethod)以箭线表示活动，每个活动都由两个数字来定义。节点代表关系虚活动我国应用比较多，国内采用该方法的软件较多A45312CBD11双代号网络图图例总体设计需求确认需求获取系统测试集成测试编码详细设计计划评审项目规划12369875412如何编制进度计划0建立企业和项目资源库1设置项目日历、资源日历2设置项目的主要里程碑点3在WBS下列出工作清单（Task，Activity）4估计每个Task的工期5计算每个Task之间的逻辑关系6加载完成每个Task所需要的资源和资源数量7进度计算后，看开工/完工里程碑是否符合合同或业主要求，看资源负荷是否过大？8需要调整吗？9调整的方法：压缩关键路径上Task的工期：多投入资源以缩短工期，分解工期较长的作业10合适了吗？合适了，则把第一份计划保存为目标计划（Baseline）11公布第一版计划，通知项目干系人13关键路线：CPM从项目开始到结束占用时间最长的路线工作总时差为零的工作，也就是其开始时间或结束时间没有任何机动余地的工作。项目的总工期是由关键路线的工作总时间决定的CPM上任一节点若不按期完成，则整个计划的完工若要缩短项目的计划完工期限，应当设法缩短某个或某些关键工作的作业时间某个项目关键路线可能不止一条14正推法(Forwardpass)按照时间顺序计算最早开始时间和最早完成时间的方法,称为正推法.首先建立项目的开始时间项目的开始时间是网络图中第一个活动的最早开始时间从左到右，从上到下进行任务编排当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期公式:ES+Duration=EF15正推法实例StartLFLSEFESDuration=7TaskA18LFLSEFESDuration=3TaskB14LFLSEFESDuration=6TaskC814LFLSEFESDuration=3TaskD47LFLSEFESDuration=3TaskG1417LFLSEFESDuration=3TaskE710LFLSEFESDuration=2TaskH1719LFLSEFESDuration=2TaskF46Finish当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期16逆推法(Backwardpass)按照逆时间顺序计算最晚开始时间和最晚结束时间的方法,称为逆推法.首先建立项目的结束时间项目的结束时间是网络图中最后一个活动的最晚结束时间从右到左，从上到下进行计算当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期公式:LF-Duration=LS17逆推图示StartLFLSEFESDuration=7TaskA1818LFLSEFESDuration=3TaskB14811LFLSEFESDuration=6TaskC814814LFLSEFESDuration=3TaskD471114LFLSEFESDuration=3TaskG14171417LFLSEFESDuration=3TaskE7101417LFLSEFESDuration=2TaskH17191719LFLSEFESDuration=2TaskF461214Finish当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期CP:A-C-G-HCpPath:1818课堂练习作为项目经理，你需要给一个软件项目做计划安排，经过任务分解后得到任务A，B，C，D，E，F，G，假设各个任务之间没有滞后和超前，下图是这个项目的PDM网络图。通过历时估计已经估算出每个任务的工期，现已标识在PDM网络图上。假设项目的最早开工日期是第０天，请计算每个任务的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间，同时确定关键路径，并计算关键路径的长度.19课堂练习LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF确定ＣＰ以及ＣＰ的长度？20课堂练习-答案LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF44104121219192412202427272424241619191212612440CP:A-E-C-D-GCPPath:27211、边表示活动的网(ActivityOnEdgeNetwork，简称为AOE网)为带权有向无环图，其中：顶点表示事件，边表示活动，边的权值表示活动持续的时间。•其中：AOE网中顶点表示的事件实际上体现了一种状态，即该顶点的所有入边表示的活动均已完成，出边表示的活动可以开始。v1v2v3v4v53813223一个AOE网a1a2a3a4a5a6a7关键路径程序实现一、基本概念222、源点、汇点：表示实际工程的AOE网应该只有一个入度为0的顶点和一个出度为0的顶点，前者称作为源点，后者称作为汇点。•研究的问题：对于表示工程计划的AOE网，需要研究的问题是：完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？23v1v2v3v4v53813223a1a2a3a4a5a6a73、关键路径：由于AOE网中的若干活动是可以并行进行的，所以完成工程的最短时间是从源点到汇点的最长路径的长度，即最长路径上各边权值之和。从源点到汇点的最长路径称为关键路径。AOE网中的关键路径可能不止一条。24•事件vj可能的最早发生时间ve(j)应为从源点到顶点vj的最长路径长度•弧vj,vk表示的活动ai的最早开始时间e(i)等于ve(j)。•在不推迟整个工程完成的前提下，事件vk允许的最迟发生时间vl(k)应等于汇点vn的最迟发生时间vl(n)减去vk到vn的最长路径长度。•弧vj,vk表示的活动ai的最迟开始时间l(i)等于vl(k)减去弧vj,vk的权值。4、ve(j)、e(i)、vl(k)、l(i)25v1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,vl(2)=11-8=3e(1)=0l(1)=vl(2)-3=0265、关键活动：对活动ai而言，l(i)-e(i)为其在不延误整个工程工期情况下，可以延迟的时间。若e(i)=l(i)则称活动ai为关键活动。关键路径上的所有活动都是关键活动。缩短或延误关键活动的持续时间将提前或推迟整个工程的完工时间。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(j,k)因为：若活动ai由vj,vk表示，其权值记为dut(j,k)，则有如下关系：28求ve(j)和vl(j)需分两步进行：(1)从ve(1)=0开始向前递推ve(j)=max{ve(i)+dut(vi,vj)}vi,vj属于以vj为头的弧的集合，2=j=nv1v2v3v4v53813223a1a2a3a4a5a6a7ve(1)=0ve(2)=3ve(3)=max{ve(1)+2,ve(2)+2}=5ve(4)=max{ve(1)+1,ve(3)+3}=8ve(5)=max{ve(2)+8,ve(4)+3}=11AOE网中计算事件的ve(j)是按顶点的某一拓扑序列的次序进行的。29(2)从vl(n)=ve(n)开始向后递推vl(i)=min{vl(j)-dut(vi,vj)}vi,vj属于以vi为尾的弧的集合，1=i=n-1v1v2v3v4v53813223a1a2a3a4a5a6a7vl(5)=11vl(4)=vl(5)-3=8vl(3)=vl(4)-3=5vl(2)=min{vl(3)-2,vl(5)-8}=3vl(1)=min{vl(2)-3,vl(3)-2,vl(4)-1}=0AOE网中计算事件的vl(i)是按顶点的某一拓扑序列的逆序进行的。30e(i)=ve(j)l(i)=vl(k)-dut(j,k)vl(5)=11vl(4)=8vl(3)=5vl(2)=3vl(1)=0ve(1)=0ve(2)=3ve(3)=5ve(4)=8ve(5)=11活动a1a2a3a4a5a6a7e0003538l0733538l-e0730000v1v2v3v4v53813223a1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a7312、求关键活动的算法：(1)对AOE网进行拓扑排序，并按排序的次序求各顶点事件的ve值,若网有回路，则算法终止，否则执行步骤(2);(2)按拓扑排序的逆序求各顶点事件的vl值;(3)根据各顶点事件的ve值和vl值，求各活动ai的e(i)和l(i)。若e(i)=l(i)，则ai为关键活动。323、算法描述：StackTopologicalOrder(ALGraphG,StackT){inti,j,k,count;StackS;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);InitStack(&T);for(i=0;iG.vexnum;i++){if(!indegree[i])Push(&S,i);}count=0;for(i=0;iG.v