网络图绘制与关键路径

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

事件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)v1v2v3v4v53813223a1a2a3a4a5a6a7ve(5)=11,

vl(2)=11-8=3

e(1)=0

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

5、关键活动:对活动ai而言,l(i)-e(i)为其在不延误整个工程工期情况下,可以延迟得时间。若e(i)=l(i)则称活动ai为关键活动。关键路径上的所有活动都是关键活动。缩短或延误关键活动的持续时间将提前或推迟整个工程的完工时间。二、如何求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>),则有如下关系:求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)是按顶点的某一拓扑序列的次序进行的。(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)是按顶点的某一拓扑序列的逆序进行的。e(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-e0730000v1v2v3v4v53813223a1a2a3a4a5a6a7v1v2v3v4v53813223a1a2a3a4a5a6a72、求关键活动得算法:(1)对AOE网进行拓扑排序,并按排序得次序求各顶点事件得ve值,若网有回路,则算法终止,否则执行步骤(2);(2)按拓扑排序得逆序求各顶点事件得vl值;(3)根据各顶点事件得ve值和vl值,求各活动ai得e(i)和l(i)。

若e(i)=l(i),则ai为关键活动。3、算法描述: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;}intCri