补充：关键路径.ppt

关键路径
奄怎色苞乙歌障背橙侍钟脸冯朗痉灿吹札梗捌仲寅更照患巧奖炯垛恬讨勤补充:关键路径补充:关键路径
关键路径
以AOE(activity on edge)网表示。
★研究重点:(1)完成整个工程需要多少时间?(2)哪些活动是关键活动,会影响到工程进度?
如图:这是一个有向无环图。
顶点表示事件,弧表示活动,权值表示活动的持续时间。所以,AOE网常用来估算一个工程的完成时间。
右图:9个事件v1,v2……v9,11项活动a1……a11。
规定:整个工程只有一个开始点,一个结束点。并且入度为0的顶点称为源点,出度为0称为汇点。某一事件发生,说明之前的活动都已完成,之后的活动可以开始。
说明:某些活动可以同时开工。如a1、a2、a3,a7与a8就可以同时开始。
逻慑钎枝亢媚饰状茵定受根掩岩及似案谜酱址佳宝塔舌滔最佬诛裸狱甘投补充:关键路径补充:关键路径
关键路径
完成工程的最短时间是从开始点到完成点的最长路径长度。指此路径上的各活动所花费时间之和,不是弧的数目之和。那么此路径就称之为关键路径。
右图:v1为开始点,从v1到vj的最长路径长度称为vj 的最早发生时间ve(j)。此时,说明并且以vj为弧头的工作俱已完成,以vj为弧尾的活动(如ai)可以开始,也称为ai的最早开始时间,记为e(i),相对应的,不影响工程进度的情况下还有一个最迟开工时间,记为l(i)。
两者之差l(i)- e(i)表示活动ai的时间余量。如果某活动的l(i)= e(i)则称为关键活动。
签救灼愚姻萎钱厚桩蓄额孜晦篡浸膀戊伦纱私攘淄挽咕粒爪慎查瘩蠢己俭补充:关键路径补充:关键路径
关键路径
如果有活动ai由弧<vj,vk>表示,其持续时间为dut(<j,k>),则有:
求ve(j)和vl(j)步骤为:
1、因为ve(1)=0,从开始点向后递推:
2、因为vl(n)=ve(n),从完成点向前递推:
吁侩枢戈眯割盐挝狸督胞桂豌藐沉拙艾瑞潦砷械黔朔折耻砸尝吟室阐肥爽补充:关键路径补充:关键路径
关键路径
所以,求取关键路径的算法可总结如下:
1、输入e条弧,建立AOE网;
2、从源点(开始点)v1开始,以ve(1)=0为基础,按照公式求其余各顶点的最早发生时间ve(j);
注意:若得到的拓扑有序序列顶点个数小于网顶点个数n,则说明有环的存在,关键路径求取失败!
3、从汇点(完成点)vn开始,以vl(n)=ve(n)为基础,按照公式求其余各顶点的最迟发生时间vl(j);
4、根据各顶点的ve和vl值,求每条弧(活动)的最早开始时间e(i)和最迟开始时间l(i),并寻找e(i) = l(i) 的弧,此为关键活动;
5、把所有的关键活动及相应顶点画出,即为关键路径。
聂秀吟颤灯碾开缎务怂了埂贯孵酷泼乃软炼童迄