臺灣博碩士論文加值系統

本研究使用兩種混合策略瀰集進化演算法（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.

中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章　導論 1
1.1 研究背景 1
1.2 研究目的 1
1.3 研究範疇及假設 2
1.4 論文架構與研究流程 2
第二章 文獻探討 4
2.1　多資源限制專案排程問題文獻回顧 4
2.2 啟發式方法 6
2.3 瀰集進化演算法 14
2.3.1 瀰集進化演算法之介紹 15
2.3.2 編碼（Encoding） 16
2.3.3 初始母體（Initial Population） 17
2.3.4 區域搜尋（Local Search） 17
2.3.5 重組（Recombination） 18
2.3.6 取代 22
2.3.7 突變（mutation） 22
2.3.8 停止條件 22
第三章　問題敘述與數學模式 24
3.1 問題描述 24
3.2 數學模式 25
第四章　研究方法 28
4.1 研究方法之架構 28
4.2 瀰集進化演算法應用於此研究之解算流程介紹 31
4.2.1 計算題目參數 31
4.2.2 編碼方式 33
4.2.3 產生初始母體 33
4.2.4 資源衝突測試 34
4.2.5 區域搜尋法 36
4.2.6 計算目標值 41
4.2.7 選擇父母親 42
4.2.8 重組方式 42
4.2.9 比較與維持母體個數（精英政策） 43
4.2.10 收斂測試與突變方式 43
4.2.11 停止條件 44
第五章　初步研究結果與後續研究 45
5.1 MA-MLS實驗分析 45
5.1.1 資源衝突測試之效果分析 45
5.1.2 MA-MLS緊湊型與寬鬆型分類實驗 46
5.1.3 MA–MLS參數設定與實驗結果 47
5.2 MA-R/L實驗分析 50
5.2.1 MA-R/L緊湊型與寬鬆型分類實驗 51
5.2.2 MA–LSR參數設定與實驗結果 51
5.3 MA-MLS、MA-R/L與國際論文紀錄解算效果之比較 53
第六章　結論與後續建議 56
參考文獻 58

一、中文部分：
[1]　高文慶，「螞蟻演算法於有限資源專案排程最佳化之研究」，元智大學工業工程與管理研究所碩士論文 （2004）。
[2]　趙淑妙譯，自私的基因（Dawkins, R., 1976），初版，台北：天下遠見出版股份有限公司，頁 287-306 （1995）。
[3]　蔡登茂，「有限資源專案排程問題之文獻回顧研究」，正修學報，第九期，57～74頁 （1996）。
[4] 蔡登茂，「有限資源多專案排程啟發法之績效評估及其應用」，技術學刊，第十一卷，第四期，第547-562頁 （1996）。
[5]　錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究」，元智大學工業工程研究所碩士論文 （1999）。
二、英文部分：
[6] Areibi, A., Moussa, M. and Abdullah, H. (2001), “A comparison of genetic/memetic algorithms and other heuristic search techniques,” in International Conference on Artificial Intellegence, Las Vegas, Nevada, June 2001, 660-666
[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.
[10] Brucker, P., Drexl, A., Mohring, R., Neumann, K. and Pesch, E. (1999), “Resource-constrained project scheduling: Notation, classification, models, and methods,” European Journal of Operational Research, 112, 3-41.
[11] Brucker, P. and Knust, S. (2000), “A linear programming and constraint propagation-based lower bound for the RCPSP,” European Journal of Operational Research, 127, 355-362.
[12] Brucker, P. and Knust, S. (2003), “Lower bounds for resource-constrained project scheduling problems,” European Journal of Operational Research, 149, 302-313.
[13] Dorndorf, U., Pesch, E. and Phan-Huy, T. (2000), “A branch and bound algorithm for the resource-constrained project scheduling problem,” Mathematical Methods of Operations Researrch, 52, 413-439.
[14] Freszar, K. and Hindi, K. S. (2004), “Solving the resource-constrained project scheduling problem by a variable neighbourhood search,” European Journal of Operational Research, 155, 402-413.
[15] Hartmann, S. (1998), “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research Logistics, 45, 733-750.
[16] Hartmann, S. (2002), “A self-adapting genetic algorithm for project scheduling under resource constraints,” Naval Research Logistics, 49, 433-448.
[17] Hartmann, S. and Kolisch, R. (2000), “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” European Journal of Operational Research, 127, 394-407.
[18]Herroelen, W., De. Reyck, B., and Demeulemeester, E. (1998), “Resource-constrained project scheduling: A survey of recent developments,” Computers and Operations Research, 25 (4), 279-302.
[19] Klein, R. (2000), “Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects,” European Journal of Operational Research, 127, 619-638.
[20] Kolisch, R. (1996), “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation,” European Journal of Operational Research, 90, 320-333.
[21] Kolisch, R. and Sprecher, A. (1996), “PSPLIB – A project scheduling problem library,” European Journal of Operational Research, 96, 205-216.
[22] Kolisch, R., Sprecher, A. and Drexl, A. (1995), “Characterization and generation of a general class of resource-constrained project scheduling problems,” Management Science, 41, 693-1703.
[23] Li, K. Y. and Willis R. J. (1992), “An iterative scheduling technique for resource-constrained project scheduling,” European Journal of Operational Research, 56, 370-379.
[24] Merkle, D., Middendorf, M. and Schmeck, H. (2002), “Ant colony optimization for resource-constrained project scheduling,” IEEE Transactions on Evolutionary Computation, 6, 333-346.
[25] Merz, R. (2002), “A comparison of memetic recombination operators for the traveling salesman problem,” in GECCO 2002: proceedings of the Genetic and Evolutionary Computation Conference, (Langdon, W. B. et al., eds.), Morgan Kaufman, 472-479.
[26] Merz, R. and Freisleben, B. (2000), “Fitness landscape analysis and memetic algorithms for the quadratic assignment problem,” IEEE Transactions on Evolutionary Computation, 4 (4), 337-352.
[27] , R. H., Schulz, A. Z., Stork, F., and Uetz, M. (2003), “Solving project scheduling problems by minimum cut computations,” Management Science, 49 (3), 330-350.
[28] Moscato, P. (1989), “On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms,” Tech. Rep., Caltech Concurrent Computation Program, California Institute of Technology, Pasadena, California, USA, Report.826.
[29] Nonobe, K. and Ibaraki, T. (2001), “Formulation and tabu search algorithm for the resource constrained project scheduling problem,” Essays and Surveys in Metaheuristics, (Ribero, C.C. and Hansen, P. eds.), Kluwer Academic Publishers, Dordrecht, The Netherlands, 557-588.
[30] Sprecher, A., Kolisch, R. and Drexl, A. (1995), “Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem,” European Journal of Operational Research, 80, 94-102.
[31] Tormos, P. and Lova, A. (2001), “A competitive heuristic solution technique for resource-constrained project scheduling,” Annals of Operations Research, 102, 65-81.
[32] Valls, V., Ballestin, F. and Quintanilla, S. (2003), “Resource-constrained project scheduling: A critical activity reordering heuristic,” European Journal of Operational Research, 149, 282-301.
[33] Valls, V., Ballestin, F. and Quintanilla, S. （2005）, “Justification and RCPSP: A technique that pays”, European Journal of Operational Research, 165, 375-386.
[34] Zou, P., Zhou, Z., Chen, G.-L. and Yao, X. （2004）, “A novel memetic algorithm with random multi-local-search: a case study of TSP”, in CECCO 2004: Proeedings of the 2004 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, USA, 19-23 June 2004, Portland, Oregon, USA, 2335-2340.