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

張海波 / 中鐵七局集團(tuán)西安鐵路工程公司

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

張海波 / 中鐵七局集團(tuán)西安鐵路工程公司

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

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

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

1.1 高鐵工程多項(xiàng)目調(diào)度問(wèn)題描述

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

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

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

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

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

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

2.1 算法設(shè)計(jì)

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

2. 1.1 染色體編碼。

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

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

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

2.1.3 約束條件處理。

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

2.1.4 初始化種群.

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

2.1.5 解碼操作

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

1) 令 S1= 0，j = 1 ;

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

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

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

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

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

求得各項(xiàng)目工期為：

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

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

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

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

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

2.1.7 模擬退火操作。

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

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

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

2.2 高鐵多項(xiàng)目調(diào)度問(wèn)題算法步驟

2) 初始化種群

3) 將當(dāng)前種群隨機(jī)均分成 C 個(gè)子種群，對(duì)每個(gè)子種群獨(dú)立運(yùn)行各自模擬退火遺傳算法( 低層遺傳算法)。

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

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

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

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

3.結(jié)束語(yǔ)

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

[1] 王凱，李原，張杰． 基于人工免疫算法的航空多項(xiàng)目資源均衡技術(shù)［J］． 計(jì)算機(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ìn)遺傳算法的性能比較［J］．微計(jì)算機(jī)信息，2007，23( 10) : 190-192．