基于Graph的鐵道工程工期估算算法及實(shí)現(xiàn)

涂玉芬

（武漢鐵路職業(yè)技術(shù)學(xué)院電子電氣工程系，武漢 430205）

基于Graph的鐵道工程工期估算算法及實(shí)現(xiàn)

涂玉芬

（武漢鐵路職業(yè)技術(shù)學(xué)院電子電氣工程系，武漢 430205）

為有效幫助鐵道工程技術(shù)管理人員進(jìn)行工程工期估算，合理調(diào)度和控制各子工程的施工進(jìn)度，運(yùn)用Graph結(jié)構(gòu)中的AOE網(wǎng)分析工期估算算法，可實(shí)現(xiàn)計(jì)算機(jī)輔助管理，有利于科學(xué)管理鐵道工程。

Graph；鐵道工程；工期估算；AO E網(wǎng)；關(guān)鍵活動(dòng)

0 引 言

當(dāng)前，中國(guó)正進(jìn)入史無(wú)前例的高速鐵路建設(shè)期，中國(guó)鐵路已經(jīng)站在新的歷史起點(diǎn)上，迎來(lái)大發(fā)展、大建設(shè)的黃金時(shí)期。面對(duì)龐大而復(fù)雜的鐵道系統(tǒng)工程，進(jìn)行工程工期估算，合理調(diào)度和控制各子工程的施工進(jìn)度，是保證工程順利實(shí)施的前提。運(yùn)用Gr aph結(jié)構(gòu)中的AOE網(wǎng)，分析鐵道工程工期估算算法，并給出了算法的C語(yǔ)言描述，從而實(shí)現(xiàn)了計(jì)算機(jī)輔助管理，對(duì)科學(xué)管理鐵道工程具有重要意義。

1 Graph結(jié)構(gòu)

Graph（圖）是一種復(fù)雜的非線性結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)中任意兩結(jié)點(diǎn)之間都可能存在聯(lián)系。Gr aph結(jié)構(gòu)可用二元組形式表示為：

其中，n表示Graph中頂點(diǎn)的數(shù)量，el em t ype表示Graph中頂點(diǎn)（數(shù)據(jù)元素）的數(shù)據(jù)類型，P（Vi，Vj）表示存在從Vi到Vj的一條邊[1-2]。

根據(jù)Graph中存在的邊是否有方向性，Graph分為有向圖和無(wú)向圖；根據(jù)Gr aph中存在的邊是否具有權(quán)，Graph分為有權(quán)圖和無(wú)權(quán)圖；根據(jù)Graph中是否存在回路，Graph分為有環(huán)圖和無(wú)環(huán)圖[1-4]。Graph結(jié)構(gòu)適合于描述各種關(guān)系復(fù)雜的數(shù)據(jù)對(duì)象，在自然科學(xué)及社會(huì)科學(xué)等許多科學(xué)技術(shù)領(lǐng)域有著非常廣泛的應(yīng)用。

2 AO E網(wǎng)

任何一個(gè)工程項(xiàng)目在實(shí)施之前，都要進(jìn)行工程的可行性分析、工程造價(jià)評(píng)估、工程工期估算等前期規(guī)劃工作。一個(gè)大的鐵道工程一般由許多小的子工程組成，子工程之間通常存在一些時(shí)序上的約束關(guān)系，有一些子工程可同時(shí)進(jìn)行，而有一些子工程則必須在另一些子工程完成之后才能開(kāi)始，這就給工程的規(guī)劃工作帶來(lái)一定的難度。

AOE網(wǎng)是一種用來(lái)表示工程中各項(xiàng)活動(dòng)（子工程）間關(guān)系的帶權(quán)有向無(wú)環(huán)圖，在此帶權(quán)有向無(wú)環(huán)圖中，用弧（有向邊）表示活動(dòng)，弧上的權(quán)表示活動(dòng)的持續(xù)時(shí)間，用頂點(diǎn)表示事件，事件是標(biāo)志某些活動(dòng)已經(jīng)完成和另一些活動(dòng)開(kāi)始的信號(hào)[2-6]，如圖1所示。

圖1 一個(gè)鐵道工程的AOE網(wǎng)

使用AOE網(wǎng)來(lái)描述一個(gè)鐵道工程項(xiàng)目中各子項(xiàng)目及子項(xiàng)目之間時(shí)序上的約束關(guān)系，可有效地幫助工程技術(shù)管理人員進(jìn)行工程工期估算，合理調(diào)度和控制各子工程的工作進(jìn)度，確保工程如期完成。

3 工程最短工期估算方法

在如圖1所示的一個(gè)鐵道工程的AOE網(wǎng)中，通常只有一個(gè)入度為0的頂點(diǎn)，V1表示工程的開(kāi)始點(diǎn)，稱為源點(diǎn)；只有一個(gè)出度為0的頂點(diǎn)，V7表示工程的終止點(diǎn)，稱為匯點(diǎn)。從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即最長(zhǎng)路徑上所有活動(dòng)（子工程）持續(xù)時(shí)間之和，就是完成工程所需的最短時(shí)間，最長(zhǎng)路徑上的活動(dòng)（子工程）是影響整個(gè)工程進(jìn)度的關(guān)鍵。因此，找出AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑和該路徑上的活動(dòng)，是計(jì)算和控制工程工期的關(guān)鍵。

從源點(diǎn)到匯點(diǎn)的長(zhǎng)度最長(zhǎng)的路徑，稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動(dòng)，稱為關(guān)鍵活動(dòng)。在沒(méi)有延誤的情況下，時(shí)間余量（允許延遲的時(shí)間）為0的活動(dòng)即為關(guān)鍵活動(dòng)；活動(dòng)的時(shí)間余量等于該活動(dòng)的最早開(kāi)始時(shí)間與該活動(dòng)的最遲開(kāi)始時(shí)間之差。要計(jì)算AOE網(wǎng)中所有活動(dòng)的最早開(kāi)始時(shí)間與該活動(dòng)的最遲開(kāi)始時(shí)間，先要計(jì)算出AOE網(wǎng)中所有事件的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間[2][5-6]。

如圖2所示，如果活動(dòng)ai的前一事件為Vm，活動(dòng)ai的后一事件為Vn，設(shè)活動(dòng)ai的最早開(kāi)始時(shí)間為E（i），活動(dòng)ai的最遲開(kāi)始時(shí)間為L(zhǎng)（i），事件Vj的最早發(fā)生時(shí)間為VE（j），事件Vj的最遲發(fā)生時(shí)間為VL（j），則有：

如圖3所示，如果事件Vj的前一事件為Vx，事件Vx到Vj的活動(dòng)為ax，則求事件Vj的最早發(fā)生時(shí)間VE（j），應(yīng)從源點(diǎn)開(kāi)始，向匯點(diǎn)方向按下列公式進(jìn)行計(jì)算：

圖2 活動(dòng)ai

圖3 事件Vj的前一事件

如圖4所示，如果事件Vj的后一事件為Vy，事件Vj到Vy的活動(dòng)為ay，則求事件Vj的最遲發(fā)生時(shí)間VL（j），應(yīng)從匯點(diǎn)開(kāi)始，向源點(diǎn)方向按下列公式進(jìn)行計(jì)算：

圖4 事件Vj的后一事件

根據(jù)上述計(jì)算方法，如圖1所示的一個(gè)鐵道工程的AOE網(wǎng)中，所有事件Vj的最早發(fā)生時(shí)間VE（j）和最遲發(fā)生時(shí)間VL（j）見(jiàn)表1，所有活動(dòng)ai的最早開(kāi)始時(shí)間E（i）和最遲開(kāi)始時(shí)間L（i）見(jiàn)表2。

表1 事件Vj的最早發(fā)生時(shí)間VE（j）和最遲發(fā)生時(shí)間VL（j）

由表2可知，如圖1所示的一個(gè)鐵道工程的AOE網(wǎng)的關(guān)鍵活動(dòng)為a1，a4，a7，a10，控制子工程a1，a4，a7，a10的進(jìn)度就是保證工程工期的關(guān)鍵。其關(guān)鍵路徑如圖5所示。

表2 所有活動(dòng)ai的最早開(kāi)始時(shí)間E（i）和最遲開(kāi)始時(shí)間L（i）

圖5 一個(gè)鐵道工程AOE網(wǎng)的關(guān)鍵路徑

4 基于C語(yǔ)言的算法及實(shí)現(xiàn)

分析鐵道工程最短工期估算方法，可得到求關(guān)鍵路徑的算法[2][5-6]如下：

（1）輸入n條弧，建立AOE網(wǎng)的鏈接表存儲(chǔ)結(jié)構(gòu)。

（2）從源點(diǎn)V1出發(fā)，計(jì)算AOE網(wǎng)中所有事件Vj的最早發(fā)生時(shí)間VE（j）。令VE（1）=0，按拓?fù)漤樞蛴?jì)算其余各事件的最早發(fā)生時(shí)間VE（j）（2≤j≤n） ；如果得到的拓?fù)溆行蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于AOE網(wǎng)中的頂點(diǎn)個(gè)數(shù)，則該網(wǎng)有環(huán)，不能求關(guān)鍵路徑，算法終止，否則，執(zhí)行步驟（3）。

（3）從匯點(diǎn)Vn出發(fā)，計(jì)算AOE網(wǎng)中所有事件Vj的最遲發(fā)生時(shí)間VL（j）。令VL（n）=VE（n），按拓?fù)淠嫘蛴?jì)算其余各事件的最早發(fā)生時(shí)間VL（j）（n≥j≥2）。

（4）根據(jù)各事件的最早發(fā)生時(shí)間VE和最遲發(fā)生時(shí)間VL，計(jì)算AOE網(wǎng)中所有活動(dòng)ai的最早開(kāi)始時(shí)間E（i）和最遲開(kāi)始時(shí)間L（i），找出E（i）=L（i）的關(guān)鍵活動(dòng)并輸出。

以上算法可用C語(yǔ)言描述如下：

5 結(jié)束語(yǔ)

大規(guī)模的鐵路建設(shè)，將給地方經(jīng)濟(jì)帶來(lái)巨大的拉動(dòng)作用。基于Gr aph的鐵道工程工期估算算法及其實(shí)現(xiàn)，將有效地幫助鐵道工程技術(shù)管理人員進(jìn)行工程管理，合理調(diào)度和控制各子工程的施工進(jìn)度，降低工程成本，提高工作效率。

[1]李益民，鄧文華.數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版[M].北京:電子工業(yè)出版社，2004:85-86.

[2]陳明.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2005:179-219.

[3]徐士良.實(shí)用數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2006:123-139.

[4]將文容.數(shù)據(jù)結(jié)構(gòu)[M].北京:高等教育出版社，2005:85.

[5]薛鐵鷹.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)與應(yīng)用[M].北京:海洋出版社，2005:128-148.

[6]陳雁.數(shù)據(jù)結(jié)構(gòu)[M].第2版.北京:高等教育出版社，2004:73-99.

Calculation of Time Limit for Railway Engineering on Basis of Graph and its Implementations

TU Yufen
（Department of Electronic & Electric Engineering, Wuhan Railway Vocational College of Technology, Wuhan, 430205, China）

In order to help the manager of railway engineering to calculate the time limit for an engineering, to control the construction schedule of sub-projects, the AOE net in Graph structure is applied and it can achieve the goal of computer-assisted management and is beneficial for the scientific management of railway engineering.

Graph; Railway engineering; Time limit for an engineering; AOE net; Key activities

TU712.1

A

1671-4326（2011）04-0052-04

2011-07-15

涂玉芬（1966—），女，湖北武漢人，武漢鐵路職業(yè)技術(shù)學(xué)院電子電氣工程系副教授．

王志梅]