關鍵路徑法

關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑。最佳化關鍵路徑是一種提高設計工作速度的有效方法。一般地，從輸入到輸出的延時取決於信號所經過的延時最大路徑，而與其他延時小的路徑無關。在最佳化設計過程中關鍵路徑法可以反覆使用，直到不可能減少關鍵路徑延時為止。EDA工具中綜合器及設計分析器通常都提供關鍵路徑的信息以便設計者改進設計，提高速度。

基本介紹

• 中文名：關鍵路徑法
• 外文名：Critical path method
• 拼音：Guān jiàn lù jìng fǎ
• 簡稱：CPM
• 學科：運籌學
• 隸屬：網路計畫

起源

關鍵路徑法（CPM）最早出現於1956年，當時美國杜邦（Du Pont）公司的主要負責人Morgan Walker和雷明頓蘭德（Remington Rand）公司的數學家James E. Kelly研究如何能夠採取正確的措施，在減少工期的情況下能儘可能少的增加費用。1957年5月7日，Kelly借用了線性規劃的概念來解決項目計畫自動計算的問題，簡單的說就是確定了每個活動的工期和活動間的邏輯關係，輸入電腦後就能自動計算項目的工期，為了電腦的計算，Kelly在活動間使用了i，j這樣的節點來表示活動間的前後邏輯關係。同時Kelly繪製了圖形來解釋電腦所作的工作，圖形以箭線表示活動，以節點表示活動間的邏輯關係，這就是最早的箭線圖（ADM）。1959年，Kelly和Walker共同發表了”Critical Path Planning and Scheduling” 論文，在這篇長達25頁的論文中，Kelly和Walker不僅闡述了關鍵路徑法的基本原理，還提出了資源分配與平衡、費用計畫的方法。我們今天所使用的方法的原理，與Kelly和Walker在論文中提出的方法，並沒有原則上的不同。

與此同時，另外一個對關鍵路徑法（CPM）的發展起到重要作用的是美國海軍北極星計畫開發的計畫評審技術（PERT）。在1955年11月17日，美國海軍北極星計畫成立了一個特別項目管理辦公室（SPO），管理其Fleet Ballistic Missile計畫，負責人是Admiral Raborn。在1956年和1957年期間，他們研究了各種已經存在的項目管理技術，在大約1957年秋季的時候，他們接觸到了杜邦公司開發的計畫管理技術，這對他們開發PERT起到了重要的作用。1958年1月份，SPO研究了在計算機上實現計畫和控制的可行性，1958年1月27日，SPO正式成立了一個小組開發PERT技術，在大約一年以後，PERT技術成為一種可操作性的技術，計畫評審技術（PERT）和關鍵路徑法（CPM）基本上一樣，唯一的區別是計畫評審技術的每個活動的工期不是確定的，而是包括了悲觀值，樂觀值和最有可能值三個值。比較有趣的是，1959年，北極星計畫的這個特別項目管理辦公室（SPO）開了一個招待會，介紹他們的這種新技術，並希望參會者能給出更多的意見，Kelly和Walker在被邀請之列，在會上，他們發現SPO開發的PERT和他們的Kelly-Walker法原理上完全一樣，而SPO所說的關鍵線路（Critical Path），就是他們的Kelly-Walker法中的主鏈路（Main Chain）。回去之後，他們決定將它們的方法的名稱改為關鍵路徑法（Critical Path Method）。

關鍵路徑法（CPM）最初被開發是用於項目管理，不過，在發展過程中，它逐漸在工程項目的契約索賠和糾紛解決上起到重要作用。最早在訴訟中涉及到要求使用關鍵路徑法（CPM）是1972（Appeal of Minmar Builders，Inc，GSBCA No. 3430，72-2 BOA）年，在此案例中，法庭由於承包商沒有使用關鍵路徑法（CPM）而拒絕了承包商的索賠，因為其使用的橫道圖不能顯示具體的活動是否在關鍵線路上，從而無法判斷活動耽誤對於整體的影響。之後，關鍵路徑法（CPM）逐漸成為工期延誤索賠中必須的做法，並逐漸形成了很多專門的分析方法，甚至有很多人專業從事工期延誤分析的工作。

使用步驟

1. 畫出網路圖，以節點標明事件，由箭頭代表作業。這樣可以對整個項目有一個整體概觀。習慣上項目開始於左方終止於右方；
   
2. 在箭頭上標出每項作業的持續時間（T）；
   
3. 從左面開始，計算每項作業的最早結束時間（EF）。該時間等於最早可能的開始時間（ES）加上該作業的持續時間；
   
4. 當所有的計算都完成時，最後算出的時間就是完成整個項目所需要的時間；
   
5. 從右邊開始，根據整個項目的持續時間決定每項作業的最遲結束時間（LF）；
   
6. 最遲結束時間減去作業的持續時間得到最遲開始時間（LS）；
   
7. 每項作業的最遲結束時間與最早結束時間，或者最遲開始時間與最早開始時間的差額就是該作業的時差；
   
8. 如果某作業的時差為零，那么該作業就在關鍵路線上；
   
9. 項目的關鍵路線就是所有作業的時差為零的路線。
   

分類

關鍵路徑法是用尋找關鍵路徑及其時間長度來確定項目的完成日期與總工期的方法。

根據繪製方法的不同，關鍵路徑法可以分為兩種：即箭線圖（ADM）和前導圖（PDM）。

箭線圖（ADM）法又稱為雙代號網路圖法，它是以橫線表示活動而以帶編號的節點連線活動，活動間可以有一種邏輯關係，結束-開始型邏輯關係。在箭線圖中，有一些實際的邏輯關係無法表示，所以在箭線圖中需要引入虛工作的概念。

圖1 關鍵路徑法

箭線圖

箭線圖（ADM）要表示的是一個項目的計畫，所以其清晰的邏輯關係和良好的可讀性是非常重要的，除了箭線圖（ADM）本身具有正確的邏輯性，良好的繪圖習慣也是必要的。因此在繪圖時遵守上面的這些規則就是非常重要的，另外，在繪圖時，一般儘量使用直線和折線，在不可避免的情況下可以使用斜線，但是要注意邏輯方向的清晰性。繪製箭線圖時主要有以下一些規則：

1. 在箭線圖（ADM）中不能出現迴路；
   
2. 箭線圖（ADM）一般要求從左向右繪製；
   
3. 每一個節點都要編號，號碼不一定要連續，但是不能重複，且按照前後順序不斷增大；
   
4. 一般編號不能連續，並且要預留一定的間隔；
   
5. 表示活動的線條不一定要帶箭頭，但是為了表示的方便，一般推薦使用箭頭；
   
6. 一般要求雙代號網路圖要開始於一個節點，並且結束於一個節點；
   
7. 在繪製網路圖時，一般要求連線不能相交，在相交無法避免時，可以採用過橋法或者指向法等方法避免混淆。
   

前導圖

前導圖（PDM）法又稱為單代號網路圖法，它是以節點表示活動而以節點間的連線表示活動間的邏輯關係，活動間可以有四種邏輯關係，結束-開始、結束-結束、開始-開始和開始-結束。繪製前導圖時主要有以下一些規則：

1. 單代號網路圖必須正確表達已定的邏輯關係；
   
2. 單代號網路圖中，嚴禁出現循環迴路；
   
3. 單代號網路圖中，嚴禁出現雙向箭頭或無箭頭的連線；
   
4. 單代號網路圖中，嚴禁出現沒有箭尾節點的箭線和沒有箭頭節點的箭線；
   
5. 繪製網路圖時，箭線不宜交叉，當交叉不可避免時，可採用過橋法或指向法繪製。
   

時間參數

在關鍵路徑法中，一般有以下的時間參數：

最早開始時間（Early Start）是指活動最早開始時間，由所有前置活動中最後一個最早結束時間確定。

最早結束時間（Early Finish）是指活動最早結束時間，由活動的最早開始時間加上其工期確定。

最遲結束時間（Late Finish）是指一個活動在不耽誤整個項目的結束時間的情況下能夠最遲結束的時間。它等於所有緊後工作中最晚的一個最遲開始時間加上工期。

最遲開始時間（Late Start）是指一個活動在不耽誤整個項目的結束時間的情況下能夠最遲開始的時間。它等於活動的最遲結束時間減去活動的工期。

總時差（Total Float) 是指一項活動在不影響整體計畫工期的情況下最大的浮動時間。

自由時差（Free Float）是指活動在不影響其緊後工作的最早開始時間的情況下可以浮動的時間。

如果是對於箭線圖法，用到的時間參數還常有：

最早節點時間（Early Event Occurrence Time）由其前置活動中最晚的最早結束時間確定。

最遲節點時間（Late Event Occurrence Time）由其後置活動中最早的最遲開始時間確定。

時間計算

正推法

箭線圖（ADM）的計算一般有正推法（Forward Pass）和逆推法（Backward Pass）兩種，正推法用於計算活動和節點的最早時間，其算法如下：

1. 設定箭線圖（ADM）中的第一個節點的時間，如設定為1；
   
2. 選擇一個開始於第一個節點的活動開始進行計算；
   
3. 令活動最早開始時間等於其開始節點的最早時間；
   
4. 在選擇的活動的最早開始時間上加上其工期，就是其最早結束時間；
   
5. 比較此活動的最早結束時間和此活動結束節點的最早時間。如果結束節點還沒有設定時間，則此活動的最早結束時間就是該結束節點的最早時間；如果活動的結束時間比結束節點的最早時間大，則取此活動的最早結束時間作為節點的最早時間；如果此活動的最早結束時間小於其結束節點的最早時間，則保留此節點時間作為其最早時間；
   
6. 檢查是否還有其它活動開始於此節點，如果有，則回到步驟3進行計算；如果沒有，則進入下一個節點的計算，並回到步驟3開始，直到最後一個節點。
   

逆推法

活動和節點的最遲時間採用逆推法（Backward Pass）計算，逆推法（Backward Pass）一般從項目的最後一個活動開始計算，直到計算到第一個節點的時間為止，在逆推法的計算中，首先令最後一個節點的最遲時間等於其最早時間，然後開始計算，具體的計算步驟如下所示：

1. 設定最後一個節點的最遲時間，令其等於正推法計算出的最早時間；
   
2. 選擇一個以此節點為結束節點的活動進行計算；
   
3. 令此活動的最遲結束時間等於此節點的最遲時間；
   
4. 從此活動的最遲結束時間中減去其工期，得到其最遲開始時間；
   
5. 比較此活動的最遲開始時間和其開始節點的最遲時間。如果開始節點還沒有設定最遲時間，則將活動的最遲開始時間設定為此節點的最遲時間，如果活動的最遲開始時間早於節點的最遲時間，則將此活動的最遲開始時間設定為節點的最遲時間，如果活動的最遲開始時間遲於節點的最遲時間，則保留原節點的時間作為最遲時間；
   
6. 檢查是否還有其它活動以此節點為結束節點，如果有則進入第二步計算，如果沒有則進入下一個節點，然後進入第二步計算，直至最後一個節點；
   
7. 第一個節點的最遲時間是本項目必須要開始的時間，假設取最後一個節點的最遲時間和最早時間相等，則其值應該等於1。
   

套用

在項目管理中，編制網路計畫的基本思想就是在一個龐大的網路圖中找出關鍵路徑，並對各關鍵活動，優先安排資源，挖掘潛力，採取相應措施，儘量壓縮需要的時間。而對非關鍵路徑的各個活動，只要在不影響工程完工時間的條件下，抽出適當的人力、物力和財力等資源，用在關鍵路徑上，以達到縮短工程工期，合理利用資源等目的。在執行計畫過程中，可以明確工作重點，對各個關鍵活動加以有效控制和調度。

關鍵路徑法主要是一種基於單點時間估計、有嚴格次序的一種網路圖。它的出現為項目提供了重要的幫助，特別是為項目及其主要活動提供了圖形化的顯示，這些量化信息為識別潛在的項目延遲風險提供極其重要的依據。