关键路径

简介

概念：

1. AOE网（Activity On Edge Network，用顶点表示活动的网）：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络。
2. 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
3. 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
4. 完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

求解关键路径的一些定义：

• 事件$v_k$的最早发生时间$ve{(k)}$——决定了所有以$v_k$开始的活动能够开工的最早时间
• 活动$a_i$的最早开始时间$e(i)$——指该活动弧的起点所表示的事件的最早发生时间
• 事件$v_k$的最迟发生时间$vl(k)$——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
• 活动$a_i$的最迟开始时间$l(i)$——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
• 活动$a_i$的时间余量$d(i)=l(i)-e(i)$，表示在不增加完成整个工程所需总时间的情况下，活动$a_i$可以拖延的时间
• 若一个活动的时间余量为零，则说明该活动必须要如期完成，$d(i)=0$的活动$a_i$是关键活动；由关键活动组成的路径就是关键路径。

求解关键路径的步骤：

1. 求所有事件的最早发生时间$ve()$

   • 按拓扑排序序列，依次求各个顶点的 $v e(k)$ :
     $v e($ 源点 $)=0$
     v e(k)=\operatorname{Max}\left\{v \mathrm{e}(j)+\operatorname{Weight}\left(v_{j}, v_{k}\right)\right\}, \quad v_{j} 为 $v_{k}$ 的任意前驱

2. 求所有事件的最迟发生时间$vl()$

   • 按逆拓扑排序序列，依次求各个顶点的 v l(\boldsymbol{k}) :
     $v l($ 汇点 )=v e( 汇点)

     v l(k)=\operatorname{Min}\left\{v l(j)-\operatorname{Weight}\left(v_{k}, v_{j}\right)\right\}, v_{j} 为 $v_{k}$ 的任意后继

3. 求所有活动的最早发生时间$e()$

   • 若边 $<v_{k}, v_{j}>$ 表示活动 $a_{i}$, 则有 $e(i)=v e(k)$

4. 求所有活动的最迟发生时间$l()$

   • 若边 $<v_{k}, v_{j}>$ 表示活动 $a_{i}$, 则有 $l(i)=v l(j)-$ Weight $\left(v_{k}, v_{j}\right)$

5. 求所有活动的时间余量$d()$

   • $d(i)=l(i)-e(i)$

关键活动、关键路径的特性：

1. 若关键活动耗时增加，则整个工程的工期将增长
2. 缩短关键活动的时间，可以缩短整个工程的工期
3. 当缩短到一定程度时，关键活动可能会变成非关键活动
4. 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。