高鐵工程多項目調度研究

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

高鐵工程多項目調度研究

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

在當前信息化、專業化、精細化管理的形勢下，高鐵工程建設項目進一步規范化、標準化的要求下，為進一步實現高鐵工程多項目調度優化，本文建立了多資源約束下高鐵工程多項目調度問題的數學模型，并提出了一種基于遺傳算法的求解方法。

高鐵工程；多項目調度；遺傳算法

1.高鐵工程多項目調度問題模型

1.1 高鐵工程多項目調度問題描述

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

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

1.2 高鐵工程多項目調度問題模型建立

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

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

2.高鐵工程多項目調度問題數學模型求解

2.1 算法設計

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

2. 1.1 染色體編碼。

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

2.1.2 適應度函數。

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

2.1.3 約束條件處理。

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

2.1.4 初始化種群.

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

2.1.5 解碼操作

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

1) 令 S1= 0，j = 1 ;

2) 當 j ≤ mn 時，j = j + 1 ，轉 3) ，否則轉 6) ;

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

4) 判斷各資源在作業 j 的持續時間內是否存在沖突，若存在則轉5)，否則，轉2) ;

5) Sj= Sj+ 1 ，轉 4) ;

6) 返回所有作業的最早開始時間，結束。

求得各項目工期為：

2.1.6 遺傳算子設計。

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

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

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

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

2.1.7 模擬退火操作。

1) 交叉和變異概率的模擬退火本文根據退火優化思想［9］，設計了具有自適應的 Pc、Pm。

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

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

2.2 高鐵多項目調度問題算法步驟

2) 初始化種群

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

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

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

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

7) 程序結束并輸出結果。

3.結束語

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

[1] 王凱，李原，張杰． 基于人工免疫算法的航空多項目資源均衡技術［J］． 計算機工程與應用，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．