基于遺傳算法的多模式資源約束項(xiàng)目調(diào)度問題研究

摘要：為解決多模式資源約束項(xiàng)目調(diào)度問題，提出了一種混合遺傳算法的求解方法。該算法采用二維編碼方法來表示問題的解，基因的值表示任務(wù)的優(yōu)先權(quán)和執(zhí)行模式，每條染色體對(duì)應(yīng)一個(gè)滿足邏輯關(guān)系約束的可行任務(wù)排序，根據(jù)染色體所對(duì)應(yīng)的任務(wù)調(diào)度順序和執(zhí)行模式序列可以獲得一個(gè)滿足資源約束的項(xiàng)目調(diào)度方案。應(yīng)用該編碼方法進(jìn)行選擇、交叉和變異等遺傳操作，能夠使搜索范圍遍及整個(gè)問題解空間。實(shí)際應(yīng)用表明，該算法能快速求得問題的最優(yōu)解或近似最優(yōu)解。

關(guān)鍵詞：多模式； 資源約束； 項(xiàng)目調(diào)度； 遺傳算法

中圖法分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001－3695(2007)01－0072－03

Key words：MultiMode; ResourceConstrained; Project Scheduling; Genetic Algorithm

資源約束項(xiàng)目調(diào)度問題(RCPSP)指的是一類在滿足項(xiàng)目資源約束和任務(wù)前后約束的條件下合理安排工程各作業(yè)的開始時(shí)間，以最小化項(xiàng)目總工期的調(diào)度問題。在傳統(tǒng)的RCPSP中，每項(xiàng)任務(wù)的工期和資源需求量都是固定的，稱為單模式資源約束項(xiàng)目調(diào)度問題（SRCPSP）。多模式資源約束項(xiàng)目調(diào)度問題（MRCPSP）是SRCPSP的擴(kuò)展，每項(xiàng)任務(wù)在執(zhí)行時(shí)有多種工期和資源需求量的組合形式可供選擇，與SRCPSP相比MRCPSP更接近工程實(shí)際。

MRCPSP與SRCPSP一樣也屬于NPhard問題，近年來該問題吸引著越來越多的學(xué)者對(duì)其進(jìn)行研究，并提出了各種各樣的優(yōu)化方法，概括起來可分為以下三類：以分支定界法為代表的精確類算法[1，2]；基于優(yōu)先規(guī)則的啟發(fā)式算法[3，4]；以遺傳算法和模擬退火算法為代表的智能優(yōu)化算法[5~7]。精確算法能求得小規(guī)模問題的最優(yōu)解，但對(duì)大規(guī)模問題無能為力；啟發(fā)式算法和智能優(yōu)化算法不能保證求得問題的最優(yōu)解，但在解決大規(guī)模問題時(shí)能在求解質(zhì)量和求解效率上獲得一種較好的平衡。本文針對(duì)MRCPSP提出了一種混合遺傳算法的解決策略。

1問題描述

在進(jìn)行問題描述之前，先作如下假設(shè)：

①任務(wù)一旦開始必須進(jìn)行到完工，中途不得中斷，不得改變執(zhí)行模式；

②資源均為可更新資源，即資源能力在項(xiàng)目工期范圍內(nèi)為均勻分布；

③每項(xiàng)任務(wù)所需資源量均小于資源的最大供應(yīng)量。

設(shè)項(xiàng)目工期為T；項(xiàng)目共包含n個(gè)任務(wù)，A={1，2，…，n}為項(xiàng)目的任務(wù)集，A中第1個(gè)和第n個(gè)任務(wù)是為了描述問題方便而增設(shè)的虛擬任務(wù)，其作用是標(biāo)記項(xiàng)目開始時(shí)間和結(jié)束時(shí)間，只有一種模式，持續(xù)時(shí)間和資源消耗量均為0；任務(wù)j共有Mj種模式，mj是任務(wù)j所采用的模式，在該模式下對(duì)第k種資源的消耗量為rjmjk，持續(xù)時(shí)間為djmj；任務(wù)j的開始時(shí)間為sj；At為時(shí)刻t正在進(jìn)行的任務(wù)集合；Pj為任務(wù)j的緊前任務(wù)集合；Rk是資源k的總量；K是不同資源類型的數(shù)量，則問題可以用數(shù)學(xué)語言描述如下：

式（1）定義的是目標(biāo)函數(shù)，即最小化項(xiàng)目工期；式(2)定義的是緊前約束關(guān)系，表示任務(wù)j必須在其所有緊前任務(wù)均已完工的情況下才能開始進(jìn)行；式(3)定義的是資源約束關(guān)系，即在時(shí)刻t進(jìn)行的所有任務(wù)對(duì)資源k的消耗量不能超過其限制的數(shù)量。

2染色體編碼和解碼

任務(wù)之間存在著緊前約束關(guān)系，任意的排序可能產(chǎn)生不可行的進(jìn)行次序，如何有效地產(chǎn)生能夠處理前后約束的編碼是遺傳算法解決該問題的關(guān)鍵。本文提出一種基于優(yōu)先權(quán)的編碼方案來解決該問題。

定義設(shè)有任務(wù)鏈表V=(i1，i2，…，in)，鏈表中的元素為各任務(wù)的編號(hào)，元素的下標(biāo)為元素所對(duì)應(yīng)任務(wù)在鏈表中的位置，如果Ｖ中各任務(wù)的排列順序滿足緊前約束關(guān)系，即如果i∈Pj，任務(wù)i在Ｖ中的位置處于任務(wù)j的前面，則稱Ｖ為緊前關(guān)系相容鏈表。

在算法中采用二維編碼方法來表示MRCPSP的解，該編碼方法如圖1所示。染色體表示的二維結(jié)構(gòu)由任務(wù)優(yōu)先權(quán)和任務(wù)執(zhí)行模式兩行組成：第一行中pi的值用來表示任務(wù)i的優(yōu)先權(quán)，是區(qū)間[0，1]內(nèi)的一個(gè)實(shí)數(shù)，數(shù)值越大則優(yōu)先權(quán)越高；第二行中mi是區(qū)間[1，Mi]內(nèi)的一個(gè)整數(shù)，用來表示任務(wù)i的執(zhí)行模式。

采用基于優(yōu)先權(quán)的編碼方法可以表示給定項(xiàng)目的所有可能緊前關(guān)系相容鏈表，并且任何染色體總是對(duì)應(yīng)著一個(gè)緊前關(guān)系相容鏈表。染色體的解碼過程分為兩步：

（1）根據(jù)染色體所表達(dá)的任務(wù)優(yōu)先權(quán)和執(zhí)行模式信息生成緊前關(guān)系相容鏈表和執(zhí)行模式序列。該過程按照一次通過方式進(jìn)行：從左到右一次確定一項(xiàng)任務(wù)在緊前關(guān)系相容鏈表中的位置以及該任務(wù)的執(zhí)行模式。該過程每一次迭代中的所有任務(wù)均處于下列三種狀態(tài)之一：

①已排序任務(wù)。已經(jīng)放入緊前關(guān)系相容鏈表中的任務(wù)。

②合格任務(wù)。緊前任務(wù)都是已排序任務(wù)的任務(wù)。

③自由任務(wù)。所有其他任務(wù)。

3適應(yīng)度函數(shù)

對(duì)染色體進(jìn)行解碼得到各任務(wù)的開始時(shí)間，利用式(1)可得到項(xiàng)目持續(xù)時(shí)間，即目標(biāo)函數(shù)值。由于MRCPSP的目標(biāo)是最小化項(xiàng)目工期，因此必須將原始目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)，以確保優(yōu)秀個(gè)體具有大的適應(yīng)度值。

設(shè)vk是當(dāng)前種群的第k個(gè)染色體， f(vk)是適應(yīng)度函數(shù)，Tk是目標(biāo)函數(shù)值，即項(xiàng)目持續(xù)時(shí)間，Tmax是當(dāng)前種群中的最大目標(biāo)函數(shù)值。轉(zhuǎn)換方法如下：

其中γ是一正整數(shù)，使用γ的目的是使選擇行為從適應(yīng)度比例選擇調(diào)整到純隨機(jī)選擇。當(dāng)染色體間適應(yīng)度值的差距相對(duì)較大時(shí)，為比例選擇；當(dāng)區(qū)別相對(duì)較小時(shí)，則選擇趨向于純隨機(jī)選擇。

4遺傳操作

4．1種群的初始化

按照任務(wù)ID對(duì)項(xiàng)目任務(wù)進(jìn)行升序排列，根據(jù)生成的排列順序隨機(jī)地為各任務(wù)指定一執(zhí)行模式，并生成區(qū)間[0，1]內(nèi)的一隨機(jī)實(shí)數(shù)序列作為各任務(wù)的優(yōu)先權(quán)，從而構(gòu)成一條染色體。按照該方法生成指定數(shù)目的個(gè)體構(gòu)成初始種群。

4．2選擇操作

由于選擇、交叉和變異等遺傳操作的隨機(jī)性，它們有可能破壞掉當(dāng)前種群中適應(yīng)度最好的個(gè)體，從而影響算法的收斂性。為了保證每一代的優(yōu)良個(gè)體不被破壞，采用最優(yōu)個(gè)體保留策略[8]。

4．3交叉操作

采用單點(diǎn)交叉算子來完成交叉操作。記參與交叉的兩個(gè)父代個(gè)體為A和B，隨機(jī)生成一整數(shù)q，1

4．4變異操作

采用單重均勻變異算子來完成對(duì)染色體的變異操作，變異算子依變異概率pm對(duì)染色體A中的每個(gè)分量進(jìn)行變異操作，得到子代個(gè)體A′。設(shè)染色體A的第q個(gè)基因發(fā)生變異，則子代個(gè)體A′各基因所表示的優(yōu)先權(quán)和執(zhí)行模式分別為

5實(shí)例計(jì)算分析

為了證明本算法的有效性，設(shè)計(jì)了一項(xiàng)目實(shí)例，該項(xiàng)目的網(wǎng)絡(luò)計(jì)劃圖如圖2所示，圖中共有20項(xiàng)任務(wù)，其中首尾節(jié)點(diǎn)是為了描述問題方便而增設(shè)的虛擬任務(wù)。該項(xiàng)目需要對(duì)兩種可更新資源R1和R2進(jìn)行約束優(yōu)化，資源R1和R2的限量分別為36和15。除起始任務(wù)和終止任務(wù)只有一種模式之外，其余各項(xiàng)任務(wù)均有兩種模式。該項(xiàng)目的具體參數(shù)如表1所示。

表1項(xiàng)目實(shí)例參數(shù)

在利用遺傳算法求解問題時(shí)，算法參數(shù)對(duì)算法性能影響非常大。在本實(shí)例中，取種群規(guī)模為50，用不同的交叉和變異概率進(jìn)行了反復(fù)實(shí)驗(yàn)，交叉概率分別取為0.1，0.2，0.3，…，0．9；變異概率取為0.01，0.02，…，0.09，共81種組合，每種組合實(shí)驗(yàn)50次。實(shí)驗(yàn)結(jié)果表明，當(dāng)交叉概率為0.4～0.6、變異概率為0.03～0.05時(shí)，利用遺傳算法進(jìn)行求解可獲得較好的算法性能。

如果項(xiàng)目中的所有任務(wù)只采用第一種模式或第二種模式，該MRCPSP轉(zhuǎn)換為SRCPSP。同樣在資源R1和R2的限量分別為36和15的約束條件下，所有任務(wù)只采用第一種模式時(shí)，項(xiàng)目的原始工期為46，利用分支定界法求得其最優(yōu)解為51；所有任務(wù)只采用第二種模式時(shí)，項(xiàng)目的原始工期為35，利用分支定界法求得其最優(yōu)解為41。由于該項(xiàng)目中除起止節(jié)點(diǎn)以外每個(gè)任務(wù)有兩種執(zhí)行模式，相當(dāng)于218個(gè)單模式項(xiàng)目，用分支定界法難以求出該MRCPSP的最優(yōu)解。利用本文所設(shè)計(jì)的遺傳算法能求得的問題最優(yōu)解為38，相對(duì)于只采用一種模式時(shí)的最優(yōu)解51和41來說有了較大的改善。當(dāng)取得最優(yōu)解38時(shí)各任務(wù)的執(zhí)行模式以及開始時(shí)間如表2所示。

表2優(yōu)化后的項(xiàng)目任務(wù)開始時(shí)間和執(zhí)行模式

6結(jié)論

本文針對(duì)多模式資源約束項(xiàng)目調(diào)度問題，采用了一種混合遺傳算法，設(shè)計(jì)了一種二維編碼方案，染色體的值對(duì)應(yīng)著各任務(wù)在進(jìn)行調(diào)度時(shí)的優(yōu)先權(quán)和執(zhí)行模式。根據(jù)任務(wù)的優(yōu)先權(quán)進(jìn)行解碼操作能獲得滿足任務(wù)之間邏輯關(guān)系約束的緊前關(guān)系相容鏈，能夠徹底避免不可行調(diào)度解的產(chǎn)生。實(shí)例計(jì)算表明該混合遺傳算法能快速有效地解決MRCPSP問題，是一種較好的搜索方法。

參考文獻(xiàn)：

［1］Sprecher A， Hartmann S， Drexl A. An Exact Algorithm for Project Scheduling with Multiple Modes[J]. OR Spektrum， 1997，19(3)：195203.

［2］Hartmann S， Drexl A. Project Scheduling with Multiple Modes： A Comparison of Exact Algorithms[J]. Networks，1998，32(4)：283297.

［3］Boctor F F. Heuristics for Scheduling Projects with Resource Restrictions and Several ResourceDuration Modes[J].International Journal of Production Research，1993，31(11)：25472558.

［4］Boctor F F. A New and Efficient Heuristic for Scheduling Projects with Resource Restrictions and Multiple Execution Modes[J].European Journal of Operational Research，1996，90(3)：349361.

［5］Alcaraz J， Maroto C， Ruiz R. Solving the MultiMode ResourceConstrained Project Scheduling Problem with Genetic Algorithms[J]. Journal of the Operational Research Society， 2003，54(6)：614626.

［6］Bouleimen K， Lecocq H. A New Efficient Simulated Annealing Algorithm for the ResourceConstrained Project Scheduling Problem and Its Multiple Mode Version[J]. European Journal of Operational Research， 2003，149(2)：268281.

［7］劉士新， 王夢(mèng)光， 聶義勇. 多執(zhí)行模式資源受限工程調(diào)度問題的優(yōu)化算法[J]. 系統(tǒng)工程學(xué)報(bào)， 2001，16(1)： 5560.

［8］侯健， 曲昌學(xué)， 陳月明， 等. 用基于實(shí)數(shù)編碼的自適應(yīng)遺傳算法求解產(chǎn)量預(yù)測(cè)模型[J]. 石油大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2002，26(3)：5559.

作者簡(jiǎn)介：

王為新（1980），男，山東鄆城人，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)輔助設(shè)計(jì)、項(xiàng)目網(wǎng)絡(luò)計(jì)劃優(yōu)化等；

李原（1964），女，陜西西安人，教授，博士，主要研究方向?yàn)橛?jì)算機(jī)輔助技術(shù)、并行工程與虛擬制造技術(shù)等；

張開富（1977），男，四川安岳人，博士研究生，主要研究方向?yàn)楹娇债a(chǎn)品項(xiàng)目管理、計(jì)算機(jī)輔助技術(shù)。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文