项目管理中通过CPM算法求关键路径，最早和最晚开始时间

左手的ㄟ右手 2022-06-16 13:44 96阅读 0赞

首先贴一下百度百科对CPM的定义：

关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。

最早开始时间：活动开始的最早时间   
最晚开始时间：在保证不延期的前提下可以开始的最晚时间

对于给定的活动图求出他的关键路径，最早和最晚开始时间一般采用回溯法，通俗讲就是从结束节点回推各个节点的开始时间。下面用一个例子展示这种[算法][Link 1]：

如图，求出关键路径，最早开始时间和最晚开始时间，时差和各个活动的前驱节点。   
![这里写图片描述][20151230122104340]

1.  求各个路径的总权值，权值最大的即为关键路径   
    ABDIJL 权值为3+5+2+2+8=20   
    ABDIJKL 权值为3+5+2+2+2+3=17   
    ABIJL 权值为19   
    ABIJKL 权值为16   
    AEGJL 权值为17   
    AEGJKL 权值为14   
    AEGHKL 权值为17   
    ACFHKL 权值为16   
    由此可知关键路径为ABDIJL。
2.  回溯求出最早，最晚开始时间和差值
    
    \*\*！！！！：对于关键路径上的活动最早最晚开始时间的差值始终为0；   
    最晚开始时间=后驱节点对应的时间-活动时间   
    （如果后驱节点对应多个时间，选取最小的那个）\*\*   
    最早开始时间=max\{到达前驱结点的路径权值\}+1   
    （这个加1是为什么呢？举个例子，一个工程的前半部分需要20天，从月初的1号开始，在20号正好完成，所以后半部分工程从21号开始）   
    e.p.   
    活动KL的的前驱节点为K，   
    最晚开始时间=（20+1）-3=18   
    （此处加1意义同上，但在计算最晚开始时间时只在最后活动加1，其他活动不必再加1，考虑考虑，这是符合常理的）   
    最早开始时间=max\{c(ABDIJ),c(ABIJ),c(AEGJ),c(AEGH),c(ACFH)\}+1=15   
    所以，   
    KL: Precursor\{K\} , Earliest start Time:15, latest Start Time:18 Slacktime:3;

在计算一个HK：   
通过计算KL我们知道K对应的最晚开始 时间为18   
最晚开始时间=18-4=14   
最早开始时间=11（方法同上）

所以此题所有答案如下：

AB: Precursor\{A\} , Earliest start Time:1, latest Start Time:1 Slacktime:0;   
BD: Precursor\{B\} , Earliest start Time:4, latest Start Time:4 Slacktime:0;   
DI: Precursor\{D\} , Earliest start Time:9, latest Start Time:9 Slacktime:0;   
BI: Precursor\{B\} , Earliest start Time:4, latest Start Time:5 Slacktime:1;   
AE: Precursor\{A\} , Earliest start Time:1, latest Start Time:5 Slacktime:3;   
EG: Precursor\{E\} , Earliest start Time:5, latest Start Time:8 Slacktime:3;   
GJ: Precursor\{G\} , Earliest start Time:8, latest Start Time:11 Slacktime:3;   
GH: Precursor\{G\} , Earliest start Time:8, latest Start Time:11 Slacktime:3;   
IJ: Precursor\{I\} , Earliest start Time:11, latest Start Time:11 Slacktime:0;   
AC: Precursor\{A\} , Earliest start Time:1, latest Start Time:5 Slacktime:4;   
CF: Precursor\{A\} , Earliest start Time:6, latest Start Time:10 Slacktime:4;   
FH: Precursor\{F\} , Earliest start Time:9, latest Start Time:13 Slacktime:4;   
HK: Precursor\{H\} , Earliest start Time:11, latest Start Time:14 Slacktime:3;   
JK: Precursor\{J\} , Earliest start Time:13, latest Start Time:16 Slacktime:3;   
JL: Precursor\{J\} , Earliest start Time:13, latest Start Time:13 Slacktime:0;   
KL: Precursor\{K\} , Earliest start Time:15, latest Start Time:18 Slacktime:3;

另外需要说明一点的是，在计算最晚开始时间时，如果后驱节点对应多个时间，选取最小的那个。   
例如，IJ   
J对应的最晚开始时间分别出现在JK和JL,选取小的那个13。

由于最近在学习软件工程这门课程，所以按照官方定义自己捉摸了这个做题的路子，有什么不对的还请指正。

[Link 1]: http://lib.csdn.net/base/datastructure
[20151230122104340]: /images/20220616/1a838fc2bee341e5aa8a77460b219922.png