研究生: |
王映萱 Wang, Ying-Suan |
---|---|
論文名稱: |
以分解型演化演算法求解多目標資源限制專案排程問題 A Decomposition-based Memetic Algorithm for Multiobjective Resource Constrained Project Scheduling Problem |
指導教授: |
蔣宗哲
Chiang, Tsung-Che |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2017 |
畢業學年度: | 105 |
語文別: | 中文 |
論文頁數: | 71 |
中文關鍵詞: | 資源限制專案排程問題 、多目標最佳化問題 、多目標啟發式演算法 |
DOI URL: | https://doi.org/10.6345/NTNU202203485 |
論文種類: | 學術論文 |
相關次數: | 點閱:119 下載:10 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
目前求解資源限制專案排程問題 (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能得出最好的效果。
[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.