熊衛(wèi)民

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

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

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

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

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

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

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

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

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

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

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

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

1、計(jì)算方法

因?yàn)樵谕还こ添?xiàng)目中的一些子工程是可以同時(shí)施工的，所以，完成整個(gè)工程所需要的時(shí)間應(yīng)該是從源點(diǎn)到匯點(diǎn)之間的最大路徑長(zhǎng)度（即該路徑上所有子工程施工時(shí)間之和）。

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

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

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

Ve[1]=0

Ve[k]=max{ve[j]+dut（）} 表示從第j個(gè)頂點(diǎn)到第k個(gè)頂點(diǎn)的一條邊

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

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

Vl[n]=ve[n]

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

（3）計(jì)算活動(dòng)（即子工程）的最早開(kāi)工時(shí)間

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

e[i]=ve[k]

（4）計(jì)算活動(dòng)ai的最晚開(kāi)始時(shí)間

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

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

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

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

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

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

三、結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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