基于EVM矩陣求解關(guān)鍵路徑的方法

林銘德，戴一璟

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

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

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

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

1 AOE網(wǎng)

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

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

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

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

2 EVM矩陣

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

3 EVM矩陣生成算法

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

EVM生成算法步驟如下:

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

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

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

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

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

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

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

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

4 Matlab實(shí)驗(yàn)仿真

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

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

4.2 實(shí)驗(yàn)仿真結(jié)果

(1)計(jì)算源點(diǎn)與直接后序節(jié)點(diǎn)連接結(jié)果:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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