关键路径是指设计中从输入到输出经过的延时最长的逻辑路径(从起点到终点的最长路径)。
有了这个概念就可以求解大部分常见问题啦,比如下面这个 AOE 网,求一下关键路径和关键路径长度
不就是最长的路径嘛?像这种题如果是选择、填空或者简答题,最简单的办法就是列出所有路径长度,找出最长的,就是答案了。此题有 2 个关键路径,即 V1-V2-V5-V7 和 V1-V4-V5-V7,长度都是 10,答案就出来了。大概用时不到半分钟,如果按步骤用正常方法,估计至少需要几分钟的时间。
但是遇到求解下面一些概念的时候,则不得不按常规方法做了:
(1) 事件开始的最早时间 ve(i);
(2) 事件开始的最晚时间 vl(i);
(3) 活动开始的最早时间 e(i);
(4) 活动开始的最晚时间 l(i) ;
定义 e(i)=l(i)的活动叫关键活动,也就是关键路径上的活动;
下面还是以上图为例,求解上面 4 个时间(注意 AOE 网中顶点代表事件,边代表活动):
求解顺序是,先求 ve(i),然后是 vl(i),再然后根据这两个即可分别求得 vl(i)、l(i)。
还是这个图:
从起点开始向终点找
先看 V1,作为第一个事件,V1 的最早开始时间 ve(i) 毫无疑问应该是 0;
然后是 V2,从 V1 到它只有一条路径 (a1=3),那么它的最早开始时间应该是 0+3=3;
同理 V3,应该就是 0+2=2;
重点是 V4,从 V1 到它有 3 条路径,分别是 (a1=3,a5=2)、(a2=6)、(a3=2,a6=1),其中第二个路径最长为 6,第 3 个最短为 3。由最早开始,容易想到路径最短,但是要注意 AOE 网下面的性质(2):
(1)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。
(2)只有在进入某点的各有向边所代表的活动都已结束,该顶点所代表的时事件才能发生。
只有 a2 完成后,才能算都结束,所以 V4 的最早开始时间 ve(i) 是 6;
小结:Vi 的最早开始时间 ve(i) 就是从起点到它的最长路径;
从终点开始向起点找
先看 V7,算 V7 的 ve(i) 时就已经得出,从起点到它最多需要 10,所以它的最晚开始时间 vl(i) 也不能再多于 10 了,也即 vl(i)=ve(i)=10。
然后是 V6,V7 最晚开始是 10,而 V6 到 V7 需要 4,所以 V6 再晚也不能晚于 10-4=6 吧;
同理 V5,是 10-3=7,V4,是 7-1=6;
重点是 V2,有 V4 和 V5 两个事件限制它,V5 需要它最晚不能晚于 7-4=3,V4 需要它不能晚于 6-2=4,
所以它最晚不能晚于 3 不难理解吧?
小结:从终点倒推,终点的 vl(i)=ve(i),事件 i 的直接后续事件减去活动时间为要求它最晚开始的事件,其中最小的一个就是它的 vl(i);
所有事件的 ve(i) 和 vl(i):
有了 ve(i) 和 vl(i),e(i) 和 l(i) 就好求了:
ai 的 e(i)就等于 ai 的起点 (弧头) 事件的 ve(i),比如 a1、a2、a3 的 e(i)等于 V1 的 ve(i)都是 0,a4 的 e(i)是 3;
ai 的 l(i)就等于 ai 的终点 (弧尾) 事件的 vl(i)减去 ai,比如 a7 的 l(i)是 V7 的 vl(i)减去 ai,即 10-4=6,a5、a2、a6 的 l(i)分布是 6-2=4、6-6=0、6-1=5
最终结果:
其中 e(i)=l(i) 即 e(i)-l(i)=0 的活动,就是关键活动啦。
(1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;
(2) 只有缩短关键活动的工期才有可能缩短工期;
(3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;
(4) 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
注意这个 "有可能",还是以上题为例,如果把关键活动 a4 由 4 缩短为 3,并不能缩短关键路径的长度,它还是 10,因为这样 V1-V4-V5-V7 的最长度为 9,已经不是关键路径了;
那么把公共的关键活动 a9 由 3 缩短为 2 呢?这样是可以的,关键路径长度变为 9;
把 a9 由 3 缩短为 1 呢?那 V1-V2-V5-V7 和 V1-V4-V5-V7 就都不是关键路径了;
试试下面两个题?
按简单方法,是不是几秒钟就可以选出正确答案?
.
.
.
.
.
.
.
.
.
.
.
.
.
正确答案:A
从上至下第一条路径的长度就是 20,而选项里最大就是 20。
能有效缩短关键路径长度的方法是()。
A.缩短任意一个活动的持续时间
B.缩短关键路径上任意一个关键活动的持续时间
C.缩短多条关键路径上共有的任意一个关键活动的持续时间
D.缩短所有关键路径上共有的任意一个关键活动的持续时间
.
.
.
.
.
.
.
.
.
.
.
.
.
.
正确答案:D
关键路径是始点和终点间的最长路径,只有所有关键路径的长度都缩短,整个图的关键路径才能有效缩短,但也不能任意缩短,一旦缩短到一定程度,该关键活动可能变成非关键活动了。
来源: http://www.jianshu.com/p/038a59851ac7