AOE网中求解关键路径（Critical Path）

╰+攻爆jí腚メ 2023-02-14 13:12 23阅读 0赞

首先推荐有个b站视频，讲关键路径讲的非常好，20min可搞懂：[https://www.bilibili.com/video/BV1PW41187vc?from=search&seid=40093726432206649][https_www.bilibili.com_video_BV1PW41187vc_from_search_seid_40093726432206649]

## 一、概念 ##

AOE网: 用顶点表示事件，用边表示活动，权表示活动持续的时间。

AOE网可回答的问题有：完成整个工程至少需要多长时间？哪些活动是影响工程进度的关键？活动的最早开始时间和最晚开始时间？活动的总浮动和自由浮动时间？

找到AOE网的关键路径属于项目管理的范围，应由项目经理严格把控和协调每个活动的最早/最晚开始时间，以致于不影响项目的完成日期。

关键路径：决定项目最早完成时间的一系列活动。如果两个或多个路径的长度相同，则可以有多个关键路径。项目经理应密切监控关键路径上活动的表现，以避免项目延迟完成。

free float自由浮动：一项活动可以被延迟的时间，而不会延迟任何紧随其后的活动的提前开始。

total float总浮动：一个活动可能从其早期开始被延迟的时间量，而不会延迟计划的项目完成日期。

Forward pass：确定较早的开始和完成日期   ES（最早开始时间）

Backward pass ：确定较晚的开始和完成日期  LF （最晚开始时间）

## 二、例子： ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70][]

### 1.  Construct the CPM Network Diagram ###

用结点表示事件，边表示活动，括号里的数值代表活动的持续时间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1][]

###  2.  Calculate the Forward Pass, Backward Pass, Free Float ###

先规定一下： Dij来表示一条边，则i表示出度，j表示入度。比如A12 , F56。v来表示结点，如v1 , v2。

![20200603003353424.png][]

**ES：最早开始时间**

顶点（事件）的最早开始时间：如上公式，比如求V(4)的最早开始时间，V(4)可由V(2)+D(4)得来，也可以由V(5)+E(5)得来，取两者最大值作为v(4)的ES。通俗讲，结点4可由结点2或结点5得来，将这些代价算出来取最大值即可。最早开始时间不应该尽可能取最小吗，这里为什么取最大值呢？因为结点4要开始，则它之前的工作必须全部做完，假设它之前需要做两份工作，一份花费1h，一份花费2h，则必须等这两份工作都做完后（等待一个两者中时间的最大值）才能开始开启结点4的事件。

边（活动Dij ）的最早开始时间 = V(i)，比如活动G，该活动的最早开始时间等于结点4的最早开始时间。

![20200603004445787.png][]

**LF:   最晚开始时间**

顶点（事件）的最晚开始时间：从Finish结点开始，往前去计算。比如结点2，既可以通过3返回，也可以通过4返回，这时取这俩值中的最小值。可以这样理解，比如由结点3的LF推得结点2的LF为第一天，由结点4的LF推得结点2的LF为第二天。这里可得结点2的LF应为第一天，如果结点2选择第二天开始的话，则结点4就不能在指定时间完成了，会延误。

边（活动Dij ）的最晚开始时间 = V(J)的最晚开始时间-duration（活动持续时间）。比如G(6)的最晚开始时间等于V(7)-6。

**Total float:** 一个活动可以被延迟多久，而不会影响项目的完成日期。对于每个活动，直接用最晚开始时间-最早开始时间。

**Free float: **一个活动可以被延迟多久，而不会影响紧随其后的活动的提前开始。该活动入度结点的最早开始时间-该活动入度结点的最早开始时间-该活动持续时间。比如F(7).free float = V(6).ES - V(5).ES - F.duration = 23 - 16 - 7 = 0.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 2][]

###  3. Critical Path: ###

从结点的表格和边的表格都可以看出关键路径。首先明确关键路径上的边没有松弛时间，即最早开始时间=最晚开始时间，关键路径经过的结点也没有松弛时间，最早开始时间=最晚开始时间。

从结点角度看，1,2,3,4,5,7,8,9的ES等于LF。将这些结点相连，就为关键路径。

从边的角度看，A,B,C,E,G,I,J的ES等于LF。将这些边用红线标出，如下图。

> 从结点表格看，
> 
> 1->2->3->5->4->7->8->9
> 
> A-B-C-E-G-I-J = 5+8+3+5+6+6+5 = 38

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 3][]

[https_www.bilibili.com_video_BV1PW41187vc_from_search_seid_40093726432206649]: https://www.bilibili.com/video/BV1PW41187vc?from=search&seid=40093726432206649
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603001720451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200603001819626.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0,size_16,color_FFFFFF,t_70
[20200603003353424.png]: https://img-blog.csdnimg.cn/20200603003353424.png
[20200603004445787.png]: https://img-blog.csdnimg.cn/20200603004445787.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200603001946578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020060300203396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0,size_16,color_FFFFFF,t_70