熊衛(wèi)民

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

【中圖分類號】 G6425 【文獻(xiàn)標(biāo)識碼】 A 【文章編號】 2095-3089（2017）13-00-01

一、關(guān)鍵路徑的基本概念

在數(shù)據(jù)結(jié)構(gòu)中，如果我們用頂點表示事件的發(fā)生（比如：某項活動的開始或結(jié)束），用邊表示活動（活動的實施），邊所對應(yīng)的權(quán)值表示活動所持續(xù)的時間代價，則稱這樣邊帶權(quán)的有向圖為AOE（Activity on edge network）網(wǎng)。AOE網(wǎng)通常在工程或項目管理中有著實際的應(yīng)用。

如果用AOE網(wǎng)來描述一項工程或項目實施計劃的話，那么，邊可以表示子工程或子活動，有向邊（也稱為?。┍硎咀庸こ虒嵤┑南群蟠涡?，邊所帶的權(quán)表示子工程實施的持續(xù)時間代價。我們在設(shè)計工程施工計劃時，有時必須關(guān)心整個工程竣工最少需要多少時間；哪些子工程的施工進(jìn)度會影響到整個工程的按時完工，如果加速這些子工程的施工進(jìn)度能否提高整個工程的效率。因此，有必要對子工程的施工次序、子工程互相之間的影響關(guān)系、預(yù)計完成的時間有一個預(yù)測（估算），同時要確定影響整個工程進(jìn)度的關(guān)鍵子工程有哪些。這就形成了工程施工的AOE網(wǎng)。

從數(shù)據(jù)結(jié)構(gòu)中我們得知，AOE網(wǎng)是一個有向無環(huán)結(jié)構(gòu)的圖，AOE網(wǎng)應(yīng)具有下面兩個性質(zhì)：

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

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

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

二、關(guān)鍵路徑在某工程管理中的應(yīng)用

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

下面就數(shù)據(jù)結(jié)構(gòu)中求解關(guān)鍵路徑、關(guān)鍵活動（即子工程）的相關(guān)算法，簡要介紹整個工程的竣工最少需要多少時間、影響整個工程進(jìn)度的主要子工程有哪些。

1、計算方法

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

在AOE網(wǎng)中求解關(guān)鍵路徑的方法：

（1）計算事件最早發(fā)生的時間

設(shè)Ve[k]為第k個事件的最早發(fā)生時間，根據(jù)AOE網(wǎng)的性質(zhì)，只有當(dāng)?shù)趉個子工程的前期子工程全部結(jié)束時，第k個子工程才能開工，即第k個子工程的最早時間才能確定。而子工程的最早結(jié)束時間為ve[j]+dut（）。計算方法如下：

Ve[1]=0

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

（2）計算事件最晚發(fā)生的時間

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

Vl[n]=ve[n]

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

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

設(shè)e[i]為第i項活動（ai）的最早開始時間?；顒釉贏OE網(wǎng)中對應(yīng)著一條弧，用所表示的一項活動。依據(jù)AOE網(wǎng)的性質(zhì)，只有事件vk發(fā)生了，活動ai才能開工。即，活動ai的最早開工時間應(yīng)等于事件vk的最早發(fā)生時間。計算方法如下：

e[i]=ve[k]

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

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

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

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

2、確定關(guān)鍵路徑與關(guān)鍵活動

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

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

三、結(jié)語

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

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

參考文獻(xiàn)：

鄭誠.數(shù)據(jù)結(jié)構(gòu)導(dǎo)論.外語教學(xué)與研究出版社.北京：2012

陳承歡.數(shù)據(jù)結(jié)構(gòu)分析與應(yīng)用實用教程.清華大學(xué)出版社.北京：2015