關(guān)鍵路徑法（Critical Path Method，CPM）是一種基于數(shù)學(xué)計(jì)算的項(xiàng)目計(jì)劃管理方法，是網(wǎng)絡(luò)圖計(jì)劃方法的一種，屬于肯定型的網(wǎng)絡(luò)圖。關(guān)鍵路徑法將項(xiàng)目分解成為多個(gè)獨(dú)立的活動(dòng)并確定每個(gè)活動(dòng)的工期，然后用邏輯關(guān)系（結(jié)束-開始、結(jié)束-結(jié)束、開始-開始和開始結(jié)束）將活動(dòng)連接，從而能夠計(jì)算項(xiàng)目的工期、各個(gè)活動(dòng)時(shí)間特點(diǎn)（最早最晚時(shí)間、時(shí)差）等。在關(guān)鍵路徑法的活動(dòng)上加載資源后，還能夠?qū)?xiàng)目的資源需求和分配進(jìn)行分析。關(guān)鍵路徑法是現(xiàn)代項(xiàng)目管理中最重要的一種分析工具。

關(guān)鍵路徑法_關(guān)鍵路徑法 -分類

根據(jù)繪制方法的不同，關(guān)鍵路徑法可以分為兩種：即箭線圖（ADM）和前導(dǎo)圖（PDM）。

箭線圖（ADM）法又稱為雙代號(hào)網(wǎng)絡(luò)圖法，它是以橫線表示活動(dòng)而以帶編號(hào)的節(jié)點(diǎn)連接活動(dòng)，活動(dòng)間可以有一種邏輯關(guān)系，結(jié)束-開始型邏輯關(guān)系。

在箭線圖中，有一些實(shí)際的邏輯關(guān)系無法表示，所以在箭線圖中需要引入虛工作的概念。

關(guān)鍵路徑法_關(guān)鍵路徑法 -箭線圖

箭線圖（ADM）要表示的是一個(gè)項(xiàng)目的計(jì)劃，所以其清晰的邏輯關(guān)系和良好的可讀性是

非常重要的，除了箭線圖（ADM）本身具有正確的邏輯性，良好的繪圖習(xí)慣也是必要的。因此在繪圖時(shí)遵守上面的這些規(guī)則就是非常重要的，另外，在繪圖時(shí)，一般盡量使用直線和折線，在不可避免的情況下可以使用斜線，但是要注意邏輯方向的清晰性。

繪制箭線圖時(shí)主要有以下一些規(guī)則：

⒈在箭線圖（ADM）中不能出現(xiàn)回路。如上文所述，回路是邏輯上的錯(cuò)誤，不符合實(shí)際的情況，而且會(huì)導(dǎo)致計(jì)算的死循環(huán)，所以這條規(guī)則是必須的要求。

⒉箭線圖（ADM）一般要求從左向右繪制。這雖然不是必須的要求，但是符合人們閱讀習(xí)慣，可以增加箭線圖（ADM）的可讀性。

⒊每一個(gè)節(jié)點(diǎn)都要編號(hào)，號(hào)碼不一定要連續(xù)，但是不能重復(fù)，且按照前后順序不斷增大。這條規(guī)則有多方面的考慮，在手工繪圖時(shí)，它能夠增加圖形的可讀性和清晰性，另外，在使用計(jì)算機(jī)運(yùn)行箭線圖（ADM）這一條就非常重要，因?yàn)樵谟?jì)算機(jī)中一般通過計(jì)算節(jié)點(diǎn)的時(shí)間來確定各個(gè)活動(dòng)的時(shí)間，所以節(jié)點(diǎn)編號(hào)不重復(fù)是必須的。

⒋一般編號(hào)不能連續(xù)，并且要預(yù)留一定的間隔。主要是為了在完成的箭線圖（ADM）中可能需要增加活動(dòng)，如果編號(hào)連續(xù)，新增加活動(dòng)就不能滿足編號(hào)由小到大的要求。

⒌表示活動(dòng)的線條不一定要帶箭頭，但是為了表示的方便，一般推薦使用箭頭。這一條主要是繪制箭線圖（ADM）時(shí)可以增加箭線圖（ADM）的可讀性。

⒍一般要求雙代號(hào)網(wǎng)絡(luò)圖要開始于一個(gè)節(jié)點(diǎn)，并且結(jié)束于一個(gè)節(jié)點(diǎn)。此要求可以在手工繪圖增加可讀性，而在計(jì)算機(jī)計(jì)算時(shí)，可以增加效率和結(jié)果的清晰性。

⒎在繪制網(wǎng)絡(luò)圖時(shí)，一般要求連線不能相交，在相交無法避免時(shí)，可以采用過橋法或者指向法等方法避免混淆。此要求主要是為了增加圖形的可讀性。

關(guān)鍵路徑法_關(guān)鍵路徑法 -起源

關(guān)鍵路徑法（CPM）

關(guān)鍵路徑法（CPM）最早出現(xiàn)于1956年，當(dāng)時(shí)美國杜邦（Du Pont）公司擁有一臺(tái)UNⅣAC 1 計(jì)算機(jī)，他們使用這臺(tái)計(jì)算機(jī)進(jìn)行他們公司幾乎所有的數(shù)據(jù)處理工作，但是仍然還有大量的剩余時(shí)間，杜邦（Du Pont）公司的管理層開始研究計(jì)算機(jī)在其它方面使用的可能性，因?yàn)楫?dāng)時(shí)電腦的費(fèi)用是非常高昂的，他們考慮工程計(jì)劃可能是應(yīng)用電腦的一個(gè)方向。

他們聯(lián)系了雷明頓蘭德（Remington Rand）公司的Macuchy 博士，幫他們解決計(jì)算機(jī)使用的問題，后者派出了年輕的數(shù)學(xué)家James E. Kelly去協(xié)助杜邦（Du Pont）公司解決問題，杜邦公司方面的負(fù)責(zé)人是Morgan Walker。

他們要解決的問題是在工程項(xiàng)目中工期和費(fèi)用之間的關(guān)系，他們研究的是如何能夠采取正確的措施，在減少工期的情況下能盡可能少的增加費(fèi)用。1957年5月7日，在特拉華州內(nèi)瓦克召開的一個(gè)會(huì)議正式確定開始新計(jì)劃技術(shù)的開發(fā)。Kelly借用了線性規(guī)劃的概念來解決項(xiàng)目計(jì)劃自動(dòng)計(jì)算的問題，簡單的說就是確定了每個(gè)活動(dòng)的工期和活動(dòng)間的邏輯關(guān)系，輸入電腦后就能自動(dòng)計(jì)算項(xiàng)目的工期，為了電腦的計(jì)算，Kelly在活動(dòng)間使用了i，j這樣的節(jié)點(diǎn)來表示活動(dòng)間的前后邏輯關(guān)系。

當(dāng)時(shí)遇到的一個(gè)問題是，杜邦公司的管理層并不理解Kelly所使用的方法，為了讓其他人能夠理解所使用方法的原理，Kelly就繪制了圖形來解釋電腦所作的工作，圖形以箭線表示活動(dòng)，以節(jié)點(diǎn)表示活動(dòng)間的邏輯關(guān)系，這就是最早的箭線圖（ADM）。

前面提到過，Kelly和Walker最初研究的目的是為了解決項(xiàng)目中工期和費(fèi)用之間關(guān)系的問題，所以在Kelly和Walker最初提出的方法中，也包括費(fèi)用的計(jì)劃方法，其做法是，在每個(gè)活動(dòng)上加載其相應(yīng)的費(fèi)用，從而得到整個(gè)項(xiàng)目的費(fèi)用，就能分析與進(jìn)度相關(guān)的費(fèi)用問題，這種做法與現(xiàn)用的方法沒有太大差別。但在當(dāng)時(shí)的情況下，項(xiàng)目收集費(fèi)用并分解到各個(gè)活動(dòng)上存在較大困難。所以，在之后的很長時(shí)期

內(nèi)，關(guān)鍵路徑法主要還是用于進(jìn)度的計(jì)劃和控制方面。Kelly和Walker還提出了資源加載和分配的方法，當(dāng)然也存在和費(fèi)用分析一樣的問題。

算法簡化

盡管存在這些問題，在1957年7月24日，他們已經(jīng)做了一個(gè)簡化的例子，稱為”George Fischer Works”，這個(gè)計(jì)劃包括了61條活動(dòng)，其中有8個(gè)時(shí)間限制和16條虛工作。在剛開發(fā)出這種方法時(shí)，他們將這種方法稱為Kelly-Walker法，而計(jì)劃中的關(guān)鍵線路，他們稱之為主鏈路（Main chain）。

根據(jù)Kelly和Walker的論文和其它相關(guān)書籍的記載，當(dāng)時(shí)他們一共進(jìn)行了三個(gè)試驗(yàn)對(duì)Kelly-Walker法進(jìn)行檢驗(yàn)。第一個(gè)試驗(yàn)是在1957年12月份，杜邦公司成立了一個(gè)測(cè)試小組對(duì)這種新的計(jì)劃方法測(cè)試，有一個(gè)傳統(tǒng)的計(jì)劃組與他們同時(shí)獨(dú)立對(duì)一個(gè)價(jià)值1000萬美元的化學(xué)設(shè)備項(xiàng)目進(jìn)行計(jì)劃。這個(gè)測(cè)試小組的成員沒有參與Kelly-Walker法的開發(fā)，但是在開始測(cè)試之前，他們接受40個(gè)小時(shí)的培訓(xùn)。此項(xiàng)目的計(jì)劃從初步設(shè)計(jì)的完成開始，在編制計(jì)劃時(shí)，他們首先將整個(gè)項(xiàng)目分解成一些較小的工作包，然后再將這些工作包最終分解成為活動(dòng)，項(xiàng)目共有800條活動(dòng)，其中包括400條施工活動(dòng)，150條采購和設(shè)計(jì)活動(dòng)。根據(jù)記載，在此項(xiàng)目中顯示出的Kelly-Walker法的最大優(yōu)勢(shì)在于，此項(xiàng)目在實(shí)施中出現(xiàn)了較大的變更，相對(duì)于傳統(tǒng)計(jì)劃方法，使用Kelly-Walker法更容易更新計(jì)劃，其工作量僅有最初建立計(jì)劃的10%，另外，在設(shè)計(jì)信息只有30%的情況下，能夠比較準(zhǔn)確的預(yù)測(cè)勞動(dòng)力，還有就是能夠比較準(zhǔn)確的識(shí)別關(guān)鍵的采購工作。

1958年，他們進(jìn)行了第二次試驗(yàn)，此試驗(yàn)所針對(duì)的是一個(gè)價(jià)值2000萬美元的化學(xué)設(shè)備項(xiàng)目，根據(jù)Kelly和Walker在1959年發(fā)表的論文，此次試驗(yàn)顯示的最主要的優(yōu)點(diǎn)是能夠比較容易的包含設(shè)計(jì)部分的計(jì)劃。

不過現(xiàn)在人們最常提及的一個(gè)試驗(yàn)是他們隨后進(jìn)行的維護(hù)設(shè)備的試驗(yàn)，在此項(xiàng)目中，他們使用Kelly-Walker法進(jìn)行分析和計(jì)劃，使得設(shè)備維護(hù)時(shí)間減少了25%。

培訓(xùn)和推廣

1959年，Kelly和Walker共同發(fā)表了”Critical Path Planning and Scheduling” 論文，在這篇長達(dá)25頁的論文中，Kelly和Walker不僅闡述了關(guān)鍵路徑法的基本原理，還提出了資源分配與平衡，費(fèi)用計(jì)劃的方法。我們今天所使用的方法的原理，與Kelly和Walker在論文中提出的方法，并沒有原則上的不同。

不過隨后關(guān)鍵路徑法的發(fā)展并不是很順利，杜邦公司開發(fā)此項(xiàng)技術(shù)的領(lǐng)導(dǎo)層更換之后，不再使用這項(xiàng)技術(shù)，而雷明頓蘭德公司也認(rèn)為這項(xiàng)技術(shù)沒有太大前途。

對(duì)于關(guān)鍵路徑法的發(fā)展起到重要作用的是Mauchly博士和Kelly隨后成立的Mauchly合伙公司。在60年代初期，在Kelly的帶領(lǐng)下，此公司進(jìn)行了大量的關(guān)鍵路徑法的培訓(xùn)和推廣工作。

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

應(yīng)用

在60年代初期，PERT的發(fā)展比較迅速，據(jù)統(tǒng)計(jì)，到1964年，關(guān)于PERT的參考書目和論文達(dá)到了1000多種。到1961年，各種基于PERT的類似的方法出現(xiàn)，如PERT/Cost,PERT-RAMPS（Resource Allocation & Multi-Project Schedule），MAPS，SCANS，TOPS，PEP，TRACE，LESS和PAR等。其中PEP法是將甘特圖的活動(dòng)賦以邏輯關(guān)系，這是計(jì)劃軟件一般采用的一種圖形輸出方法。1962年的時(shí)候，時(shí)任美國國防部長MacNamara在起草一項(xiàng)法令時(shí)，指出計(jì)劃評(píng)審法和關(guān)鍵路徑法同時(shí)并存的局面容易引起混淆，以后國防部的所有部門一律使用計(jì)劃評(píng)審法（PERT），這在當(dāng)時(shí)對(duì)于關(guān)鍵路徑法的提倡者是一個(gè)重大打擊，不過在隨后的發(fā)展中，關(guān)鍵路徑法（CPM）逐漸占了優(yōu)勢(shì)，真正使用計(jì)劃評(píng)審法的其實(shí)已經(jīng)很少。而且即使是在當(dāng)時(shí)，很多所謂的計(jì)劃評(píng)審法（PERT），其實(shí)質(zhì)其實(shí)是關(guān)鍵路徑法（CPM）。如美國航空局（NASA）當(dāng)時(shí)使用的NASA-PERT，實(shí)際就是關(guān)鍵路徑法（CPM）。

無論是關(guān)鍵路徑法（CPM）還是計(jì)劃評(píng)審法（PERT），最初使用的表示方法都是箭線法（ADM），在之后很長的一段時(shí)間箭線法（ADM）都是人們主要使用的方法，直到70年代以后，前導(dǎo)圖（PDM）才開始逐漸流行起來，但是箭線法（ADM）仍然使用極為廣泛。在90年代以后，美國Primavera公司開發(fā)出其Windows版本的計(jì)劃管理軟件時(shí)，只采用前導(dǎo)圖（PDM）作為其計(jì)算平臺(tái)，從根本上改變了這一局面，從此以后，前導(dǎo)圖（PDM）成了人們主要使用的方法，而箭線圖（ADM）則很少使用。

前導(dǎo)圖（PDM）的發(fā)展

在早期對(duì)于前導(dǎo)圖（PDM）的發(fā)展起到重要作用的是美國斯坦福大學(xué)的John W. Fondahl,他是60年代初期的非計(jì)算機(jī)關(guān)鍵路徑法的權(quán)威，1961年他發(fā)表了一篇題為”A Non-computer Approach to Critical Path Methods for the Construction Industry”，在這篇論文中，他闡述了前導(dǎo)圖系統(tǒng)，并把它作為一種效率比較高的手工繪制關(guān)鍵路徑法的方法，因?yàn)楫?dāng)時(shí)使用計(jì)算機(jī)運(yùn)行CPM是非常昂貴的。Fondahl從1958年開始作為斯坦福大學(xué)的成員，受美國海軍委托為其研究提高生產(chǎn)效率的方法。其中最主要的成果就是這份論文，這份論文當(dāng)時(shí)一共出售了20000份。

在這份論文中，根據(jù)習(xí)慣使用的流程圖方法，F(xiàn)ondahl提出了以節(jié)點(diǎn)表示活動(dòng)以連接線表示活動(dòng)間的邏輯關(guān)系。論文論述了流程圖的簡易性和使用手算在較少的人力投入下采用關(guān)鍵路徑法的可能性，同時(shí)論文也論述了費(fèi)用工期互為反比的問題。斯坦福大學(xué)之后繼續(xù)研究了前導(dǎo)圖（PDM）的手工進(jìn)度更新的問題，并在1964年發(fā)表了相關(guān)的技術(shù)報(bào)告。

雖然Fondahl博士極力強(qiáng)調(diào)他提出的方法是為了手工計(jì)算關(guān)鍵路徑法，但是H.B Zachry公司在1962年開始研究將前導(dǎo)圖法用于計(jì)算機(jī)上，1963年3月他們與IBM公司聯(lián)合進(jìn)行該項(xiàng)研究，之后形成了IBM的計(jì)劃軟件，名為”Project Control System（PCS）”。該系統(tǒng)還是第一個(gè)在計(jì)劃中引入時(shí)間間隔（LAG）的軟件。雖然前導(dǎo)圖法最初被應(yīng)用于大型機(jī)，但是隨后被廣泛應(yīng)用于小型機(jī)和個(gè)人電腦上的軟件，這一趨勢(shì)使得前導(dǎo)圖（PDM）逐漸成為主要使用的方法，在國外前導(dǎo)圖（PDM）基本已經(jīng)成為唯一在使用的方法，而箭線圖（ADM）只有在教學(xué)和培訓(xùn)中還有時(shí)用到。而發(fā)展勢(shì)頭曾一度壓過關(guān)鍵路徑法（CPM）的計(jì)劃評(píng)審技術(shù)（PERT），正在使用的已經(jīng)很少了。

在美國發(fā)展出關(guān)鍵路徑法（CPM）和計(jì)劃評(píng)審技術(shù)（PERT）的同時(shí)，其它一些國家如歐洲和英國等，也曾經(jīng)開發(fā)出一些類似的項(xiàng)目管理技術(shù)，但是關(guān)于這些技術(shù)的記載已經(jīng)很少。

關(guān)鍵路徑法（CPM）最初被開發(fā)是用于項(xiàng)目管理，不過，在發(fā)展過程中，它逐漸在工程項(xiàng)目的合同索賠和糾紛解決上起到重要作用。最早在訴訟中涉及到要求使用關(guān)鍵路徑法（CPM）是1972（Appeal of Minmar Builders,Inc,GSBCA No. 3430,72-2 BOA）年，在此案例中，法庭由于承包商沒有使用關(guān)鍵路徑法（CPM）而拒絕了承包商的索賠，因?yàn)槠涫褂玫臋M道圖不能顯示具體的活動(dòng)是否在關(guān)鍵線路上，從而無法判斷活動(dòng)耽誤對(duì)于整體的影響。之后，關(guān)鍵路徑法（CPM）逐漸成為工期延誤索賠中必須的做法，并逐漸形成了很多專門的分析方法，甚至有很多人專業(yè)從事工期延誤分析的工作。

關(guān)鍵路徑法_關(guān)鍵路徑法 -時(shí)間參數(shù)

在關(guān)鍵路徑法中，一般有以下一些時(shí)間參數(shù)：

最早開始時(shí)間（Early Start）活動(dòng)最早開始時(shí)間由所有前置活動(dòng)中最后一個(gè)最早結(jié)束時(shí)間確定。

最早結(jié)束時(shí)間（Early Finish）活動(dòng)的最早結(jié)束時(shí)間由活動(dòng)的最早開始時(shí)間加上其工期確定。

最遲結(jié)束時(shí)間（Late Finish）一個(gè)活動(dòng)在不耽誤整個(gè)項(xiàng)目的結(jié)束時(shí)間的情況下能夠最遲結(jié)束的時(shí)間。它等于所有緊后工作中最早的一個(gè)最晚開始時(shí)間。

最遲開始時(shí)間（Late Start）一個(gè)活動(dòng)在不耽誤整個(gè)項(xiàng)目的結(jié)束時(shí)間的情況下能夠最遲開始的時(shí)間。它等于活動(dòng)的最遲結(jié)束時(shí)間減去活動(dòng)的工期。

總時(shí)差（Total Float) 指一項(xiàng)活動(dòng)在不影響整體計(jì)劃工期的情況下最大的浮動(dòng)時(shí)間。

自由時(shí)差（Free Float）指活動(dòng)在不影響其緊后工作的最早開始時(shí)間的情況下可以浮動(dòng)的時(shí)間。

如果是對(duì)于箭線圖法，用到的時(shí)間參數(shù)還常有：

最早節(jié)點(diǎn)時(shí)間（Early Event Occurrence Time）最早節(jié)點(diǎn)時(shí)間由其前置活動(dòng)中最晚的最早結(jié)束時(shí)間確定。

最遲節(jié)點(diǎn)時(shí)間（Late Event Occurrence Time）最遲節(jié)點(diǎn)時(shí)間由其后置活動(dòng)中最早的最遲開始時(shí)間確定。

關(guān)鍵路徑法_關(guān)鍵路徑法 -時(shí)間計(jì)算

在進(jìn)行計(jì)算時(shí)，箭線圖和前導(dǎo)圖的計(jì)算過程有所不同。

正推法

箭線圖（ADM）的計(jì)算一般有正推法（Forward Pass）和逆推法（Backward Pass）兩種，正推法用于計(jì)算活動(dòng)和節(jié)點(diǎn)的最早時(shí)間，其算法如下：

⒈設(shè)置箭線圖（ADM）中的第一個(gè)節(jié)點(diǎn)的時(shí)間，如設(shè)置為1。

⒉選擇一個(gè)開始于第一個(gè)節(jié)點(diǎn)的活動(dòng)開始進(jìn)行計(jì)算。

⒊令活動(dòng)最早開始時(shí)間等于其開始節(jié)點(diǎn)的最早時(shí)間。

⒋在選擇的活動(dòng)的最早開始時(shí)間上加上其工期，就是其最早結(jié)束時(shí)間。

⒌比較此活動(dòng)的最早結(jié)束時(shí)間和此活動(dòng)結(jié)束節(jié)點(diǎn)的最早時(shí)間。如果結(jié)束節(jié)點(diǎn)還沒有設(shè)置時(shí)間，則此活動(dòng)的最早結(jié)束時(shí)間就是該結(jié)束節(jié)點(diǎn)的最早時(shí)間；如果活動(dòng)的結(jié)束時(shí)間比結(jié)束節(jié)點(diǎn)的最早時(shí)間大，則取此活動(dòng)的最早結(jié)束時(shí)間作為節(jié)點(diǎn)的最早時(shí)間；如果此活動(dòng)的最早結(jié)束時(shí)間小于其結(jié)束節(jié)點(diǎn)的最早時(shí)間，則保留此節(jié)點(diǎn)時(shí)間作為其最早時(shí)間。

⒍檢查是否還有其它活動(dòng)開始于此節(jié)點(diǎn)，如果有，則回到步驟3進(jìn)行計(jì)算；如果沒有，則進(jìn)入下一個(gè)節(jié)點(diǎn)的計(jì)算，并回到步驟3開始，直到最后一個(gè)節(jié)點(diǎn)。

逆推法

活動(dòng)和節(jié)點(diǎn)的最遲時(shí)間采用逆推法（Backward Pass）計(jì)算，逆推法（Backward Pass）一般從項(xiàng)目的最后一個(gè)活動(dòng)開始計(jì)算，直到計(jì)算到第一個(gè)節(jié)點(diǎn)的時(shí)間為止，在逆推法的計(jì)算中，首先令最后一個(gè)節(jié)點(diǎn)的最遲時(shí)間等于其最早時(shí)間，然后開始計(jì)算，具體的計(jì)算步驟如下所示：

⒈設(shè)置最后一個(gè)節(jié)點(diǎn)的最遲時(shí)間，令其等于正推法計(jì)算出的最早時(shí)間。

⒉選擇一個(gè)以此節(jié)點(diǎn)為結(jié)束節(jié)點(diǎn)的活動(dòng)進(jìn)行計(jì)算。

⒊令此活動(dòng)的最遲結(jié)束時(shí)間等于此節(jié)點(diǎn)的最遲時(shí)間。

⒋從此活動(dòng)的最遲結(jié)束時(shí)間中減去其工期，得到其最遲開始時(shí)間。

⒌比較此活動(dòng)的最遲開始時(shí)間和其開始節(jié)點(diǎn)的最遲時(shí)間，如果開始節(jié)點(diǎn)還沒有設(shè)置最遲時(shí)間，則將活動(dòng)的最遲開始時(shí)間設(shè)置為此節(jié)點(diǎn)的最遲時(shí)間，如果活動(dòng)的最遲開始時(shí)間早于節(jié)點(diǎn)的最遲時(shí)間，則將此活動(dòng)的最遲開始時(shí)間設(shè)置為節(jié)點(diǎn)的最遲時(shí)間，如果活動(dòng)的最遲開始時(shí)間遲于節(jié)點(diǎn)的最遲時(shí)間，則保留原節(jié)點(diǎn)的時(shí)間作為最遲時(shí)間

⒍檢查是否還有其它活動(dòng)以此節(jié)點(diǎn)為結(jié)束節(jié)點(diǎn)，如果有則進(jìn)入第二步計(jì)算，如果沒有則進(jìn)入下一個(gè)節(jié)點(diǎn)，然后進(jìn)入第二步計(jì)算，直至最后一個(gè)節(jié)點(diǎn)。

⒎第一個(gè)節(jié)點(diǎn)的最遲時(shí)間是本項(xiàng)目必須要開始的時(shí)間，假設(shè)取最后一個(gè)節(jié)點(diǎn)的最遲時(shí)間和最早時(shí)間相等，則其值應(yīng)該等于1。

關(guān)鍵路徑法_關(guān)鍵路徑法 -公式計(jì)算

上面介紹了活動(dòng)的最早和最遲時(shí)間的計(jì)算方法，以上的過程可以用比較簡單的公式來表達(dá)。

節(jié)點(diǎn)計(jì)算法

上面所講述的方法，我們一般稱為節(jié)點(diǎn)計(jì)算法，節(jié)點(diǎn)和活動(dòng)的最早時(shí)間按照正推法進(jìn)行計(jì)算，起點(diǎn)節(jié)點(diǎn)未規(guī)定時(shí)間時(shí)，我們?nèi)∑鋾r(shí)間為1，即

ETi=1（i=1）

對(duì)于任意一個(gè)節(jié)點(diǎn)，如果其之前只有一條活動(dòng)時(shí)，則其最早時(shí)間按照下式計(jì)算，

ETj= ETi+Di-j

如果該節(jié)點(diǎn)之前有多條活動(dòng)時(shí)，則其最早時(shí)間按照下式計(jì)算，

ETj= max{ETi+Di-j}

其中Di-j為活動(dòng)i-j的工期

對(duì)于活動(dòng)的最早時(shí)間，最早開始時(shí)間為：

ESi-j=ETi

最早結(jié)束時(shí)間為

EFi-j= ESi-j+ Di-j

計(jì)劃的總工期

T=ETn-1

節(jié)點(diǎn)和活動(dòng)的最遲時(shí)間以逆推法計(jì)算，計(jì)算時(shí)，首先令最后一個(gè)節(jié)點(diǎn)的最遲時(shí)間等于其最早時(shí)間，即

LTn=ETn

對(duì)于其之后只有一條活動(dòng)的節(jié)點(diǎn)，最遲時(shí)間如下式所示

LTi=LTj-Di-j

對(duì)于其之后有多條活動(dòng)的節(jié)點(diǎn)，最遲時(shí)間如下式所示

LTj=min{ LTj-Di-j}

工作i-j的最遲完成時(shí)間以下式計(jì)算，

LFi-j=LTj

最遲開始時(shí)間為

LSi-j=LFj- Di-j

工作計(jì)算法

以上的算法是節(jié)點(diǎn)計(jì)算法，另外，也可以采用一種叫做工作計(jì)算法的方法進(jìn)行活動(dòng)時(shí)間的計(jì)算，具體如下。

對(duì)于最早時(shí)間，采用正推法計(jì)算。在沒有指定節(jié)點(diǎn)的開始時(shí)間時(shí)，則起點(diǎn)開始活動(dòng)的最早開始時(shí)間定為1，即

ESi-j=1

當(dāng)工作i-j只有一條緊前工作h-i時(shí)，其最早開始時(shí)間按如下公式計(jì)算

ESi-j=ESh-i+ Dh-i

當(dāng)工作i-j有多條緊前工作時(shí)，其最早開始時(shí)間按照以下公式計(jì)算

ESi-j=max {ESh-j+ Dh-i}

工作i-j的最早完成時(shí)間按照下式計(jì)算

EFi-j=ESi-j+ Di-j

網(wǎng)絡(luò)計(jì)劃的計(jì)算工期按照下式確定

T=max {EFi-n}-1

活動(dòng)的最遲結(jié)束時(shí)間和最遲開始時(shí)間需要采用逆推法計(jì)算。

以終點(diǎn)節(jié)點(diǎn)為箭頭節(jié)點(diǎn)的活動(dòng)的最遲完成時(shí)間按照網(wǎng)絡(luò)計(jì)劃的工期確定，即

LFi-j=T+1

其它活動(dòng)的最遲開始時(shí)間按照下式計(jì)算

LFi-j=min {LFj-k- Dj-k}

活動(dòng)的最遲開始時(shí)間以下式確定

LSi-j=LFi-j- Di-j

對(duì)于總時(shí)差和自由時(shí)差可以采用如下的公式計(jì)算。

總時(shí)差可以按照下式計(jì)算：

TFi-j= LSi-j- ESi-j

或者

TFi-j= LFi-j- EFi-j

當(dāng)工作i-j有緊后工作j-k時(shí)，自由時(shí)差可以按照下式計(jì)算：

FFi-j=ESi-k- ESi-j- Di-j

或者

FFi-j=ESj-k-EFi-j

由于引入了多種邏輯關(guān)系，前導(dǎo)圖（PDM）的時(shí)間計(jì)算和箭線圖（ADM）有一些差別。除了前導(dǎo)圖（PDM）中不存在節(jié)點(diǎn)最早時(shí)間和最遲時(shí)間，在箭線圖（ADM）中提及的其它時(shí)間參數(shù)也都適合前導(dǎo)圖（PDM）。

正推法計(jì)算

對(duì)于活動(dòng)的最早開始和最早結(jié)束時(shí)間，采用正推法計(jì)算，其算法如下所示：

⒈將第一個(gè)活動(dòng)的最早開始時(shí)間設(shè)置為1.

⒉在活動(dòng)的最早開始時(shí)間上加上其工期，得到活動(dòng)的最早結(jié)束時(shí)間。

⒊根據(jù)該活動(dòng)與后置活動(dòng)的邏輯關(guān)系，計(jì)算后置活動(dòng)應(yīng)該的最早開始時(shí)間，并與其已有的最早開始時(shí)間對(duì)比，如果其后置活動(dòng)還沒有設(shè)置最早開始時(shí)間，則將此時(shí)間設(shè)為其最早開始時(shí)間，如果此時(shí)間早于其后置活動(dòng)已有的最早開始時(shí)間，則保留后置活動(dòng)的原有最早開始時(shí)間，如果此時(shí)間遲于其后置活動(dòng)已有的最早開始時(shí)間，則將此時(shí)間設(shè)置為后置活動(dòng)的最遲開始時(shí)間。

⒋重復(fù)步驟2和3，直到所有活動(dòng)的時(shí)間被計(jì)算完為止。

對(duì)于以上所示的最早時(shí)間的計(jì)算過程，可以以公式的形式表示如下：

當(dāng)活動(dòng)間的邏輯關(guān)系為SS，則計(jì)算如下

ESj=max{ ESi+ STS}

當(dāng)活動(dòng)間的邏輯關(guān)系為FS，則計(jì)算如下

ESj= max{ESi+ Di+ FTS}

當(dāng)活動(dòng)間的邏輯關(guān)系為FF，計(jì)算如下

ESj= max{ESi+ Di- Dj+FTF}

當(dāng)活動(dòng)間的邏輯關(guān)系為SF，計(jì)算如下

ESj=max{ ESi- Dj+STF}

在計(jì)算出各個(gè)活動(dòng)的最早開始和結(jié)束時(shí)間之后，就可以計(jì)算活動(dòng)的自由時(shí)差，在計(jì)算前導(dǎo)圖（PDM）的自由時(shí)差時(shí)應(yīng)注意，由于引入了多種邏輯關(guān)系，并且活動(dòng)間可以存在延時(shí)，所以其計(jì)算方法與箭線圖（ADM）的計(jì)算方法不一樣。

計(jì)算自由時(shí)差

對(duì)于前導(dǎo)圖（PDM）的活動(dòng)間，除了延時(shí)還可以存在時(shí)間間隔（LAG），一般可以按照下面的方式計(jì)算。

當(dāng)活動(dòng)間的邏輯關(guān)系為SS，則計(jì)算如下

LAGi-j= ESj- ESi- STS

當(dāng)活動(dòng)間的邏輯關(guān)系為FS，則計(jì)算如下

LAGi-j= ESj- EFi- FTS

當(dāng)活動(dòng)間的邏輯關(guān)系為FF，計(jì)算如下

LAGi-j= EFj- EFi- FTF

當(dāng)活動(dòng)間的邏輯關(guān)系為SF，計(jì)算如下

LAGi-j= EFj- ESi- STF

則對(duì)于任意一個(gè)活動(dòng)，其自由時(shí)差為

FFi=min{ LAGi-j}

最后一個(gè)活動(dòng)的自由時(shí)差為0.

對(duì)于總時(shí)差，終點(diǎn)節(jié)點(diǎn)的總時(shí)差為0，對(duì)于其它任意一個(gè)節(jié)點(diǎn)，總時(shí)差按照下式進(jìn)行計(jì)算

TFi=min{TFj+ LAGi-j}

對(duì)于任意一個(gè)活動(dòng)的最晚開始時(shí)間可以由其最早開始時(shí)間加上總時(shí)差得到，同樣，其最晚開始時(shí)間可以由最早結(jié)束時(shí)間加上其總時(shí)差得到，公式表示如下

LSi=ESi+TFi

LFi=EFi+TFi

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/8103380103/78136.html