張海波 / 中鐵七局集團西安鐵路工程公司

高鐵工程多項目調(diào)度研究

張海波 / 中鐵七局集團西安鐵路工程公司

在當(dāng)前信息化、專業(yè)化、精細化管理的形勢下，高鐵工程建設(shè)項目進一步規(guī)范化、標準化的要求下，為進一步實現(xiàn)高鐵工程多項目調(diào)度優(yōu)化，本文建立了多資源約束下高鐵工程多項目調(diào)度問題的數(shù)學(xué)模型，并提出了一種基于遺傳算法的求解方法。

高鐵工程；多項目調(diào)度；遺傳算法

1.高鐵工程多項目調(diào)度問題模型

1.1 高鐵工程多項目調(diào)度問題描述

高鐵工程施工企業(yè)一般都是通過網(wǎng)絡(luò)計劃方式來做項目計劃的，針對網(wǎng)絡(luò)計劃圖中的多項目問題，本文通過增加虛擬開始/結(jié)束作業(yè)的方式[1]，將多個海工裝備項目網(wǎng)絡(luò)計劃進行合并，形成一個虛擬的帶作業(yè)工期和資源消耗量的特殊單代號網(wǎng)絡(luò)圖，在本文中， ni為第 i 個作業(yè)的作業(yè)編號，di表示第 i 個作業(yè)的工期，r1i、r2i表示第 i 個作業(yè)在單個工作日對 R1、R22 種資源的消耗量，S ，E 為合成項目的虛擬開始/結(jié)束作業(yè)，s1，e1、s2，e2分別為項目 1、2 的虛擬開始/結(jié)束作業(yè)，ds1，ds2、de1，de2為虛擬作業(yè) s1，e1、s2，e2對應(yīng)的工期。

在此基礎(chǔ)上，為了建立多資源約束下多項目調(diào)度優(yōu)化問題模型，進行如下假設(shè):（1） 一旦啟動項目中的作業(yè)，不得中斷作業(yè)，必須持續(xù)到完工;（2）在工期使用范圍內(nèi)，資源供給能力為均勻分布; （3） 單位時間內(nèi)各作業(yè)對某種資源的需求量之和必須小于該資源的供給上限; （4）除了共享資源外，項目之間相互獨立。

1.2 高鐵工程多項目調(diào)度問題模型建立

高鐵工程多項目調(diào)度包含 m 個并行項目，共享 k 種可更新資源，其中第 k 種資源的供給上限為 Rk，第 i 個項目包含 ni+ 2 個作業(yè)，其中第 0 個和第ni+ 1 個作業(yè)為項目 i 的擬開始和結(jié)束作業(yè)，具有一定的持續(xù)時間但不消耗任何資源。第 i 個項目中的第 j 個作業(yè)記為 Aij，其工期為 dij，開始時間記為 Sij，對第 k 種資源的需求量為 rijk，用 Pij表示作業(yè)Aij的緊前作業(yè)集合，It表示第 t 個工作日正在進行的所有作業(yè)集合，則問題的數(shù)學(xué)模型可以描述為

公式（1）為目標函數(shù)，表示所有項目最短加權(quán)總工期，?i表示第i個項目的權(quán)重，公式（2）指并行項目的權(quán)重系數(shù)之和必須為1；公式（3）為項目作業(yè)的緊前關(guān)系約束，一個作業(yè)開始前必須保證其所有緊前作業(yè)集中的作業(yè)均已完工；公式（4）為資源約束，單個工作日內(nèi)所有作業(yè)對某一資源的需求量之和必須小于該資源的供給上限；公式（5）指作業(yè)對人以資源的需求都不得為負；公式（6）指第t個工作日正在進行的所有作業(yè)集合。

2.高鐵工程多項目調(diào)度問題數(shù)學(xué)模型求解

2.1 算法設(shè)計

在低層和高層遺傳算法的進化中，采用模擬退火處理后的Pc、Pm進行交叉和變異操作，對交叉和變異過的個體分別進行模擬退火操作，從而幫助種群跳出局部最優(yōu)解。高層遺傳算法每運行一代都進行終止判斷，如果不滿足終止條件，繼續(xù)高層遺傳算法，進化5代后，返回低層遺傳算法進行新一輪的尋優(yōu)。

2. 1.1 染色體編碼。

本文采用作業(yè)列表的方式進行染色體編碼，染色體表達式為: Vk= ［r1，r2，…，ri，…，rmn］，其中 mn為所有項目的總作業(yè)數(shù)，ri表示第 i 個作業(yè)。

2.1.2 適應(yīng)度函數(shù)。

由于本文采用特殊方法進行種群的初始化以及交叉變異操作，不會產(chǎn)生非法染色體，所以在對個體的適應(yīng)度評價時無需引入懲罰函數(shù)，本算法的適應(yīng)度函數(shù): f( s) = 1 /F( s) ，式中: F( s) 是個體 s的目標函數(shù)值，即所有項目工期的加權(quán)和。

2.1.3 約束條件處理。

高鐵工程多項目調(diào)度問題的主要約束條件包括兩個: 作業(yè)緊前關(guān)系約束以及資源約束[2]。采用常規(guī)的方法( 如懲罰函數(shù)法) 并不能很好的處理這兩個約束條件，本文采用的染色體編碼設(shè)計主要考慮作業(yè)的先后關(guān)系，而作業(yè)的開始時間以及資源消耗則是通過解碼操作完成的，這樣自然就將作業(yè)緊前關(guān)系約束和資源約束分開了，因此本文設(shè)計了以下策略來進行高鐵工程多項目調(diào)度問題的約束條件處理:作業(yè)緊前關(guān)系約束: 在初始化種群時就考慮，使初始化時產(chǎn)生的個體都滿足該約束條件，并采用特殊處理的交叉變異算子，避免不滿足緊前關(guān)系約束個體的產(chǎn)生；資源約束:在解碼操作時直接考慮資源約束，當(dāng)加入新作業(yè)存在資源沖突時自動將該作業(yè)的開始時間延。

2.1.4 初始化種群.

本文在初始化種群的同時考慮緊前關(guān)系約束，使產(chǎn)生的個體都滿足約束條件，具體的實施策略是:采用3 個一維數(shù)組 A1、A2、A3和 1 個二維數(shù)組B ，其中 A1是未完成作業(yè)集合，A2是可執(zhí)行作業(yè)集合( 過渡數(shù)組) ，A3是已完成作業(yè)集合，二維數(shù)組B中的每一列是 A1中相應(yīng)列作業(yè)對應(yīng)的緊前作業(yè)集合，B 數(shù)組相當(dāng)于是一個緊前關(guān)系約束條件數(shù)組，在整個循環(huán)過程中都不發(fā)生變化。

2.1.5 解碼操作

本文在實例驗證時發(fā)現(xiàn)，在解碼過程中直接把資源約束條件考慮進去，比采用懲罰函數(shù)法更加方便有效．假設(shè)有 m 個并行項目，Ti表示項目 i 的工期，Sj表示作業(yè) j 的開始時間，染色體 Vk=［r1，r2，…，ri，…，rmn］表示所得到的拓撲排序后的作業(yè)列表，對該染色體的解碼操作如下：

1) 令 S1= 0，j = 1 ;

2) 當(dāng) j ≤ mn 時，j = j + 1 ，轉(zhuǎn) 3) ，否則轉(zhuǎn) 6) ;

3) Sj= max{ Sk+ dk} ( k ∈ Pj) ，轉(zhuǎn) 4) ;

4) 判斷各資源在作業(yè) j 的持續(xù)時間內(nèi)是否存在沖突，若存在則轉(zhuǎn)5)，否則，轉(zhuǎn)2) ;

5) Sj= Sj+ 1 ，轉(zhuǎn) 4) ;

6) 返回所有作業(yè)的最早開始時間，結(jié)束。

求得各項目工期為：

2.1.6 遺傳算子設(shè)計。

1) 選擇算子 選擇算子采用輪盤賭選擇法，并采取精英保留策略。

可又有誰這么大本事，神不知鬼不覺地偷走這么多東西？這營業(yè)部四周有高達3米的圍墻，上面還插了很多玻璃碎片，別說人，就是在院壩里尋食的黑眼麻雀都要抬高了腦袋才能飛過去。其次這倉庫大門對著不到五米就是我家，再怎么說我不可能一點聲響都聽不到，就算我老了耳朵不中用，但正值壯年的藏獒莽子，絕對不會聽不到，平時，除了營業(yè)部里的人，沒幾個人敢在莽子前出現(xiàn)。就算是那幾個下貨物的人認識莽子，可他們怎么可能會有倉庫的鑰匙，這倉庫的鑰匙只有我和丁主任有，而丁主任怎么可能干這監(jiān)守自盜的事，難道……難道？別人以為是我干的？

2) 交叉算子 為了避免產(chǎn)生非法解，本文在一般單點交叉的基礎(chǔ)上進行了一定的改進，具體運算過程如下: 在［1，mn］范圍內(nèi)隨機生成一個整數(shù)p，將父染色體Xi和Xj的前p個基因互換得到子染色體Yi和Yj(現(xiàn)在的）Yi和Yj中存在重復(fù)作業(yè)，屬于非法解)，再從 Xi中找出與 Yi的前 p 個基因不同的剩下 mn － p 個基因按在 Xi中的先后順序替換掉子染色體 Yi的后 mn － p 個基因，同理從 Xj中找出剩下的mn － p 個基因?qū)⒆尤旧w Yj替換。

3) 變異算子。變異算子的目的是防止算法陷入局部最優(yōu)解[3]，增加種群多樣性，尤其是在進化后期，種群中的個體過于相似，僅通過交叉操作很難產(chǎn)生新個體，因此必須采用變異算子來引入新個體．

2.1.7 模擬退火操作。

1) 交叉和變異概率的模擬退火本文根據(jù)退火優(yōu)化思想［9］，設(shè)計了具有自適應(yīng)的 Pc、Pm。

2) 交叉和變異后個體的模擬退火

首先在交叉/變異后個體 Vi的鄰域 N( Vi) 內(nèi)隨機選取一點Vi1( Vi1也是問題的一個可行解) ，隨機生成［0，1］之間的數(shù)q，判 斷 由 式 ( 13 ) 計 算 的Pt( T2) 是否大于q ，若大于則用 Vi1代替 Vi，否則保留 V。

2.2 高鐵多項目調(diào)度問題算法步驟

2) 初始化種群

3) 將當(dāng)前種群隨機均分成 C 個子種群，對每個子種群獨立運行各自模擬退火遺傳算法( 低層遺傳算法)。

4) 每個子種群獨立進化5 代后，將 C 個遺傳算法的結(jié)果種群記錄到二維數(shù)組R［1 ～ C，1 ～ c］中(c = popsize / C ) 。同時，將 C 個子種群的平均適應(yīng)度記錄到數(shù)組A［1 ～ C］中。

5) 高層遺傳算法保留若干最優(yōu)個體后，運行 1代，判斷結(jié)果是否滿足終止條件，若滿足，轉(zhuǎn) 7) ，若不滿足，轉(zhuǎn) 6)。

6) 判斷是否運行了 5代，是則轉(zhuǎn) 3) ，否則轉(zhuǎn) 5)。

7) 程序結(jié)束并輸出結(jié)果。

3.結(jié)束語

本文針對高鐵工程多項目調(diào)度建立了優(yōu)化數(shù)學(xué)模型，提出了一種基于遺傳算法的求解方法，并將模擬退火算法和遺傳算法進行融合，對遺傳算法進行分層，可有效求解大規(guī)模高鐵工程多項目調(diào)度問題。

[1] 王凱，李原，張杰． 基于人工免疫算法的航空多項目資源均衡技術(shù)［J］． 計算機工程與應(yīng)用，2008，44( 16) : 211-214．

[2] Van PETEGHEM V，VANHOUCKE M． A genetic algorithm for the preemptive and non-preemptive multi-mode resourceconstrained project scheduling problem ［J］． Euopean Journal of Operational Research，2010，201: 409-418．

[3]劉剛，曹勇，李華德．幾種改進遺傳算法的性能比較［J］．微計算機信息，2007，23( 10) : 190-192．