基于遺傳算法的多模式資源約束項目調度問題研究
2007-01-01 00:00:00王為新李原張開富
計算機應用研究 2007年1期
摘要：為解決多模式資源約束項目調度問題，提出了一種混合遺傳算法的求解方法。該算法采用二維編碼方法來表示問題的解，基因的值表示任務的優先權和執行模式，每條染色體對應一個滿足邏輯關系約束的可行任務排序，根據染色體所對應的任務調度順序和執行模式序列可以獲得一個滿足資源約束的項目調度方案。應用該編碼方法進行選擇、交叉和變異等遺傳操作，能夠使搜索范圍遍及整個問題解空間。實際應用表明，該算法能快速求得問題的最優解或近似最優解。
關鍵詞：多模式； 資源約束； 項目調度； 遺傳算法
中圖法分類號：TP391文獻標識碼：A
文章編號：1001－3695(2007)01－0072－03
Key words：MultiMode; ResourceConstrained; Project Scheduling; Genetic Algorithm
資源約束項目調度問題(RCPSP)指的是一類在滿足項目資源約束和任務前后約束的條件下合理安排工程各作業的開始時間，以最小化項目總工期的調度問題。在傳統的RCPSP中，每項任務的工期和資源需求量都是固定的，稱為單模式資源約束項目調度問題（SRCPSP）。多模式資源約束項目調度問題（MRCPSP）是SRCPSP的擴展，每項任務在執行時有多種工期和資源需求量的組合形式可供選擇，與SRCPSP相比MRCPSP更接近工程實際。
MRCPSP與SRCPSP一樣也屬于NPhard問題，近年來該問題吸引著越來越多的學者對其進行研究，并提出了各種各樣的優化方法，概括起來可分為以下三類：以分支定界法為代表的精確類算法[1，2]；基于優先規則的啟發式算法[3，4]；以遺傳算法和模擬退火算法為代表的智能優化算法[5~7]。精確算法能求得小規模問題的最優解，但對大規模問題無能為力；啟發式算法和智能優化算法不能保證求得問題的最優解，但在解決大規模問題時能在求解質量和求解效率上獲得一種較好的平衡。本文針對MRCPSP提出了一種混合遺傳算法的解決策略。
1問題描述
在進行問題描述之前，先作如下假設：
①任務一旦開始必須進行到完工，中途不得中斷，不得改變執行模式；
②資源均為可更新資源，即資源能力在項目工期范圍內為均勻分布；
③每項任務所需資源量均小于資源的最大供應量。
設項目工期為T；項目共包含n個任務，A={1，2，…，n}為項目的任務集，A中第1個和第n個任務是為了描述問題方便而增設的虛擬任務，其作用是標記項目開始時間和結束時間，只有一種模式，持續時間和資源消耗量均為0；任務j共有Mj種模式，mj是任務j所采用的模式，在該模式下對第k種資源的消耗量為rjmjk，持續時間為djmj；任務j的開始時間為sj；At為時刻t正在進行的任務集合；Pj為任務j的緊前任務集合；Rk是資源k的總量；K是不同資源類型的數量，則問題可以用數學語言描述如下：
式（1）定義的是目標函數，即最小化項目工期；式(2)定義的是緊前約束關系，表示任務j必須在其所有緊前任務均已完工的情況下才能開始進行；式(3)定義的是資源約束關系，即在時刻t進行的所有任務對資源k的消耗量不能超過其限制的數量。
2染色體編碼和解碼
任務之間存在著緊前約束關系，任意的排序可能產生不可行的進行次序，如何有效地產生能夠處理前后約束的編碼是遺傳算法解決該問題的關鍵。本文提出一種基于優先權的編碼方案來解決該問題。
定義設有任務鏈表V=(i1，i2，…，in)，鏈表中的元素為各任務的編號，元素的下標為元素所對應任務在鏈表中的位置，如果Ｖ中各任務的排列順序滿足緊前約束關系，即如果i∈Pj，任務i在Ｖ中的位置處于任務j的前面，則稱Ｖ為緊前關系相容鏈表。
在算法中采用二維編碼方法來表示MRCPSP的解，該編碼方法如圖1所示。染色體表示的二維結構由任務優先權和任務執行模式兩行組成：第一行中pi的值用來表示任務i的優先權，是區間[0，1]內的一個實數，數值越大則優先權越高；第二行中mi是區間[1，Mi]內的一個整數，用來表示任務i的執行模式。
采用基于優先權的編碼方法可以表示給定項目的所有可能緊前關系相容鏈表，并且任何染色體總是對應著一個緊前關系相容鏈表。染色體的解碼過程分為兩步：
（1）根據染色體所表達的任務優先權和執行模式信息生成緊前關系相容鏈表和執行模式序列。該過程按照一次通過方式進行：從左到右一次確定一項任務在緊前關系相容鏈表中的位置以及該任務的執行模式。該過程每一次迭代中的所有任務均處于下列三種狀態之一：
①已排序任務。已經放入緊前關系相容鏈表中的任務。
②合格任務。緊前任務都是已排序任務的任務。
③自由任務。所有其他任務。
3適應度函數
對染色體進行解碼得到各任務的開始時間，利用式(1)可得到項目持續時間，即目標函數值。由于MRCPSP的目標是最小化項目工期，因此必須將原始目標函數轉換為適應度函數，以確保優秀個體具有大的適應度值。
設vk是當前種群的第k個染色體， f(vk)是適應度函數，Tk是目標函數值，即項目持續時間，Tmax是當前種群中的最大目標函數值。轉換方法如下：
其中γ是一正整數，使用γ的目的是使選擇行為從適應度比例選擇調整到純隨機選擇。當染色體間適應度值的差距相對較大時，為比例選擇；當區別相對較小時，則選擇趨向于純隨機選擇。
4遺傳操作
4．1種群的初始化
按照任務ID對項目任務進行升序排列，根據生成的排列順序隨機地為各任務指定一執行模式，并生成區間[0，1]內的一隨機實數序列作為各任務的優先權，從而構成一條染色體。按照該方法生成指定數目的個體構成初始種群。
4．2選擇操作
由于選擇、交叉和變異等遺傳操作的隨機性，它們有可能破壞掉當前種群中適應度最好的個體，從而影響算法的收斂性。為了保證每一代的優良個體不被破壞，采用最優個體保留策略[8]。
4．3交叉操作
采用單點交叉算子來完成交叉操作。記參與交叉的兩個父代個體為A和B，隨機生成一整數q，1 4．4變異操作 采用單重均勻變異算子來完成對染色體的變異操作，變異算子依變異概率pm對染色體A中的每個分量進行變異操作，得到子代個體A′。設染色體A的第q個基因發生變異，則子代個體A′各基因所表示的優先權和執行模式分別為 5實例計算分析 為了證明本算法的有效性，設計了一項目實例，該項目的網絡計劃圖如圖2所示，圖中共有20項任務，其中首尾節點是為了描述問題方便而增設的虛擬任務。該項目需要對兩種可更新資源R1和R2進行約束優化，資源R1和R2的限量分別為36和15。除起始任務和終止任務只有一種模式之外，其余各項任務均有兩種模式。該項目的具體參數如表1所示。 表1項目實例參數 在利用遺傳算法求解問題時，算法參數對算法性能影響非常大。在本實例中，取種群規模為50，用不同的交叉和變異概率進行了反復實驗，交叉概率分別取為0.1，0.2，0.3，…，0．9；變異概率取為0.01，0.02，…，0.09，共81種組合，每種組合實驗50次。實驗結果表明，當交叉概率為0.4～0.6、變異概率為0.03～0.05時，利用遺傳算法進行求解可獲得較好的算法性能。 如果項目中的所有任務只采用第一種模式或第二種模式，該MRCPSP轉換為SRCPSP。同樣在資源R1和R2的限量分別為36和15的約束條件下，所有任務只采用第一種模式時，項目的原始工期為46，利用分支定界法求得其最優解為51；所有任務只采用第二種模式時，項目的原始工期為35，利用分支定界法求得其最優解為41。由于該項目中除起止節點以外每個任務有兩種執行模式，相當于218個單模式項目，用分支定界法難以求出該MRCPSP的最優解。利用本文所設計的遺傳算法能求得的問題最優解為38，相對于只采用一種模式時的最優解51和41來說有了較大的改善。當取得最優解38時各任務的執行模式以及開始時間如表2所示。 表2優化后的項目任務開始時間和執行模式 6結論 本文針對多模式資源約束項目調度問題，采用了一種混合遺傳算法，設計了一種二維編碼方案，染色體的值對應著各任務在進行調度時的優先權和執行模式。根據任務的優先權進行解碼操作能獲得滿足任務之間邏輯關系約束的緊前關系相容鏈，能夠徹底避免不可行調度解的產生。實例計算表明該混合遺傳算法能快速有效地解決MRCPSP問題，是一種較好的搜索方法。 參考文獻： ［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］劉士新， 王夢光， 聶義勇. 多執行模式資源受限工程調度問題的優化算法[J]. 系統工程學報， 2001，16(1)： 5560. ［8］侯健， 曲昌學， 陳月明， 等. 用基于實數編碼的自適應遺傳算法求解產量預測模型[J]. 石油大學學報(自然科學版)， 2002，26(3)：5559. 作者簡介： 王為新（1980），男，山東鄆城人，碩士研究生，主要研究方向為計算機輔助設計、項目網絡計劃優化等； 李原（1964），女，陜西西安人，教授，博士，主要研究方向為計算機輔助技術、并行工程與虛擬制造技術等； 張開富（1977），男，四川安岳人，博士研究生，主要研究方向為航空產品項目管理、計算機輔助技術。 注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
