第2章网络图绘制与关键路径课件.ppt

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

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

3、：只表示工作之间的相互关系。箭线的箭头方向表示互关系。箭线的箭头方向表示工作的前进方向。工作的前进方向。.代号：一项工作只能有一个代号：一项工作只能有一个代号。箭头节点的号码应大于代号。箭头节点的号码应大于箭尾节点的号码。箭尾节点的号码。NO：n工作名称工作名称持续时间持续时间123ESLSEFLF7单代号网络图法特点n1）单代号搭接网络图必须正确表述已定的逻辑关）单代号搭接网络图必须正确表述已定的逻辑关系。系。n2)单代号搭接网络图中，严禁出现单代号搭接网络图中，严禁出现循环回路循环回路。n3)单代号搭接网络图中，严禁出现双向箭头或无单代号搭接网络图中，严禁出现双向箭头或无箭头的连线。箭头的

4、连线。n4)单代号搭接网络图中，严禁出现没有箭尾节点单代号搭接网络图中，严禁出现没有箭尾节点的箭线和没有箭头节点的箭线。的箭线和没有箭头节点的箭线。n5)绘制网络图时，绘制网络图时，箭线不宜交叉箭线不宜交叉。n6)单代号搭接网络图只应有一个起点节点和一个单代号搭接网络图只应有一个起点节点和一个终点节点。当网络图中有多项起点节点或多项终点终点节点。当网络图中有多项起点节点或多项终点节点时，应在网络图的两端分别设置一项虚工作，节点时，应在网络图的两端分别设置一项虚工作，作为该网络图的起点节点作为该网络图的起点节点(St)和终点节点和终点节点(Fin)8单代号网络图法特点1)1)工作之间的逻辑关系容

5、易表达，绘图较简单；工作之间的逻辑关系容易表达，绘图较简单；2)2)网络图便于检查和修改；网络图便于检查和修改；3)3)由于工作持续时间表示在节点之中，没有长度，故由于工作持续时间表示在节点之中，没有长度，故不够形象直观；不够形象直观；4)4)表示工作之间逻辑关系的箭线可能产生较多的纵横表示工作之间逻辑关系的箭线可能产生较多的纵横交叉现象。交叉现象。9例：绘制如下表工作关系的单代号网络计划图例：绘制如下表工作关系的单代号网络计划图工序工序ABCDEFGHI紧后工作紧后工作CDEFEFGHHI-始始BFIHGECAD终终10双代号网络图法n箭线式网络图(Arrow Diagramming Met

6、hod)以箭线表示活动，每个活动都由两个数字来定义。节点代表关系虚活动我国应用比较多，国内采用该方法的软件较多A45312CBD11双代号网络图图例总体设计需求确认需 求 获取系统测试集成测试编码详 细 设计计划评审项目规划12369875412如何编制进度计划0 建立企业和项目资源库1 设置项目日历、资源日历2 设置项目的主要里程碑点3 在WBS下列出工作清单（Task，Activity）4 估计每个Task的工期5 计算每个Task之间的逻辑关系6 加载完成每个Task所需要的资源和资源数量7 进度计算后，看开工/完工里程碑是否符合合同或业主要求，看资源负荷是否过大？8 需要调整吗？9 调

7、整的方法：压缩关键路径上Task的工期：多投入资源以缩短工期，分解工期较长的作业10 合适了吗？合适了，则把第一份计划保存为目标计划（Baseline）11 公布第一版计划，通知项目干系人 13关键路线：CPM从项目开始到结束占用时间最长的路线工作总时差为零的工作，也就是其开始时间或结束时间没有任何机动余地的工作。项目的总工期是由关键路线的工作总时间决定的 CPM上任一节点若不按期完成，则整个计划的完工 若要缩短项目的计划完工期限，应当设法缩短某个或某些关键工作的作业时间 某个项目关键路线可能不止一条14正推法(Forward pass)按照时间顺序计算最早开始时间和最早完成时间的方按照时间顺

8、序计算最早开始时间和最早完成时间的方法法,称为称为正推法正推法.q首先建立项目的开始时间q项目的开始时间是网络图中第一个活动的最早开始时间q从左到右，从上到下进行任务编排q当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期q公式:qES+Duration=EF15正推法实例StartLFLSEFESDuration=7Task A18LFLSEFESDuration=3Task B14LFLSEFESDuration=6Task C814LFLSEFESDuration=3Task D47LFLSEFESDuration=3Task G1417LFLSEFESDur

9、ation=3Task E710LFLSEFESDuration=2Task H1719LFLSEFESDuration=2Task F46Finish当一个任务有多个前置时，选择其中最大的最早完成日期作为其后置任务的最早开始日期16逆推法(Backward pass)按照逆时间顺序计算最晚开始时间和最晚结束时间的按照逆时间顺序计算最晚开始时间和最晚结束时间的方法方法,称为逆推法称为逆推法.q首先建立项目的结束时间q项目的结束时间是网络图中最后一个活动的最晚结束时间q从右到左，从上到下进行计算q当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为其前置任务的最晚完成日期q公式:qLF-

10、Duration=LS17逆推图示StartLFLSEFESDuration=7Task A1818LFLSEFESDuration=3Task B14811LFLSEFESDuration=6Task C814814LFLSEFESDuration=3Task D471114LFLSEFESDuration=3Task G14171417LFLSEFESDuration=3Task E7101417LFLSEFESDuration=2Task H17191719LFLSEFESDuration=2Task F461214Finish当一个前置任务有多个后置任务时，选择其中最小最晚开始日期作为

11、其前置任务的最晚完成日期CP:A-C-G-HCp Path:1818课堂练习q作为项目经理，你需要给一个软件项目做计划安排，经过任务分解后得到任务A，B，C，D，E，F，G，假设各个任务之间没有滞后和超前，下图是这个项目的PDM网络图。通过历时估计已经估算出每个任务的工期，现已标识在PDM网络图上。假设项目的最早开工日期是第天，请计算每个任务的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间，同时确定关键路径，并计算关键路径的长度.19课堂练习LFLSEFESDuration=3Task GLFLSEFESDuration=4Task A0LFLSEFESDuration=6Task B

12、LFLSEFESDuration=7Task CLFLSEFESDuration=5Task DLFLSEFESDuration=8Task ELFLSEFESDuration=8Task F确定以及的长度？确定以及的长度？20课堂练习-答案LFLSEFESDuration=3Task GLFLSEFESDuration=4Task A0LFLSEFESDuration=6Task BLFLSEFESDuration=7Task CLFLSEFESDuration=5Task DLFLSEFESDuration=8Task ELFLSEFESDuration=8Task F4410412121

13、9192412202427272424241619191212612440CP:A-E-C-D-GCP Path:27211、边表示活动的网边表示活动的网(Activity On Edge Network，简称为AOE网)为带权有向无环图，其中：顶点表示事件事件，边表示活动活动，边的权值表示活动持续的时间活动持续的时间。其中：其中：AOE网中顶点表示的网中顶点表示的事件事件实际上体现了一种状态，实际上体现了一种状态，即即该顶点的所有入边表示的活动均已完成，出边表示的活该顶点的所有入边表示的活动均已完成，出边表示的活动可以开始。动可以开始。v1v2v3v4v53813223一个一个AOE网网a1

14、a2a3a4a5a6a7关键路径程序实现一、基本概念一、基本概念222、源点、汇点源点、汇点：表示实际工程的：表示实际工程的AOE网应该只有一个入网应该只有一个入度为度为0的顶点和一个出度为的顶点和一个出度为0的顶点，前者称作为的顶点，前者称作为源点源点，后者称作为后者称作为汇点汇点。研究的问题：对于表示工程计划的研究的问题：对于表示工程计划的AOE网，需要研究的网，需要研究的问题是：问题是：完成整个工程至少需要多少时间？完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？哪些活动是影响工程进度的关键？23v1v2v3v4v53813223a1a2a3a4a5a6a73、关键路径：关键

15、路径：由于由于AOE网中的若干活动是可以并行进行网中的若干活动是可以并行进行的，所以完成工程的最短时间是从源点到汇点的最长路径的，所以完成工程的最短时间是从源点到汇点的最长路径的长度，即最长路径上各边权值之和。的长度，即最长路径上各边权值之和。从源点到汇点的最从源点到汇点的最长路径称为关键路径。长路径称为关键路径。AOE网中的关网中的关键路径可能不键路径可能不止一条。止一条。24 事件事件vj可能的最早发生时间可能的最早发生时间ve(j)应为从源点应为从源点到顶点到顶点vj 的的 最长路径长度最长路径长度 弧弧表示的活动表示的活动ai的的最早开始时间最早开始时间e(i)等于等于ve(j)。在不

16、推迟整个工程完成的前提下，在不推迟整个工程完成的前提下，事件事件vk允允许的最迟发生许的最迟发生 时间时间vl(k)应等于汇点应等于汇点vn的最的最迟迟发发生时间生时间vl(n)减去减去 vk到到vn的最长路径长度的最长路径长度。弧弧表示的活动表示的活动ai的最迟开始时间的最迟开始时间l(i)等于等于vl(k)减去弧减去弧的权值。的权值。4、ve(j)、e(i)、vl(k)、l(i)25v1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,vl(2)=11-8=3e(1)=0l(1)=vl(2)-3=026 5、关键活动、关键活动：对活动：对活动ai而言，而言，l(i

17、)-e(i)为其在不延误整个为其在不延误整个工程工期情况下，可以延迟的时间。工程工期情况下，可以延迟的时间。若若e(i)=l(i)则称活动则称活动ai为关键活动。为关键活动。关键路径上的所有活动都是关键活动。缩短关键路径上的所有活动都是关键活动。缩短或延误关键活动的持续时间将提前或推迟整或延误关键活动的持续时间将提前或推迟整个工程的完工时间。个工程的完工时间。27二、如何求二、如何求AOE网的关键活动网的关键活动 1、分析：分析：由关键活动的定义可知，只要求出了某个活由关键活动的定义可知，只要求出了某个活动的动的e(i)和和l(i)，便可判断该活动是否为关键活动。而为，便可判断该活动是否为关键

18、活动。而为了求了求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=nv1v2v3v4v53813223a1a2a3a4a5a6a7ve(1)=0ve(2)=3ve(

19、3)=maxve(1)+2,ve(2)+2=5ve(4)=maxve(1)+1,ve(3)+3=8ve(5)=maxve(2)+8,ve(4)+3=11 AOE网中网中计算事件计算事件的的ve(j)是按顶点的是按顶点的某一拓扑序列的次某一拓扑序列的次序进行的。序进行的。29(2)从从vl(n)=ve(n)开始向后递推开始向后递推 vl(i)=minvl(j)-dut()属于以属于以vi为尾的弧的集合，为尾的弧的集合，1=i=n-1v1v2v3v4v53813223a1a2a3a4a5a6a7vl(5)=11vl(4)=vl(5)-3=8vl(3)=vl(4)-3=5vl(2)=minvl(3)

20、-2,vl(5)-8=3vl(1)=minvl(2)-3,vl(3)-2,vl(4)-1=0 AOE网中网中计算事计算事件的件的vl(i)是按顶是按顶点的某一拓扑序点的某一拓扑序列的逆序进行的。列的逆序进行的。30e(i)=ve(j)l(i)=vl(k)-dut()vl(5)=11vl(4)=8vl(3)=5vl(2)=3vl(1)=0 ve(1)=0ve(2)=3ve(3)=5ve(4)=8ve(5)=11 活动活动 a1 a2 a3 a4 a5 a6 a7 e 0 0 0 3 5 3 8 l 0 7 3 3 5 3 8 l-e 0 7 3 0 0 0 0v1v2v3v4v53813223a

21、1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a7312、求关键活动的算法：求关键活动的算法：(1)(1)对对AOEAOE网进行拓扑排序，并按排序的次序求网进行拓扑排序，并按排序的次序求各顶点事件的各顶点事件的veve值值,若网有回路，则算法终止，否若网有回路，则算法终止，否则执行步骤则执行步骤(2);(2);(2)(2)按拓扑排序的逆序求各顶点事件的按拓扑排序的逆序求各顶点事件的vlvl值值;(3)(3)根据各顶点事件的根据各顶点事件的veve值和值和vlvl值，求各活动值，求各活动aiai的的e(i)e(i)和和l(i)l(i)。若若e(i)=l(i)

22、e(i)=l(i)，则，则aiai为为关键活动关键活动。323、算法描述算法描述：Stack TopologicalOrder(ALGraph G,Stack T)int i,j,k,count;Stack S;ArcNode*p;FindInDegree(G,indegree);InitStack(&S);InitStack(&T);for(i=0;iG.vexnum;i+)if(!indegreei)Push(&S,i);count=0;for(i=0;inextrc)k=p-adjvex;if(-indegreek=0)Push(&S,k);if(vej+p-infovek)vek=ve

23、j+p-info;if(countG.vexnum)else return T;33int CriticalPath(ALGraph G)Stack T;int i,j,k,dut,ee,el;ArcNode*p;int vln;T=TopologicalOrder(G,T);for(i=0;inextrc)k=p-adjvex;dut=p-info;if(vlk-dutvlj)vlj=vlk-dut;for(j=0;jnextrc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf();34双代号时标网络计划n双代号时标

24、网络计划的概念n双代号时标网络计划的时间参数计算1312345678910112456ABEGFCDHITF=1TF=1TF=0TF=0TF=3TF=3TF=135双代号时标网络计划的概念n1.基本符号：n实箭线：水平投影长度表示工作的持续时间 n虚箭线：虚工作 n波形线：工作自由时差 minijj kijFFESEFijijijijijTFLFEFLSES36双代号时标网络计划的概念n2.绘制规则n按最早时间绘制；n各工作的时间参数由其在时标表上的水平位置表示；n各工作持续时间由其水平投影长度表示；n自由时差由波形线表示。37时标网络计划的时间参数计算n1.关键路线：没有波形线的路线n2.时间参数的确定n计算工期n工作最早时间n工作最迟时间n工作总时差n工作自由时差38工序紧后工序时间工序时间紧后工序AD3G9-BH,F,E,D6H3I,JCK,G5I15-DK4J6KEI,J2K4LFK,G2L5-1、请绘制网络图、确定关键路线；绘制各工序在最早时间开始时标网络图综合作业