系统集成项目管理工程师(关键路径).ppt

《系统集成项目管理工程师(关键路径).ppt》由会员分享，可在线阅读，更多相关《系统集成项目管理工程师(关键路径).ppt（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.8 关键路径关键路径问题问题:假设以有向网表示一个施工流图，弧上的权值表示假设以有向网表示一个施工流图，弧上的权值表示完成某活动所需时间。完成某活动所需时间。问：哪些活动是问：哪些活动是“关键活动关键活动”？即：哪些活动将影响整个工程的完成期限的？即：哪些活动将影响整个工程的完成期限的？abcdefghk645211872446174活动活动事件事件1 1abcdefghk64521182446147“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点72 2如何求关键活动？

2、如何求关键活动？“活动活动(弧弧)”的的 最早开始时间最早开始时间 e(i)“活动活动(弧弧)”的的 最迟开始时间最迟开始时间 l(i)关键活动关键活动：e(i)l(i)“事件事件(顶点顶点)”的的最早发生时间最早发生时间 ve(j)“事件事件(顶点顶点)”的的最迟发生时间最迟发生时间 vl(k)假设第假设第 i 条弧为条弧为 则则 对第对第 i 项活动言项活动言e(i)=ve(j)；l(i)=vl(k)dut()；jkiabce6411613 3事件事件(顶点顶点)发生时间的计算公式发生时间的计算公式最早开始时间：最早开始时间：ve(源点源点)=0；ve(k)=Maxve(j)+dut()最

3、迟开始时间：最迟开始时间：vl(汇点汇点)=ve(汇点汇点)；vl(j)=Minvl(k)dut()abce6411614 4abcdefghk645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k5 506457715 14 181814161078660000645777 15 14141602366887 106 6算法的实现算法的实现求求ve的顺序应该是按拓扑排序的次序；的顺序应该是按拓扑排序的次序；求求vl的顺序应该是按拓扑逆序的次序；的顺序应该是按拓扑逆序的次序；因为拓扑逆序序列即为拓扑有序序列的逆序列，因为拓扑逆序序列即为拓扑有序序列的逆序列，因此应该在拓扑排序的过程中，另设一个因此应该在拓扑排序的过程中，另设一个“栈栈”记记下拓扑有序序列。下拓扑有序序列。7 7