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

甘特图例子1精选ppt甘特图优缺点优点：每项活动时间定位非常准确；图形简单、清晰；缺点：活动之间关系不够清晰；活动的重要度不够明确；对大型复杂工程，甘特图显得不太适用2精选ppt单代号网络图法单代号网络图法〔PDM,PrecedenceDiagrammingMethod、节点法、顺序图法〕大多数工程管理软件所采用,软件工程中PDM更通用3精选ppt活动之间的逻辑关系A结束后B才开始〔FS〕一种活动结束后，另一种活动才能开始这是应用最普遍的一种关系例如：软件的分析，设计，编码活动ABB开始前A必须开始〔SS〕后续活动不需要等待前导活动结束后才开始这经常表示某种并行，但具有一定依赖关系的活动例如：软件的测试活动，往往依赖开发活动的结果，但又独立于开发活动AB4精选ppt活动之间的逻辑关系A结束前B必须结束〔FF〕例如：热水器安装〔B〕厨房粉刷〔A〕A开始后B才结束〔SF〕这是一种最特殊的活动逻辑先后关系，即后续活动的结束依赖于前导活动的开始日常的生活中，例如：找到新的工作后，才可能放弃原来的工作；许多人再找到新爱后才会放弃旧爱ABAB5精选ppt单代号网络方案图的绘制与计算一、单代号网络方案图的构成１.节点：用圆圈或方框表示，一个节点表示一项具体的工作。２.箭线：只表示工作之间的相互关系。箭线的箭头方向表示工作的前进方向。３.代号：一项工作只能有一个代号。箭头节点的号码应大于箭尾节点的号码。NO：n工作名称持续时间123ESLSEFLF6精选ppt单代号网络图法特点1〕单代号搭接网络图必须正确表述已定的逻辑关系。2)单代号搭接网络图中，严禁出现循环回路。3)单代号搭接网络图中，严禁出现双向箭头或无箭头的连线。4)单代号搭接网络图中，严禁出现没有箭尾节点的箭线和没有箭头节点的箭线。5)绘制网络图时，箭线不宜交叉。6)单代号搭接网络图只应有一个起点节点和一个终点节点。当网络图中有多项起点节点或多项终点节点时，应在网络图的两端分别设置一项虚工作，作为该网络图的起点节点(St)和终点节点(Fin)7精选ppt单代号网络图法特点1)工作之间的逻辑关系容易表达，绘图较简单；2)网络图便于检查和修改；3)由于工作持续时间表示在节点之中，没有长度，故不够形象直观；4)表示工作之间逻辑关系的箭线可能产生较多的纵横交叉现象。8精选ppt例：绘制如下表工作关系的单代号网络方案图工序ABCDEFGHI紧后工作CDEFEFGHHI---始BFIHGECAD终9精选ppt双代号网络图法箭线式网络图(ArrowDiagrammingMethod) 以箭线表示活动，每个活动都由两个数字来定义。节点代表关系虚活动我国应用比较多，国内采用该方法的软件较多A45312CBD10精选ppt双代号网络图图例总体设计需求确认需求获取系统测试集成测试编码详细设计计划评审项目规划12369875411精选ppt如何编制进度方案0建立企业和工程资源库1设置工程日历、资源日历2设置工程的主要里程碑点3在WBS以下出工作清单〔Task，Activity〕4估计每个Task的工期5计算每个Task之间的逻辑关系6加载完成每个Task所需要的资源和资源数量7进度计算后，看开工/完工里程碑是否符合合同或业主要求，看资源负荷是否过大？8需要调整吗？9调整的方法：压缩关键路径上Task的工期：多投入资源以缩短工期，分解工期较长的作业10适宜了吗？适宜了，那么把第一份方案保存为目标方案〔Baseline〕11公布第一版方案，通知工程干系人12精选ppt关键路线：CPM从工程开始到结束占用时间最长的路线工作总时差为零的工作，也就是其开始时间或结束时间没有任何机动余地的工作。工程的总工期是由关键路线的工作总时间决定的CPM上任一节点假设不按期完成，那么整个方案的完工假设要缩短工程的方案完工期限，应当设法缩短某个或某些关键工作的作业时间某个工程关键路线可能不止一条13精选ppt正推法(Forwardpass)按照时间顺序计算最早开始时间和最早完成时间的方法,称为正推法.首先建立工程的开始时间工程的开始时间是网络图中第一个活动的最早开始时间从左到右，从上到下进行任务编排当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期公式:ES+Duration=EF14精选ppt正推法实例StartLFLSEFESDuration=7TaskA18LFLSEFESDuration=3TaskB14LFLSEFESDuration=6TaskC814LFLSEFESDuration=3TaskD47LFLSEFESDuration=3TaskG1417LFLSEFESDuration=3TaskE710LFLSEFESDuration=2TaskH1719LFLSEFESDuration=2TaskF46Finish当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期15精选ppt逆推法(Backwardpass)按照逆时间顺序计算最晚开始时间和最晚结束时间的方法,称为逆推法.首先建立工程的结束时间工程的结束时间是网络图中最后一个活动的最晚结束时间从右到左，从上到下进行计算当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期公式:LF-Duration=LS16精选ppt逆推图示StartLFLSEFESDuration=7TaskA1818LFLSEFESDuration=3TaskB14811LFLSEFESDuration=6TaskC814814LFLSEFESDuration=3TaskD471114LFLSEFESDuration=3TaskG14171417LFLSEFESDuration=3TaskE7101417LFLSEFESDuration=2TaskH17191719LFLSEFESDuration=2TaskF461214Finish当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期CP:A->C->G->HCpPath:1817精选ppt课堂练习作为工程经理，你需要给一个软件工程做方案安排，经过任务分解后得到任务A，B，C，D，E，F，G，假设各个任务之间没有滞后和超前，以下图是这个工程的PDM网络图。通过历时估计已经估算出每个任务的工期，现已标识在PDM网络图上。假设工程的最早开工日期是第０天，请计算每个任务的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间，同时确定关键路径，并计算关键路径的长度.18精选ppt课堂练习LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF确定ＣＰ以及ＣＰ的长度？19精选ppt课堂练习-答案LFLSEFESDuration=3TaskGLFLSEFESDuration=4TaskA0LFLSEFESDuration=6TaskBLFLSEFESDuration=7TaskCLFLSEFESDuration=5TaskDLFLSEFESDuration=8TaskELFLSEFESDuration=8TaskF44104121219192412202427272424241619191212612440CP:A->E->C->D->GCPPath:2720精选ppt1、边表示活动的网(ActivityOnEdgeNetwork，简称为AOE网)为带权有向无环图，其中：顶点表示事件，边表示活动，边的权值表示活动持续的时间。其中：AOE网中顶点表示的事件实际上表达了一种状态，即该顶点的所有入边表示的活动均已完成，出边表示的活动可以开始。v1v2v3v4v53813223一个AOE网a1a2a3a4a5a6a7关键路径程序实现一、根本概念21精选ppt2、源点、汇点：表示实际工程的AOE网应该只有一个入度为0的顶点和一个出度为0的顶点，前者称作为源点，后者称作为汇点。研究的问题：对于表示工程方案的AOE网，需要研究的问题是：完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？22精选pptv1v2v3v4v53813223a1a2a3a4a5a6a73、关键路径：由于AOE网中的假设干活动是可以并行进行的，所以完成工程的最短时间是从源点到汇点的最长路径的长度，即最长路径上各边权值之和。从源点到汇点的最长路径称为关键路径。AOE网中的关键路径可能不止一条。23精选ppt

事件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)24精选pptv1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,

vl(2)=11-8=3

e(1)=0

l(1)=vl(2)-3=0

25精选ppt5、关键活动：对活动ai而言，l(i)-e(i)为其在不延误整个工程工期情况下，可以延迟的时间。假设e(i)=l(i)那么称活动ai为关键活动。关键路径上的所有活动都是关键活动。缩短或延误关键活动的持续时间将提前或推迟整个工程的完工时间。26精选ppt二、如何求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>)，那么有如下关系：27精选ppt求ve(j)和vl(j)需分两步进行：(1)从ve(1)=0开始向前递推

ve(j)=max{ve(i)+dut(<vi,vj>)}

<vi,vj>属于以vj为头的弧的集合，2<=j<=nv1v2v3v4v53813223a1a2a3a4a5a6a7ve(1)=0

ve(2)=3

ve(3)=max{ve(1)+2,ve(2)+2}=5

ve(4)=max{ve(1)+1,ve(3)+3}=8

ve(5)=max{ve(2)+8,ve(4)+3}=11AOE网中计算事件的ve(j)是按顶点的某一拓扑序列的次序进行的。28精选ppt(2)从vl(n)=ve(n)开始向后递推

vl(i)=min{vl(j)-dut(<vi,vj>)}

<vi,vj>属于以vi为尾的弧的集合，1<=i<=n-1v1v2v3v4v53813223a1a2a3a4a5a6a7vl(5)=11

vl(4)=vl(5)-3=8

vl(3)=vl(4)-3=5

vl(2)=min{vl(3)-2,vl(5)-8}=3

vl(1)=min{vl(2)-3,vl(3)-2,vl(4)-1}=0AOE网中计算事件的vl(i)是按顶点的某一拓扑序列的逆序进行的。29精选ppte(i)=ve(j)l(i)=vl(k)-dut(<j,k>)vl(5)=11

vl(4)=8

vl(3)=5

vl(2)=3

vl(1)=0ve(1)=0

ve(2)=3

ve(3)=5

ve(4)=8

ve(5)=11活动a1a2a3a4a5a6a7e0003538l0733538l-e0730

0

0

0v1v2v3v4v53813223a1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a730精选ppt2、求关键活动的算法：(1)对AOE网进行拓扑排序，并按排序的次序求各顶点事件的ve值,假设网有回路，那么算法终止，否那么执行步骤(2);(2)按拓扑排序的逆序求各顶点事件的vl值;(3)根据各顶点事件的ve值和vl值，求各活动ai的e(i)和l(i)。

假设e(i)=l(i)，那么ai为关键活动。31精选ppt3、算法描述：StackTopologicalOrder(ALGraphG,StackT){inti,j,k,count;StackS;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);InitStack(&T);for(i=0;i<G.vexnum;i++){if(!indegree[i])Push(&S,i);}count=0;for(i=0;i<G.vexnum;i++)ve[i]=0;while(!StackEmpty(&S)){Pop(&S,&j);Push(&T,j);count++;for(p=G.vertices[j].firstarc;p;p=p->nextrc){k=p->adjvex;if(--indegree[k]==0)Push(&S,k);if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}}if(count<G.vexnum){}elsereturnT;}32精选pptintCriticalPath(ALGraphG){StackT;inti,j,k,dut,ee,el;ArcNode*p;intvl[n];T=TopologicalOrder(G,T);for(i=0;i<G.vexnum;i++)vl[i]=ve[G.vexnum-1];while(!StackEmpty(&T))for(Pop(&T,&j),p=G.vertices