臺灣博碩士論文加值系統

目前求解資源限制專案排程問題 (Resource-Constrained Project Scheduling Problem, RCPSP) 的文獻，大多注重於求解單目標問題，又以專案完工時間 (makespan) 當作目標為大多數。而在實務中，專案經理對專案考慮的目標往往是多方面的，除了專案完工時間之外，也須考量如何在讓所有的工作在所規定的時間內完成，避免工作的延遲導致成本的大幅提高。因此本研究針對最小化專案完工時間以及最小化總延遲時間 (total tardiness) 兩項目標進行求解。
本研究提出MOMA/D-IGR來求解此問題，改良自MOEA/D [7]，為了增加族群的多樣性，在環境選擇機制上，讓子代可取代的個數限制為一個，並且不讓相同個體進行取代更新。接著提出四種區域搜尋策略，希望能讓族群中的個體分採用求解方向對應之區域搜尋方法。實驗的測試問題採用Xiao等人 [15] 所提出的測試問題集，並與Xiao等人 [15] 所提出的6種演算法進行比較，分別為SPEA2、SPEA2-EM、NSGAII、NSGAII-EM、MOEA/D 以及MOEA/D-EM。實驗結果顯示MOMA/D-IGR能得出最好的效果。

致謝 i
摘要 ii
附表目錄 v
附圖目錄 vi
第一章 緒論 1
1.1 研究背景 1
1.2 問題定義 3
1.2.1 資源限制專案排程問題 3
1.2.2 多目標最佳化問題 5
1.2.3 多目標資源限制專案排程問題 7
1.3 多目標啟發式演算法 8
1.3.1 柏拉圖模擬退火法 (Pareto Simulated Annealing, PSA) 8
1.3.2 NSGAII 8
1.4 研究目的 9
第二章 文獻探討 10
2.1 編碼與解碼 10
2.1.1 編碼 11
2.1.2 解碼 11
2.2 初始化族群 14
2.3 交配方法 17
2.4 區域搜尋法 21
2.5 環境選擇 23
第三章 研究方法 26
3.1 MOEA/D簡介 26
3.2 MOMA/D-IGR 28
3.3 編碼 29
3.4 解碼方式 29
3.5 初始化族群 29
3.6 適應值評估 30
3.7 親代選擇 31
3.8 交配 31
3.9 區域搜尋 32
3.10 突變 35
3.11 環境選擇 35
第四章 實驗分析 36
4.1 測試問題 36
4.2 效能評估方式 36
4.2.1 多目標最佳化問題效能評估方式 36
4.3 實驗與討論 41
4.3.1 編碼與交配方法之影響 42
4.3.2 初始化族群測試 48
4.3.3 環境選擇測試 50
4.3.4 區域搜尋測試 53
4.3.5 區域搜尋策略測試 55
4.3.6 突變與區域搜尋測試 62
4.4 效能評比 65
4.4.1 比較文獻 65
第五章 結論與未來發展 67
參考文獻 68

[1] J. E. Kelley, "The critical-path method: Resources planning and scheduling," Industrial Scheduling, vol. 13, pp. 347-365, 1963.
[2] S. Hartmann and D. Briskorn, "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, vol. 207, pp. 1-14, 2010.
[3] P. Czyzżak and A. Jaszkiewicz, "Pareto simulated annealing—a metaheuristic technique for multiple‐objective combinatorial optimization," Journal of Multi‐Criteria Decision Analysis, vol. 7, pp. 34-47, 1998.
[4] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 6, pp. 182-197, 2002.
[5] N. Srinivas and K. Deb, "Muiltiobjective optimization using nondominated sorting in genetic algorithms," Evolutionary Computation, vol. 2, pp. 221-248, 1994.
[6] F. Ballestín and R. Blanco, "Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems," Computers & Operations Research, vol. 38, pp. 51-62, 2011.
[7] Q. Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based on decomposition," IEEE Transactions on Evolutionary Computation, vol. 11, pp. 712-731, 2007.
[8] S. Hartmann and R. Kolisch, "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," European Journal of Operational Research, vol. 127, pp. 394-407, 2000.
[9] E. W. Davis and J. H. Patterson, "A comparison of heuristic and optimum solutions in resource-constrained project scheduling," Management Science, vol. 21, pp. 944-955, 1975.
[10] R. Alvarez-Valdés and J. M. Tamarit, "Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis," in Advances in Project Scheduling. vol. 9, ed: Elsevier Amsterdam, 1989, pp. 113-134.
[11] R. Kolisch, "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, vol. 90, pp. 320-333, 1996.
[12] R. Zamani, "A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem," European Journal of Operational Research, vol. 229, pp. 552-559, 2013.
[13] D. Debels, B. De Reyck, R. Leus, and M. Vanhoucke, "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, vol. 169, pp. 638-653, 2006.
[14] Ş. İ. Birbil and S.-C. Fang, "An electromagnetism-like mechanism for global optimization," Journal of Global Optimization, vol. 25, pp. 263-282, 2003.
[15] J. Xiao, Z. Wu, X.-X. Hong, J.-C. Tang, and Y. Tang, "Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP," European Journal of Operational Research, vol. 251, pp. 22-35, 2016.
[16] K. Li and R. Willis, "An iterative scheduling technique for resource-constrained project scheduling," European Journal of Operational Research, vol. 56, pp. 370-379, 1992.
[17] V. Valls, F. Ballestı́n, and S. Quintanilla, "Justification and RCPSP: A technique that pays," European Journal of Operational Research, vol. 165, pp. 375-386, 2005.
[18] R. Kolisch, A. Sprecher, and A. Drexl, "Characterization and Generation of a General Class of Resource-constrained Project Scheduling Problems," Management Science, vol. 41, pp. 1693-1703, 1995.
[19] S. Hartmann, "A competitive genetic algorithm for resource‐constrained project scheduling," Naval Research Logistics (NRL), vol. 45, pp. 733-750, 1998.
[20] F. Ballestin, V. Valls, and S. Quintanilla, "Due dates and RCPSP," in Perspectives in Modern Project Scheduling. vol. 92, ed: Springer, 2006, pp. 79-104.
[21] F. Ballestín and R. Blanco, "A hybrid genetic algorithm with transmitted justification for the RCPSP with due dates," BEIO, Boletín de Estadística e Investigación Operativa, vol. 30, pp. 125-149, 2014.
[22] M. P. Hansen, "Tabu search for multiobjective optimization: MOTS," in Proceedings of the 13th International Conference on Multiple Criteria Decision Making, 1997, pp. 574-586.
[23] A. Viana and J. P. de Sousa, "Using metaheuristics in multiobjective resource constrained project scheduling," European Journal of Operational Research, vol. 120, pp. 359-374, 2000.
[24] M. A. Al-Fawzan and M. Haouari, "A bi-objective model for robust resource-constrained project scheduling," International Journal of Production Economics, vol. 96, pp. 175-187, 2005.
[25] B. Abbasi, S. Shadrokh, and J. Arkat, "Bi-objective resource-constrained project scheduling with robustness and makespan criteria," Applied Mathematics and Computation, vol. 180, pp. 146-152, 2006.
[26] L. Wang, C. Fang, C.-D. Mu, and M. Liu, "A Pareto-archived estimation-of-distribution algorithm for multiobjective resource-constrained project scheduling problem," IEEE Transactions on Engineering Management, vol. 60, pp. 617-626, 2013.
[27] E. Zitzler, M. Laumanns, and L. Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm: Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische Informatik und Kommunikationsnetze (TIK), 2001.
[28] E. Zitzler and L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach," IEEE Transactions on Evolutionary Computation, vol. 3, pp. 257-271, 1999.
[29] V. Valls, F. Ballestin, and S. Quintanilla, "A hybrid genetic algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, vol. 185, pp. 495-508, 2008.
[30] S. Khalili, A. A. Najafi, and S. T. A. Niaki, "Bi-objective resource constrained project scheduling problem with makespan and net present value criteria: two meta-heuristic algorithms," The International Journal of Advanced Manufacturing Technology, vol. 69, pp. 617-626, 2013.
[31] P.-C. Chang, S.-H. Chen, and K.-L. Lin, "Two‐phase sub population genetic algorithm for parallel machine-scheduling problem," Expert Systems with Applications, vol. 29, pp. 705-712, 2005.
[32] J. K. Cochran, S.-M. Horng, and J. W. Fowler, "A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines," Computers & Operations Research, vol. 30, pp. 1087-1102, 2003.
[33] Z. Wang, Q. Zhang, A. Zhou, M. Gong, and L. Jiao, "Adaptive replacement strategies for MOEA/D," IEEE Transactions on Cybernetics, vol. 46, pp. 474-486, 2016.
[34] R. Kolisch and A. Sprecher, "PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program," European Journal of Operational Research, vol. 96, pp. 205-216, 1996.
[35] E. Zitzler and L. Thiele, "Multiobjective optimization using evolutionary algorithms—a comparative case study," in International Conference on Parallel Problem Solving from Nature, 1998, pp. 292-301.
[36] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, "Performance assessment of multiobjective optimizers: an analysis and review," IEEE Transactions on Evolutionary Computation, vol. 7, pp. 117-132, 2003.
[37] M. Fleischer, "The Measure of Pareto Optima. Applications to Multi-objective Metaheuristics," in Evolutionary Multi-Criterion Optimization: Second International Conference, EMO 2003, Faro, Portugal, April 8–11, 2003. Proceedings, C. M. Fonseca, P. J. Fleming, E. Zitzler, L. Thiele, and K. Deb, Eds., ed Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 519-533.
[38] G. Minella, R. Ruiz, and M. Ciavotta, "A review and evaluation of multiobjective algorithms for the flowshop scheduling problem," INFORMS Journal on Computing, vol. 20, pp. 451-471, 2008.