網(wǎng)絡計劃工期優(yōu)化的分析方法

摘 要: 工期優(yōu)化過程中主要問題是初始網(wǎng)絡計劃關鍵線路的判定及壓縮過程中新關鍵路線的判定。本文針對現(xiàn)有方法計算量大、涉及概念多、理解不便的缺點，在借鑒Dijkstra算法的基礎上提出了一種新方法，給出關鍵線路的判定和壓縮過程中新關鍵路線判定的原理和步驟，最后結合算例加以說明。

關鍵詞: 網(wǎng)絡計劃 工期優(yōu)化 CPM

網(wǎng)絡計劃技術是利用網(wǎng)絡圖對項目的各項工作進度進行安排和控制，以保證實現(xiàn)預定目標的科學的計劃管理技術。產(chǎn)生于20世紀50年代的關鍵路線法CPM(Critical Path Method)在世界各國的工程項目及生產(chǎn)中得到了廣泛應用。[1]網(wǎng)絡計劃的工期優(yōu)化，核心是對關鍵路線上關鍵工序的持續(xù)時間進行壓縮，使計算工期小于或等于計劃工期。壓縮前，需要尋找出給定初始網(wǎng)絡計劃的關鍵路線，壓縮后，網(wǎng)絡計劃可能出現(xiàn)新的關鍵路線。初始網(wǎng)絡計劃關鍵線路的尋找目前多用總時差為最小或為零的判別方法確定。乞建勛、張立輝等基于安全時差、節(jié)點時差、干擾時差提出利用前主鏈、后主鏈、特征路線、替代關鍵路線等定理，[2]尋找新的關鍵線路。[3]該方法涉及的概念、定理相當多，沒有一定的理論基礎則難以理解。基于此，本文在借鑒Dijkstra算法的基礎上，提出一種便于直觀理解和分析的方法。

1.定義

設有一網(wǎng)絡計劃，源點編號1，終點編號n，中間節(jié)點編號為2，3，4，…，n-1。每個節(jié)點的P標號表示從源點到該節(jié)點的最長距離，則P(n)即為計算工期。Wij表示工序i—j的持續(xù)時間。λ(i)表示i獲得P標號所使用的緊前節(jié)點編號。

2.初始網(wǎng)絡計劃關鍵線路的判定

2.1原理

如圖1，對于j節(jié)點，其緊前節(jié)點a，b，…，s，其相應的P標號為P(a)，P(b)，…，P(s)，則各路線最長距離的情況如下表。

由此，我們可得出從源點到節(jié)點j的最長距離為max{P(a)+Waj，P(b)+Wbj，…，P(s)+Wsj}，且取得最大值時的路線中j的緊前節(jié)點即為λ(j)。追溯λ值至源點1，即可得到從源點到節(jié)點j的最長路線。

2.2步驟

(1)假定P(1)=0;

(2)對1的緊后工作進行P標號，P(i)=W1i;

(3)對于之后的節(jié)點j，如果其所有的緊前節(jié)點都已獲得P標號，則該節(jié)點的P標號取max{緊前節(jié)點的P標號+相應的連接工序的持續(xù)時間}，并且將取最大值時的緊前節(jié)點的編號賦值給λ(j);

(4)如此將所有節(jié)點進行P標號，算出P(n)，即為計算工期;

(5)關鍵路線的確定，從終點節(jié)點開始，尋找該節(jié)點λ值指向的前一個節(jié)點，直至源點，所形成的路線即為關鍵路線。

3.壓縮過程中新關鍵路線的判定

3.1原理

在壓縮過程中應遵守以下原則。

(1)不能將關鍵工作壓縮成非關鍵工作;

(2)在優(yōu)化過程中出現(xiàn)多條關鍵線路時，必須壓縮成同一數(shù)值。

根據(jù)上述壓縮原則，若將關鍵工序i—j的持續(xù)時間壓縮，則j節(jié)點的P標號必定改變，λ(j)也可能因此而增加新的節(jié)點，即從源點到j多了一條新的最長路線。而以P(j)為計算依據(jù)的節(jié)點的P標號也將會改變，λ指向的節(jié)點也可能有新增節(jié)點的情況。如此一直傳遞作用下去。

3.2步驟

(1)在被壓縮的關鍵工序i—j的可壓縮范圍內，若其壓縮一個單位(天)時，λ(j)出現(xiàn)新增節(jié)點，則從源點至j節(jié)點又多了條最長路線，追溯該新增節(jié)點的λ值至源點即可得出該路線。不管λ(j)有沒有出現(xiàn)新增節(jié)點都進行下一個檢查步驟。

(2)檢查j節(jié)點編號之后的節(jié)點，若某個節(jié)點k的λ值為j且k節(jié)點處于原關鍵路線上，則檢查該節(jié)點λ的值有沒有新增節(jié)點。若有，則追溯該新增節(jié)點的λ值至源點得出該路線。不管該步驟有沒有出現(xiàn)新的路線，都進行下個步驟。

(3)重復(2)步驟，檢查k之后的節(jié)點，m之后的節(jié)點……至終點。

(4)找出所有的新路線后，求出每條路線上工序的總共可壓縮時間，取各條路線總共可壓縮時間的最小值。在這個最小值范圍內，將工序進一步壓縮，然后重復(2)(3)的檢查步驟。

(5)如此逐漸壓縮至不能壓縮為止。

4.算例

4.1初始網(wǎng)絡計劃關鍵線路的判定

算例見圖2。P標號如圖2中小方框，λ值如下表:

λ(9)=8，λ(8)=6或7，λ(6)=5，λ(7)=6，λ(5)=2，λ(2)=1。則關鍵線路有兩條:1—2—5—6—8—9和1—2—5—6—7—8—9。

4.2壓縮及壓縮過程中新關鍵路線的判定

關鍵路線上仍可壓縮的工序為2—5和5—6。

將5—6工序壓縮2天時，6節(jié)點P(6)=29，λ(6)新增節(jié)點為3，查λ值表可追溯得新增路線為1—2—3—6。

λ(7)=6，且7節(jié)點位于關鍵路線上。P(7)=32，λ(7)新增節(jié)點位5，查λ值表可追溯得新增路線為1—2—5—7。

此時可得新增關鍵路線:1—2—3—6—8—9，1—2—3—6—7—8—9，1—2—5—7—8—9。此時壓縮情況如圖3。

關鍵路線還可以壓縮一天。將2—5，3—6同時壓縮一天，5節(jié)點λ(5)不產(chǎn)生新增節(jié)點。6、7、8、9節(jié)點λ值也未出現(xiàn)新增節(jié)點。故此壓縮不出現(xiàn)新關鍵路線。最終壓縮情況及關鍵路線如圖4。

5.結語

本文研究了CPM網(wǎng)絡計劃工期優(yōu)化時的初始網(wǎng)絡計劃關鍵線路的判定和壓縮過程中新關鍵路線的判定問題，在借鑒Dijkstra算法提出了一種運用分析解決工期優(yōu)化問題的方法。該方法不需要計算網(wǎng)絡計劃時間參數(shù)，省卻了一半的計算量，也降低了理解難度，且簡便易行。對于處在工程一線的管理人員，在手邊沒有計算機及相應的程序時，這種直觀分析的方法尤為有幫助。

參考文獻:

[1]Avraham Shtub.Project segmentation-a tool for project management[J].International Journal of Project Management，1997，15，(1):15-19.

[2]張立輝，乞建勛.運用總時差求CPM網(wǎng)絡中次關鍵路線的方法研究[J].運籌與管理，2008，17，(4):79-83.

[3]張立輝，乞建勛，仲剛.CPM網(wǎng)絡中關鍵工序被壓縮情況下新關鍵路線規(guī)律研究[J].中國管理科學，2008，16:12-16.

[4]王卓甫，談飛，張云寧，歐陽紅祥.工程項目管理理論、方法與應用[M].北京:中國水利水電出版社，2007:80.