專案管理中通過CPM演算法求關鍵路徑,最早和最晚開始時間

NO IMAGE

首先貼一下百度百科對CPM的定義:

關鍵路徑法(Critical Path Method, CPM)是一種基於數學計算的專案計劃管理方法,是網路圖計劃方法的一種,屬於肯定型的網路圖。關鍵路徑法將專案分解成為多個獨立的活動並確定每個活動的工期,然後用邏輯關係(結束-開始、結束-結束、開始-開始和開始結束)將活動連線,從而能夠計算專案的工期、各個活動時間特點(最早最晚時間、時差)等。在關鍵路徑法的活動上載入資源後,還能夠對專案的資源需求和分配進行分析。關鍵路徑法是現代專案管理中最重要的一種分析工具。

最早開始時間:活動開始的最早時間
最晚開始時間:在保證不延期的前提下可以開始的最晚時間

對於給定的活動圖求出他的關鍵路徑,最早和最晚開始時間一般採用回溯法,通俗講就是從結束節點回推各個節點的開始時間。下面用一個例子展示這種演算法:

如圖,求出關鍵路徑,最早開始時間和最晚開始時間,時差和各個活動的前驅節點。
這裡寫圖片描述

  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。

由於最近在學習軟體工程這門課程,所以按照官方定義自己捉摸了這個做題的路子,有什麼不對的還請指正。