|
|
|
关键路径法（Critical Path Method，CPM）是借助网络图和各活动所需时间（估计值）计算每一活动的最早或最迟开始和结束时间。CPM法的关键是计算总时差，这样可决定哪一个活动有最小的时间弹性。
|
|
|
|
CPM算法的核心思想是将WBS分解的活动按逻辑关系加以整合，统筹计算出整个项目的工期和关键路径。
|
|
|
|
在网络图中的某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度。移动从开始顶点到结束顶点的最长（工作时间之和最大）路径移动为关键路径（临界路径），关键路径上的活动称为关键活动。在一条路径中，每个工作的时间之和等于工程工期，这条路径就是关键路径。
|
|
|
|
与关键路径相关的概念还有最早开始时间、最迟开始时间、总时差和自由时差等。
|
|
|
|
（1）最早开始时间（最早开工时间）：一个工作可以最早开始的时间。工作的最早开始时间应为其各项紧前工作的最早完成时间的最大值。
|
|
|
|
（2）最迟开始时间（最迟开工时间、最晚开工时间）：不延误总工期的前提下，工作可以最晚的开始时间。
|
|
|
|
（3）总时差：不延误总工期的前提下，工作的机动时间。
|
|
|
|
（4）自由时差：不延误紧后工作开工的前提下，工作的机动时间。工作的自由时差等于其各项紧后工作最早开始时间的最小值与本项目最早完工时间之差。
|
|
|
|
工作的总时差也等于其紧后工作总时差的最小值与该工作自由时差之和。若在一条路径中，每个工作的总时差都是0，这条路径就是关键路径。
|
|
|
|
为了找出给定的网络图的关键活动，从而找出关键路径，需先定义几个重要的量。
|
|
|
|
.Ve（j）、Vl（j）：顶点j事件最早开始时间、最迟开始时间。
|
|
|
|
.e（i）、l（i）：活动i最早开始时间、最迟开始时间。
|
|
|
|
从源点Vl到某顶点Vj的最长路径长度称为事件Vj的最早开始时间，记做Ve（j）。Ve（j）也是以Vj为起点的出边<Vj，Vk>所表示的活动ai的最早开始时间e（i）。
|
|
|
|
在不推迟整个工程完成的前提下，一个事件Vj允许的最迟开始时间，记做Vl（j）。显然，l（i）=Vl（j）-（ai所需时间），其中j为ai活动的终点。满足条件l（i）=e（i）的活动为关键活动。
|
|
|
|
求顶点Vj的Ve（j）和Vl（j）可按以下两步来做。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
要求一个网络图的关键路径，一般需要根据以上变量列出一张表格，逐个检查。例如，求下图所示的网络图中关键路径的表格如下表所示。
|
|
|
|
|
|
|
|
|
|
|
|
根据上表，上图的关键活动为a1、a2、a4、a8和a9，其对应的关键路径有两条，分别为（V1，V2，V5，V7）和（V1，V4，V5，V7），长度都是10。
|
|
|
|
在一个网络图中，关键路径可以不止一条。例如，下图中的关键路径共有4条，分别是1→2→3→5→7→8，1→2→3→4→5→7→8，1→2→3→5→6→7→8及1→2→3→4→5→6→7→8。在下图中，从节点6到节点7中的虚线表示虚活动，虚活动只表示一种逻辑关系，没有历时。在下图中，表示活动L要在H、I和J都完成后才能开始。
|
|
|
|
|
|
|
