涂玉芬

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

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

涂玉芬

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

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

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

0 引 言

當(dāng)前，中國正進(jìn)入史無前例的高速鐵路建設(shè)期，中國鐵路已經(jīng)站在新的歷史起點(diǎn)上，迎來大發(fā)展、大建設(shè)的黃金時期。面對龐大而復(fù)雜的鐵道系統(tǒng)工程，進(jìn)行工程工期估算，合理調(diào)度和控制各子工程的施工進(jìn)度，是保證工程順利實施的前提。運(yùn)用Gr aph結(jié)構(gòu)中的AOE網(wǎng)，分析鐵道工程工期估算算法，并給出了算法的C語言描述，從而實現(xiàn)了計算機(jī)輔助管理，對科學(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分為有向圖和無向圖；根據(jù)Gr aph中存在的邊是否具有權(quán)，Graph分為有權(quán)圖和無權(quán)圖；根據(jù)Graph中是否存在回路，Graph分為有環(huán)圖和無環(huán)圖[1-4]。Graph結(jié)構(gòu)適合于描述各種關(guān)系復(fù)雜的數(shù)據(jù)對象，在自然科學(xué)及社會科學(xué)等許多科學(xué)技術(shù)領(lǐng)域有著非常廣泛的應(yīng)用。

2 AO E網(wǎng)

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

AOE網(wǎng)是一種用來表示工程中各項活動（子工程）間關(guān)系的帶權(quán)有向無環(huán)圖，在此帶權(quán)有向無環(huán)圖中，用?。ㄓ邢蜻叄┍硎净顒樱∩系臋?quán)表示活動的持續(xù)時間，用頂點(diǎn)表示事件，事件是標(biāo)志某些活動已經(jīng)完成和另一些活動開始的信號[2-6]，如圖1所示。

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

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

3 工程最短工期估算方法

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

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

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

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

圖2 活動ai

圖3 事件Vj的前一事件

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

圖4 事件Vj的后一事件

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

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

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

表2 所有活動ai的最早開始時間E（i）和最遲開始時間L（i）

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

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

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

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

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

（3）從匯點(diǎn)Vn出發(fā)，計算AOE網(wǎng)中所有事件Vj的最遲發(fā)生時間VL（j）。令VL（n）=VE（n），按拓?fù)淠嫘蛴嬎闫溆喔魇录淖钤绨l(fā)生時間VL（j）（n≥j≥2）。

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

以上算法可用C語言描述如下：

5 結(jié)束語

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

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

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

[3]徐士良.實用數(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é)院電子電氣工程系副教授．

王志梅]