AOE网及其求解关键路径

全称

Activity on Edge Network 边活动网

特点

仅存在 有向无环图 

作用

用于记录完成整个工程至少花费的时间 ==> 哪条路径最耗时？也就是“ 关键路径 ”

AOE网元素介绍

关键活动

关键路径上的活动称为关键活动 ， 关键活动是不允许拖延的（普通活动可以拖延，拖延时间=最晚开始时间-最早开始时间），因为已经是耗时最长的一条路径，再拖延就耽误了工期。也就是说，关键活动的最早开始时间=最晚开始时间 

 

如何求得关键路径

先计算事件的最早开始时间

起点的最早开始时间=最晚开始时间=0

从前往后看，该事件的最早开始时间ve=max{原本的最早开始时间，前驱事件的ve+活动耗费的时间}

先初始化所有点的最早开始时间为0；

选取入度为0的点V1，V2的最早开始时间=max{0，0+2}=2，V3的最早开始时间=max{0，0+5}=5。删除V1及其出度边；

选取入度为0的点V2，V4的最早开始时间=max{0，2+3}=5，V3的最早开始时间=max{5，2+1}=5。删除V2及其出度边；

选取入度为0的点V3，V4的最早开始时间=max{5，5+3}=8，V6的最早开始时间=max{0，5+1}=6，V5的最早开始时间=max{0，5+4}=9。删除V3及其出度边；

选取入度为0的点V4，V5的最早开始时间=max{9，8+1}=9，V6的最早开始时间=max{6，8+4}=12。删除V4及其出度边；

选取入度为0的点V5，V6的最早开始时间=max{12，9+1}=12。删除V5及其出度边；

最后只剩V6。

接着计算事件的最晚开始时间

终点的最早开始时间=最晚开始时间=12

从后往前看，该事件的最晚开始时间vl=min{原本的最晚开始时间，后驱事件的vl-活动耗费的时间}

先初始化所有点的最晚开始时间为12；

选取出度为0的点V6，V4的最晚开始时间=min{12，12-4}=8，V3的最晚开始时间=min{12，12-1}=11，V5的最晚开始时间=min{12，12-1}=11。删除V6及其入度边；

 选取出度为0的点V5，V4的最晚开始时间=min{8，11-1}=8，V3的最晚开始时间=min{11，11-4}=7。删除V5及其入度边；

 选取出度为0的点V4，V2的最晚开始时间=min{12，8-3}=5，V3的最晚开始时间=min{7，8-3}=5。删除V4及其入度边；

 选取出度为0的点V3，V2的最晚开始时间=min{5，5-1}=4，V1的最晚开始时间=min{12，5-5}=0。删除V3及其入度边；

选取出度为0的点V2，V1的最晚开始时间=min{0，4-2}=0。删除V2及其入度边；

只剩下V1。

最终结果为：

 把每个事件的最早开始时间ve和最晚开始时间vl汇总成表格：

继续计算活动的最早开始时间

活动的最早开始时间=该活动前驱事件的最早开始时间

活动a、b的最早开始时间就是事件V1的最早开始时间0 

活动c、d的最早开始时间就是事件V2的最早开始时间2

活动e、g、f的最早开始时间就是事件V3的最早开始时间5

活动h、i的最早开始时间就是事件V4的最早开始时间8

活动j的最早开始时间就是事件V5的最早开始时间9

再计算活动的最晚开始时间

活动的最晚开始时间=该活动后驱事件的最晚开始时间-该活动耗时

活动a的最晚开始时间=事件V2的最晚开始时间-2=4-2=2

活动b的最晚开始时间=事件V3的最晚开始时间-5=5-5=0

活动c的最晚开始时间=事件V3的最晚开始时间-1=5-1=4

活动d的最晚开始时间=事件V4的最晚开始时间-3=8-3=5

活动e的最晚开始时间=事件V4的最晚开始时间-3=8-3=5

活动f的最晚开始时间=事件V5的最晚开始时间-4=11-4=7

活动g的最晚开始时间=事件V6的最晚开始时间-1=12-1=11

活动h的最晚开始时间=事件V5的最晚开始时间-1=11-1=10

活动i的最晚开始时间=事件V6的最晚开始时间-4=12-4=8

活动j的最晚开始时间=事件V6的最晚开始时间-1=12-1=11

找到关键活动

根据刚刚所求结果得出活动b、e、i是关键活动，其最早开始时间=最晚开始时间。

连接关键活动

所以关键路径就是由关键活动所连起来的这条路径。 

注意：关键路径可能有多条！！！