應用瀰集進化演算法於多資源限制專案排程問題解算效果之分析

Memetic Algorithms for the Resource-Constrained Project Scheduling Problem

陳芝傑(Zhi-Jie Chen)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(2005年)

摘要

本研究使用兩種混合策略瀰集進化演算法（Memetic algorithm；MA）求解多資源限制專案排程問題，MA為一個以母體為基底之進化演算法（Population based evolutionary algorithm），主要特性為應用區域搜尋法或廣泛區域搜尋法諸如模擬退火等，使得母體中每一個體為一個區域最佳解（Local optimum）。
兩個MA演算法之解碼方式（產生作業排程）皆採混合策略：當問題之資源限制屬緊湊型，則使用平行法（Parallel method）將作業排序表單（Activity List；AL）解碼成作業排程；反之若屬於寬鬆型，則使用序列法（Serial method）。本論文發展適當的編碼、重組、突變等演算操作方式並同時納入菁英收斂政策與隨機發散政策。
兩個MA之主要差別在於區域搜尋法之使用方式，第一個MA採用混合三種區域搜尋法（Multi-local search；MLS），簡稱MA-MLS；三種區域搜尋法分別為最左移動搜尋、強力最左移動搜尋、交換搜尋，過程中以資源衝突測試來判斷一個區域搜尋法是否值得進行，降低無謂的搜尋次數以提昇求解效率。第二個MA發展出右�左區域移動作業排序調整法（Right/left local-shift activity reordering technique）作為區域搜尋方式並應用於每一解碼後之個體，簡稱MA-R/L。
本研究採用國際測試題庫（PSPLIB）之j30，j60，j120驗證兩個演算法之求解效率，在5,000與50,000個解為比較基準下，MA-R/L略優於MA-MLS，但兩個演算法相對於目前發表之一些最佳解算法皆表現出顯著之競爭力

關鍵字

資源限制 ； 瀰集進化演算法 ； 基因演算法 ； 專案排程 ； 區域搜尋法

並列摘要

This paper proposes two memetic algorithms (MAs), which are MA-MLS and MA-R/L, for the classical resource-constrained project scheduling problem (RCPSP). The objective of the RCPSP is to minimize the total project completion time. The heuristic first identifies the problem structure and then decides which one of the serial method or the parallel method is used to decode activity lists of the problem. MA-MLS uses three local search schemes equally to refine the schedules: left-move, enhanced left-move, and swap. A resource conflict test is performed to avoid ineffective attempt before making a local search move. In MA-R/L, a local search procedure using right/left local-shift activity reordering technique is applied to refine each decoded schedule. The mechanism of the recombination and the mutation operators are capable of exploring new search regions where are in turn efficiently searched by the local search procedure. The mutation operation is performed only when the population converges. Computational experiments with PSPLIB J30, J60, J120 instances show that the proposed MA is among the best ones currently available for RCPSP. Experimental analyses regarding the effects of algorithm parameters are also included. Computational experiments with PSPLIB instances show that the MAs are among the best heuristics currently available for the RCPSP.

並列關鍵字

Memetic algorithms ； Local search ； Resource constraints ； Project scheduling

參考文獻

[1]　高文慶，「螞蟻演算法於有限資源專案排程最佳化之研究」，元智大學工業工程與管理研究所碩士論文 （2004）。

[5]　錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究」，元智大學工業工程研究所碩士論文 （1999）。

[7] Blazewicz, J., Lenstra, J. K., and Rinooy Kan, A. H. G.. (1983), “Scheduling subject to resource constraints: Classification and complexity,” Discrete Applied Mathematics 5, 11-24.

[8] Boctor, F., F. (1990) “Some efficient multi-heuristic procedures for resource-constrained project scheduling problems,” European Journal of Operational Research, 49: 3-13.

[9] Bouleimen, K. and Lecocq, H. (2003), “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, 149, 268-281.