網絡計劃工期優化的分析方法

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

關鍵詞:網絡計劃 工期優化 CPM

中圖分類號:TN915文獻標識碼:A

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

一、定義

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

二、初始網絡計劃關鍵線路的判定

(一)原理。

圖1網絡計劃示例

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

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

(二)步驟。

(1)假定P(1)=0

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

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

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

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

三、壓縮過程中新關鍵路線的判定

(一)原理 在壓縮過程中應遵守的原則。

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

2、在優化過程中出現多條關鍵線路時，必須壓縮成同一數值。

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

(二)步驟。

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

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

3、重復2步驟，檢查k之后的節點，m之后的節點……至終點，

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

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

四、算例

圖2 初始網絡計劃圖

(一)初始網絡計劃關鍵線路的判定。

P標號如圖1中小方框， 值如下表:

(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 。

(二)壓縮及壓縮過程中新關鍵路線的判定

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

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

(7)=6，且7節點位于關鍵路線上。P(7)=32，(7)新增節點位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工序5-6壓縮兩天后的網絡計劃圖

關鍵路線還可以壓縮一天。將2-5，3-6，同時壓縮一天，5節點 (5)不產生新增節點。6，7，8，9節點 值也未出現新增節點。故此壓縮不出現新關鍵路線。

最終壓縮情況及關鍵路線如圖3:

圖4最終壓縮后的網絡計劃圖

五、結束語

本文研究了CPM 網絡計劃工期優化時的關鍵路線確定問題和新關鍵路線出現規律問題，參照尋找最短路線的Dijkstra算法提出了一種運用分析解決工期優化問題的方法。該方法不需要計算網絡計劃時間參數，省了一半的計算量，也降低了理解難度，且簡便易行。對于處在工程一線的管理人員，在手邊沒有計算機及相應的程序時，這種直觀分析的方法尤為有幫助。

(作者單位:河海大學商學院2007級工程管理專業)

參考文獻:

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

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

[3]張立輝，乞建勛，仲剛.CPM網絡中關鍵工序被壓縮情況下新關鍵路線規律研究.中國管理科學2008，16.

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