林銘德，戴一璟

(1.福建工程學院計算機與信息科學系，福建福州 350108;2.福建工程學院管理學院，福建福州 350108)

在建設(shè)工程中，進度計劃是項目發(fā)展的關(guān)鍵，工程建設(shè)項目管理中用網(wǎng)絡(luò)計劃圖來表示進度計劃。用網(wǎng)絡(luò)計劃對建設(shè)項目進行進度控制，能明確表達各項工作之間的邏輯關(guān)系。通常在項目執(zhí)行過程中，存在許多不可預知的因素，可能會影響到項目是否能按期完工，因此相對于進度計劃，進度控制也同樣重要。掙值法(earned value management，EVM)作為費用/進度的綜合測評技術(shù)，最早由美國國防部在20世紀60年代將其納入費用/進度控制系統(tǒng)標準中(C/SCSC的35條準則)。20世紀90年代后期，EVM的價值被重新肯定，美國國家標準協(xié)會發(fā)布了專門的EVMS標準ANSI/EIA748(1998年)，目前已成為用于現(xiàn)代企業(yè)和商業(yè)工程項目管理的重要方法。1977年至今，美國國防部已經(jīng)用這種方法跟蹤了800多個項目的績效，極大地改善了項目超支和超期的惡性循環(huán)，節(jié)約了大量的經(jīng)費和時間。

EVM通過計算項目的工期與成本，對項目的進度與成本執(zhí)行績效的度量，進行相應(yīng)的偏差分析，并與項目原計劃比較，糾正偏差或調(diào)整項目計劃。但實際應(yīng)用中，掙值法在使用上還存在一些局限和不足，尤其是在計劃比較復雜的項目中，若掙值的計算過程中沒有考慮關(guān)鍵路徑，就有可能產(chǎn)生誤導信息，影響對于進度的判斷［1-2］。傳統(tǒng)的關(guān)鍵路徑算法［3］存在一些不足:①算法需要分別求出所有事件的最早發(fā)生時間和最遲發(fā)生時間以及每項活動的最早開始時間和最遲開始時間，然后判斷哪些活動是關(guān)鍵活動，算法過程復雜;②算法執(zhí)行完畢，只能知道哪些是關(guān)鍵活動，卻不能統(tǒng)計從源點到匯點的關(guān)鍵路徑數(shù)，也不能將每條關(guān)鍵路徑輸出。一些研究人員也對關(guān)鍵路徑的算法進行了改進，文獻［4］在廣度優(yōu)先搜索的基礎(chǔ)上，給出了一種求解關(guān)鍵路徑的算法，該算法采用圖的十字鏈表結(jié)構(gòu)形式，不需要進行拓撲排序求出所有關(guān)鍵活動，對傳統(tǒng)算法進行了改進。該算法的優(yōu)點是無需進行拓撲排序而求取關(guān)鍵路徑;不足之處在于采用十字鏈表作存儲結(jié)構(gòu)，顯得比較復雜;需要對圖進行三次廣度優(yōu)先搜索，才能輸出所有的關(guān)鍵活動，但不能把所有的關(guān)鍵路徑輸出。文獻［5］在深度優(yōu)先搜索的基礎(chǔ)上，求出從源點到匯點的所有路徑，經(jīng)過分析比較后找出最長的路徑，從而求取關(guān)鍵路徑。由于在求解過程中需要進行多次遞歸回溯，算法的執(zhí)行效率較低。文獻［6］針對上述不足提出了一種在廣度優(yōu)先搜索基礎(chǔ)上，利用優(yōu)先隊列，結(jié)合動態(tài)規(guī)劃思想實現(xiàn)求解關(guān)鍵路徑的算法。該算法使得時間復雜度降低為O(n+e)，然而，由于算法采用圖的鄰接表形式，以自底向上的方式計算最優(yōu)值，并在該過程中記錄一些有用信息，因此需要額外的存儲空間，同時，采用一個按照入度值為優(yōu)先級的優(yōu)先隊列排序。在輸出所有關(guān)鍵路徑時，需要將每個節(jié)點信息轉(zhuǎn)換為一個二維數(shù)組，因此，該算法是以空間為代價換取時間。以上算法均未綜合考慮節(jié)點變化的情況。

筆者針對傳統(tǒng)的求解關(guān)鍵路徑算法的不足，通過引入將AOE圖鄰接矩陣轉(zhuǎn)變?yōu)镋VM矩陣的思想，提出了一種新算法。算法具有如下特點:①能精確求出AOE圖中從源點到匯點的所有關(guān)鍵路徑、關(guān)鍵活動和長度;②算法簡單、直觀，在AOE圖變?yōu)镋VM樹的過程中進行關(guān)鍵路徑的求解，當矩陣轉(zhuǎn)換完成時，關(guān)鍵路徑也同時求解出來;③施工過程中節(jié)點的變化(增減節(jié)點，邊權(quán)值變化)可較簡易地通過EVM相關(guān)節(jié)點的變化實現(xiàn)新的計算，不需要重新計算所有的路徑。

1 AOE網(wǎng)

定義1 建設(shè)工程的網(wǎng)絡(luò)計劃圖［7-10］是一個AOE(activity on edge)網(wǎng)，邊表示活動的網(wǎng)，是一個帶權(quán)的有向無環(huán)圖，其中節(jié)點表示事件(event)，每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始，弧表示活動，權(quán)表示活動持續(xù)的時間。AOE網(wǎng)可用來估算工程的完成時間。由于整個工程只有一個開始點和一個完成點，故在正常的情況(無環(huán))下，網(wǎng)中只有一個入度為零的點(起點或源點)和一個出度為零的點(終點或匯點)。

定義2 由于AOE網(wǎng)中有些活動可以并行地進行，因此完成工程的最短時間是從開始點到完成點的最長路徑的長度(路徑上各活動持續(xù)時間之和)。路徑最長的路徑叫做關(guān)鍵路徑。圖1是一個典型的AOE網(wǎng)。

圖1 典型的AOE網(wǎng)

AOE網(wǎng)具有以下兩個性質(zhì):①只有某節(jié)點所代表的事件完成后，從該節(jié)點出發(fā)的各有向邊所代表的活動才能開始;②只有進入某節(jié)點的各有向邊所代表的活動全部結(jié)束，該節(jié)點所代表的事件才能發(fā)生。

2 EVM矩陣

利用AOE網(wǎng)的鄰接矩陣，由EVM生成算法計算得到的矩陣是一個EVM矩陣，該矩陣有以下性質(zhì):①EVM矩陣元素表示AOE網(wǎng)節(jié)點的編號。②AOE網(wǎng)源點編號0為EVM矩陣的第1列元素，非第1列的元素值為0表示無節(jié)點。③EVM矩陣的每一行表示AOE網(wǎng)的一條工作路徑。④矩陣行中＜i，j＞表示節(jié)點i與節(jié)點j之間有直接前后序關(guān)系。⑤工作路徑的長度為EVM矩陣的最后一列元素。⑥若AOE網(wǎng)發(fā)生變化，根據(jù)變化特點由相應(yīng)的算法對EVM矩陣進行計算，得到的結(jié)果依舊是一個EVM矩陣。

3 EVM矩陣生成算法

按AOE網(wǎng)絡(luò)節(jié)點和權(quán)值關(guān)系創(chuàng)建鄰接矩陣G(i，j)，元素值為0表示節(jié)點i與節(jié)點j無直接前后序關(guān)系，非0則表示節(jié)點i與節(jié)點j有直接前后序關(guān)系，且元素值為邊的權(quán)重。

EVM生成算法步驟如下:

(1)讀取數(shù)組G第1行第1個到最后一個數(shù)組元素，找出非0數(shù)組元素(即源點的直接后序節(jié)點)，依順序按非0數(shù)組元素列下標生成新的EVM矩陣G，共生成n行，n為非0元素個數(shù)(即源點的出度為n)。該數(shù)組為n×2，每一行第1列數(shù)組元素為0，即起點編號，第i行第2列則為數(shù)組G中第1行第i個非0數(shù)組元素的列下標，即起點的直接后序節(jié)點。EVM每行前后節(jié)點的權(quán)值length相加。

(2)設(shè)i=2，m為G的行數(shù)。

(3)若i＞m，則轉(zhuǎn)移到步驟(8)，否則查找G的第i行，依次找出非0元素，共n個(即節(jié)點i的出度)。

(4)查找EVM矩陣G中元素最大值為i-1行，若查找到，則執(zhí)行步驟(5);若查找不到，則轉(zhuǎn)移到步驟(6)。

(5)將找到的節(jié)點復制n-1個，依次將步驟(3)找到的節(jié)點添加到步驟(3)找到和生成的EVM矩陣相應(yīng)的隊列中，并累加該節(jié)點與步驟(2)找到的節(jié)點的邊的權(quán)值。

(6)繼續(xù)查找EVM矩陣G下一個滿足步驟(3)的行，若找到繼續(xù)步驟(4)的操作，若找不到則轉(zhuǎn)移到步驟(7)。

(7)i=i+1，返回到步驟(3)。

(8)輸出EVM矩陣，每行為1個工作路徑，權(quán)值最大的路徑即為關(guān)鍵路徑，結(jié)束。

4 Matlab實驗仿真

4.1 EVM矩陣生成算法的Matlab部分代碼

可將圖1的AOE網(wǎng)絡(luò)節(jié)點用鄰接矩陣G表示，算法在Matlab 7.01a上實現(xiàn)。

4.2 實驗仿真結(jié)果

(1)計算源點與直接后序節(jié)點連接結(jié)果:

(2)計算G第2行后得到的結(jié)果:

(3)計算G第3行后得到的結(jié)果:

(4)以此類推，計算最后一行的結(jié)果為EVM矩陣:

結(jié)果說明:最終得到EVM矩陣的每一行即為一條工作路徑，由此可以輕易得到關(guān)鍵路徑的長度為24，一共有3條路徑可作為關(guān)鍵路徑，分別為(0、1、3、6、8)、(0、2、4、5、6、8)和(0、2、5、6、8)，關(guān)鍵路徑上的活動都是關(guān)鍵活動。

5 AOE網(wǎng)邊權(quán)值變化、節(jié)點增減的算法

在AOE網(wǎng)絡(luò)計劃圖中，常見的變化有以下幾種(算法在Matlab仿真實現(xiàn)):

(1)邊權(quán)值變化算法(節(jié)點數(shù)量及前后順序沒變)。假設(shè)圖1中節(jié)點i=5和節(jié)點j=7連接的邊的權(quán)值由kv1=4變成kv2=6。

其算法可先求出權(quán)值差delt(kv)=k2-k1，相應(yīng)地只要在用筆者算法生成的EVM矩陣中找到所有包含相鄰節(jié)點為〈i，j〉的行(即工作路徑)，修改行路徑累加權(quán)值length=length+delt(kv)即可，不需重新生成EVM矩陣，也不需要從源點開始重新計算路徑的長度，能有效地減少計算的開銷。

(2)節(jié)點(非源點匯點)的增加。假設(shè)在節(jié)點i與節(jié)點j之間增加一個節(jié)點k(k！=0-n)，節(jié)點i到節(jié)點k邊的權(quán)值為kv;節(jié)點k的直接后序節(jié)點是節(jié)點m和節(jié)點n，邊的權(quán)值分別為x和y，如圖2所示。

圖2 增加節(jié)點k后的AOE網(wǎng)絡(luò)圖

節(jié)點增加算法的步驟為:①在EVM矩陣中統(tǒng)計節(jié)點 k的直接后序節(jié)點編號集合〈i，k，j〉，i，j屬于(0到n)，共k1個。②在EVM矩陣中依次查找包含有〈i，j〉(i，j為直接前序后序節(jié)點)的行(即原有路徑，共k2行)，刪除每行節(jié)點編號在節(jié)點i之后的所有節(jié)點。③重復步驟②直到EVM中沒有包含〈i，j〉的行(路徑)。④經(jīng)過步驟②和步驟③，(0，…，i，j，…，qz)變?yōu)榧?rout=(0，…，i，k)，計算節(jié)點集合的權(quán)值qz1。⑤在EVM中查找包含k的第一個直接后序節(jié)點j的行，復制該行m節(jié)點之后所有的節(jié)點，得到節(jié)點集合(j，…，)。計算節(jié)點集合的權(quán)值qz2。⑥繼續(xù)查找包含k的下個直接后序節(jié)點的行，重復步驟⑤，直到所有的節(jié)點k的直接后序節(jié)點都完成步驟⑤，設(shè)共有s個，集合節(jié)點不重復。⑦復制rout1，與所有步驟⑤得到的集合連接成新的行(即新的路徑)，計算路徑長度l=qz1+x+qz2并加入到EVM矩陣中。⑧結(jié)束。

EVM矩陣中的行就是增加節(jié)點k后所有的工作路徑，權(quán)值最大的就是關(guān)鍵路徑。

實驗仿真:在圖1的AOE網(wǎng)絡(luò)節(jié)點3和節(jié)點6之間加入節(jié)點k，節(jié)點3到節(jié)點k邊的權(quán)值為6，節(jié)點k到節(jié)點6邊的權(quán)值為5，刪除節(jié)點3到節(jié)點6的邊，增加一條節(jié)點k到節(jié)點7的邊，權(quán)值為5，如圖2所示，按節(jié)點增加算法得到EVM，與之前的EVM相比，工作路徑數(shù)量增加了1，由8條路徑變?yōu)?條路徑(改變節(jié)點的第1行和新增加最后一行)，關(guān)鍵路徑數(shù)量由原來的3條變?yōu)楝F(xiàn)在的1條(即第1行，工作路徑長度最大，為27):

(3)節(jié)點(非源點匯點)的減少。節(jié)點減少一般分兩種情況，一種是將該節(jié)點k的直接前序節(jié)點i連接到該節(jié)點k的直接后序節(jié)點j;另一種是將該節(jié)點的直接前序節(jié)點i連接到其他節(jié)點j1，j2，…。

第一種情況算法步驟為:①在EVM矩陣中查找包含節(jié)點k(即要刪除的節(jié)點)所在行(即包含節(jié)點k的路徑)，在鄰接矩陣 G中查找〈i，k〉和〈k，j〉的權(quán)值并累加，然后在該行中刪除節(jié)點 k，計算權(quán)值 =原路徑累加權(quán)值 -〈i，k〉和〈k，j〉的權(quán)值并累加+〈i，j〉邊的權(quán)值length。②重復步驟①直到EVM矩陣所有的行都不含節(jié)點k。

實驗仿真:將圖2中的節(jié)點k刪除，新增〈3，6〉邊權(quán)值為 6，〈3，7〉邊權(quán)值為 5，則按算法可得關(guān)鍵路徑為2條，長度length=24。

第二種情況算法步驟為:①在EVM矩陣中依次查找節(jié)點k的直接前序節(jié)點i所在的行，復制該行起點到節(jié)點i的所有節(jié)點集合rout1=(0，…，i)。②在EVM矩陣中查找節(jié)點i的后序節(jié)點j1所在的行，復制該行節(jié)點j1開始到匯點的所有節(jié)點集合rout2=(j1，…，n)，n為匯點編號，形成新的路徑rout=rout1∪rout2，計算路徑長度，判斷rout是否與EVM行重復，重復則轉(zhuǎn)到步驟③，若不重復，則加入到EVM矩陣中。③重復步驟②，直到節(jié)點i的后序節(jié)點都完成，轉(zhuǎn)移到步驟④。④重復步驟①，直到所有節(jié)點k的直接前序節(jié)點都完成，結(jié)束。

根據(jù)筆者設(shè)計的EVM矩陣生成算法，再加入所設(shè)計的邊和節(jié)點變化算法可設(shè)計出一個帶反饋的關(guān)鍵路徑計算的模型，如圖3所示。

6 結(jié)論

圖3 EVM矩陣求解AOE網(wǎng)關(guān)鍵路徑模型

筆者在AOE網(wǎng)鄰接矩陣的基礎(chǔ)上，給出了一種新的求解關(guān)鍵路徑的算法，該算法借助圖的鄰接矩陣結(jié)構(gòu)，進行關(guān)鍵路徑的求解。整個求解過程不需要對AOE網(wǎng)進行多次遍歷搜索。該算法考慮了AOE網(wǎng)的各種變化情況并進行處理，如網(wǎng)的邊權(quán)值的變化，節(jié)點的增減。因此，該算法具有更高的健壯性，算法簡單直觀，且易于操作。通過仿真實驗進行比較，該算法較傳統(tǒng)的算法更具全面性，在求解所有工作路徑的同時求解出所有關(guān)鍵路徑，具有一定的實用性。

［1］賀桂珍，呂永龍，劉達朱，等.掙值管理在環(huán)境審計中的應(yīng)用［J］.審計研究，2007(2):3-8.

［2］戚安邦.項目掙值分析方法中的錯誤與解決方案［J］.數(shù)量經(jīng)濟與技術(shù)經(jīng)濟研究，2004(5):63-68.

［3］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京:清華大學出版社，1997:17-98.

［4］徐鳳生，黃倩.關(guān)鍵路徑求解的新算法［J］.計算機應(yīng)用，2004，24(12):108-109.

［5］孟繁楨.求關(guān)鍵路徑的一個算法［J］.計算機工程，2001，21(4):6-9.

［6］劉芳，王玲.基于動態(tài)規(guī)劃思想求解關(guān)鍵路徑的算法［J］.計算機應(yīng)用，2006，26(6):1440-1442.

［7］陳建新，唐海.有向無環(huán)圖分層算法研究［J］.華中師范大學學報:自然科學版，2008，42(3):359-363.

［8］韓中，高建民，陳富民，等.面向?qū)ο蟮牧鞒坦I(yè)系統(tǒng)有向無環(huán)圖建模［J］.計算機工程，2009，35(8):23-25.

［9］方霞，潘梅森，席金菊.網(wǎng)絡(luò)計劃圖合法性檢測改進算法［J］.計算機工程與應(yīng)用，2010，46(35):222-224.

［10］楊婧，陳英武.項目網(wǎng)絡(luò)拓撲結(jié)構(gòu)與關(guān)鍵路徑相關(guān)性仿真分析［J］.系統(tǒng)仿真學報，2011，23(12):2721-2726.