關鍵路徑在某工程項目管理中的應用

熊衛民

【摘 要】 本文利用數據結構中求解關鍵路徑的相關方法，解決了在實際工程項目的計劃設計時，我們通常所關心的兩個問題：整個工程的竣工最少需要多少時間；影向整個工程進度按時完工的主要子工程是哪些。

【中圖分類號】 G6425 【文獻標識碼】 A 【文章編號】 2095-3089（2017）13-00-01

一、關鍵路徑的基本概念

在數據結構中，如果我們用頂點表示事件的發生（比如：某項活動的開始或結束），用邊表示活動（活動的實施），邊所對應的權值表示活動所持續的時間代價，則稱這樣邊帶權的有向圖為AOE（Activity on edge network）網。AOE網通常在工程或項目管理中有著實際的應用。

如果用AOE網來描述一項工程或項目實施計劃的話，那么，邊可以表示子工程或子活動，有向邊（也稱為弧）表示子工程實施的先后次序，邊所帶的權表示子工程實施的持續時間代價。我們在設計工程施工計劃時，有時必須關心整個工程竣工最少需要多少時間；哪些子工程的施工進度會影響到整個工程的按時完工，如果加速這些子工程的施工進度能否提高整個工程的效率。因此，有必要對子工程的施工次序、子工程互相之間的影響關系、預計完成的時間有一個預測（估算），同時要確定影響整個工程進度的關鍵子工程有哪些。這就形成了工程施工的AOE網。

從數據結構中我們得知，AOE網是一個有向無環結構的圖，AOE網應具有下面兩個性質：

（1）只有在某一個頂點所表示的事件發生，其后的從該頂點出發的各個有向邊所代表的活動才能開始進行。

（2）只有當指向某一頂點的所有邊代表的活動全部結束時，該頂點所代表的事件才能發生。

并且，每一個AOE網中只能有一個頂點的入度（指向該頂點的邊的條數）為0，稱之為源點；每一個AOE網中也只能有一個出度（出自該頂點的邊的條數）為0，稱之為匯點。

二、關鍵路徑在某工程管理中的應用

下面我們結合某工程項目的實施計劃情況，介紹關鍵路徑在計算整個工期以及確定重點子工程問題中的應用過程。某工程項目中共有15項子工程，每個子工經過估算的施工時間、前期子工程等情況見表1。

下面就數據結構中求解關鍵路徑、關鍵活動（即子工程）的相關算法，簡要介紹整個工程的竣工最少需要多少時間、影響整個工程進度的主要子工程有哪些。

1、計算方法

因為在同一工程項目中的一些子工程是可以同時施工的，所以，完成整個工程所需要的時間應該是從源點到匯點之間的最大路徑長度（即該路徑上所有子工程施工時間之和）。

在AOE網中求解關鍵路徑的方法：

（1）計算事件最早發生的時間

設Ve[k]為第k個事件的最早發生時間，根據AOE網的性質，只有當第k個子工程的前期子工程全部結束時，第k個子工程才能開工，即第k個子工程的最早時間才能確定。而子工程的最早結束時間為ve[j]+dut（）。計算方法如下：

Ve[1]=0

Ve[k]=max{ve[j]+dut（）} 表示從第j個頂點到第k個頂點的一條邊

（2）計算事件最晚發生的時間

設Vl[k]是在不影響整個工程按時完工的前提下，第k個事件的最晚開工時間；n為最后一個事件（本例中竣工發生的事件，亦即第11個事件）。計算方法如下：

Vl[n]=ve[n]

Vl[k]=min{vl[j]-dut（）}

（3）計算活動（即子工程）的最早開工時間

設e[i]為第i項活動（ai）的最早開始時間。活動在AOE網中對應著一條弧，用所表示的一項活動。依據AOE網的性質，只有事件vk發生了，活動ai才能開工。即，活動ai的最早開工時間應等于事件vk的最早發生時間。計算方法如下：

e[i]=ve[k]

（4）計算活動ai的最晚開始時間

設l[i]為活動ai的最晚開始時間。最晚開始時間是指在不影響整個工程按時完工的前提下，必須開工的最遲時間。計算方法如下：

l[i]=vl[j]-dut（）

根據上述方法和公式分別計算每個事件的最早、最晚發生時間（略）以及表1中各項子工程的最早、最晚開工時間（見表2）

2、確定關鍵路徑與關鍵活動

根據AOE網求解關鍵路徑及關鍵活動的算法可知：凡是最早開工時間與最晚開工時間相等的子工程即為關鍵活動（關鍵子工程），從上表中可以看出zgc2、zgc5、zgc9、zgc13、zgc14、zgc15等六項子工程是該工程項目中主要子工程，它們的施工情況直接影響著整個工程的施工進度。要想使整個工程按時竣工，就必須保正這六項子工程的施工進度按時進行，如果能夠提高這六項子工程的施工效率，則可使得整個工程提前竣工。

根據AOE網求解關鍵路徑的算法可知，從源點出發經過上述六個關鍵活動到達匯點，所形成的一條或多條路徑即為關鍵路徑（本例中只有一條），關鍵路徑上所有活動持續時間的總和（最大）即為整個工程竣工所需要的最少時間，在本例中為4+3+4+4+1+6=22，也就是說，在本例所描述的工程項目中，整個工程竣工所需要的最少時間是22天。

三、結語

雖然說，關鍵子工程的施工效率直接影響著整個工程的按時完工，但是，其它子工程如果延期足夠長也會影響整個工程的進度。所以，要保證工程進度，還是要全面管控所有子工程的實施。

另外，在預測每個子工程的施工時長時，要注意預測結果的準確性，否則，整個工程計劃就不具合理性；同時更要注意每個子工程之間的接續關系，安排要緊湊、科學，才能保障整個工程項目的如期竣工。

參考文獻：

鄭誠.數據結構導論.外語教學與研究出版社.北京：2012

陳承歡.數據結構分析與應用實用教程.清華大學出版社.北京：2015