研究生: |
李行秋 Anas Saifurrahman |
---|---|
論文名稱: |
應用改良之NSGA-II與子陣列矩陣切片方法於不等面積設施佈置問題 Applying Improved NSGA-II and Sub-Array Matrix Slicing Approach to Unequal Area Facility Layout |
指導教授: |
郭人介
Ren-Jieh Kuo |
口試委員: |
林希偉
Shi-Woei Lin 蔡榮發 Jung-Fa Tsai |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2022 |
畢業學年度: | 110 |
語文別: | 英文 |
論文頁數: | 135 |
中文關鍵詞: | 不等面積設施規劃問題 、非支配解排序之遺傳演算法 、非支配排序 、多目標演算法 、矩陣切片 |
外文關鍵詞: | UA-FLP, NSGA-II, Non-dominated sorting, Many-objective optimization, Matrix slicing |
相關次數: | 點閱:201 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
決定最佳設施規劃對於提高生產力具有非常大的影響。然而,設施規劃問題(FLP)基於其目標和配置已發展得更為複雜。不等面積的設施規劃問題(UA-FLP),由於其多樣的場地配置、不固定的走道距離和計算複雜性而具有挑戰性。除了 UA-FLP 模型的複雜性之外,現實世界中的 FLP 還利用多目標模型來表示材料移動方面以外的設施規劃。因此,本研究提出了一種萬用演算法,通過考慮三個目標函數(流量/距離測量、鄰接等級和危害移動)來解決多目標 UA-FLP。
本研究所提出的演算法,其使用矩陣切片機制,利用數組元素表示離散之佈局網格。每個部門被表示為較小的子陣列,以放置在較大的陣列中作為其廠區。這種離散方法採用由部門放置序列組成的染色體,該序列將用於多目標萬用演算法。提出的進化演算法是利用非支配排序遺傳演算法-II(NSGA-II),最優解包含一組對每個目標函數沒有任何優先的候選解。兩種演算法都增加了重複刪除機制,以保持解的多樣性並避免過早收斂。
根據計算結果,所提出的演算法能夠解決小、中及大型的多目標 UA-FLP。 NSGA-II 較 MOPSO 提供了更好的解決方法,特別是在兩點交配機制下,其適應值優於其他演算法。通過支配其他演算法的解決方法,具有兩點交配的 NSGA-II 也產生了更好的性能評估。
Determining an optimal facility placement in a production layout plays a crucial role in terms of improving productivity. However, the scope of facility layout problem (FLP) have developed a complex configuration based on its objective and placement. Facility layout problem with unequal area (UA-FLP) poses its own challenge due to its diverse department dimension, uncertain bay and computational complexity. In addition to the complex nature of UA-FLP model, real-world FLP encourages many-objective model to represent facility layout purposes other than material movement aspect. Therefore, this study proposes a metaheuristic algorithm to solve many-objective UA-FLP by considering three objective functions (flow/distance measurement, adjacency rating, and hazard movement).
The proposed algorithm uses a matrix slicing mechanism, by utilizing array elements as a discrete representation of layout grid. Each department is represented as smaller sub-array to be placed at larger array grid as its production floor. This discrete approach employs a chromosome that consist of department placement sequence that will be used in the multi-objective metaheuristics. The proposed evolutionary algorithms are non-dominated sorting genetic algorithm-II (NSGA-II) with the optimal solution contains a set of solution candidates that does not have any priorities on each objective function. Duplicate removal mechanism is added in the algorithm in order to preserve solution diversity and prevent early convergence.
Based on the computational result, the proposed algorithm is able to solve multi- objective UA-FLP on small, medium, and large data instances. The NSGA-II algorithm provide a better solution compared to MOPSO, especially with two-point crossover mechanism because the fitness value dominates the other algorithm. By dominating the other algorithm’s solution, the NSGA-II with two-point crossover
also yields a better performance evaluation
Aiello, G., La Scalia, G., and Enea, M., A multi-objective genetic algorithm for the facility layout problem based upon slicing structure encoding. Expert Systems with Applications, 39(12), 10352–10358, 2012.
Aiello, G., La Scalia, G., and Mario, E., A non-dominated ranking multi-objective genetic algorithm and electre method for unequal area facility layout problems, Expert Systems and Application, 40, 4812–4819, 2013.
Al Jadaan, O., Rajamani, L., & Rao, C. R., Non-dominated ranked genetic algorithm for solving constrained multi-objective optimization problems, Journal of Theoretical and Applied Information Technology, 640–651, 2009.
Anjos, M.F., and Vieira, M.V.C., Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions, European Journal of Operations Research, 261, 1–16, 2017.
Chae, J., and Regan, A.C., Layout design problems with heterogeneous area constraints, Computers & Industrial Engineering, 102, 198–207, 2016.
Chand, S., & Wagner, M., Evolutionary many-objective optimization: A quick-start guide, Surveys in Operations Research and Management Science, 20(2), 35– 42, 2015.
Cravo, G. L. and Amaral, A. R. S., A GRASP algorithm for solving large-scale single row facility layout problems, Computers and Operations Research, 106, 49–61, 2019.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6(2), 182–197, 2002.
Engelbrecht, A. P., Computational Intelligence: An Introduction. Chichester: Wiley, 2007.
Fahad, M., Naqvi, S.A.A., Atir, M., Zubair, M., and Shehzad, M. M., Energy management in a manufacturing industry through layout design, Procedia Manufacturing, 168–174, 2017.
El-Shorbagy, M. A., and Hassanien, A. E., Particle swarm optimization from theory to applications, International Journal of Rough Sets and Data Analysis, 5(2), 1–24, 2018.
Gonçalves, J. F., and Resende, M. G. C., A biased random-key genetic algorithm for the unequal area facility layout problem, European Journal of Operational Research, 246(1), 86–107, 2015.
Guerreiro, A. P., Fonseca, C. M., & Paquete, L. The hypervolume indicator: problems and algorithms, Arxiv Cornell University, 2020.
Hacizade, U., and Kaya, I., GA based traveling salesman problem solution and its application to transport routes optimization, IFAC-Papers Online, 51(30), 620–625, 2018.
Hadi-Vencheh, A., and Mohamadghasemi, A., An integrated AHP-NLP methodology for facility layout design, Journal of Manufacturing Systems, 32(1), 40, 2013.
Hari Prasad, N., Rajyalakshmi, G., and Sreenivasulu Reddy, A., A typical manufacturing plant layout design using CRAFT algorithm, Procedia Engineering, 97, 1808–1814, 2014.
Heizer, J., Render, B., and Munson, C., Operations management, 12th Edition, Pearson Education, Inc., London, 2017.
Ho, P., Applying Multi-Objective Metaheuristics to Container Loading Problem Considering Truck Utilization and Balance, National Taiwan University of Science and Technology, 2021.
Hosseini-Nasab, H., Fereidouni, S., Fatemi Ghomi, S.M.T., and Fakhrzad, M.B., Classification of facility layout problems: a review study, International Journal of Advanced Manufacturing and Technology, 94, 957–977, 2018.
Ishibuchi, H., Tsukamoto, N., and Nojima, Y., Evolutionary many-objective optimization: A short review, IEEE Congress on Evolutionary Computation, 2008.
Kennedy, J., and Eberhart, R. C., Particle swarm optimization, Proceedings of the 1995 IEEE International Conference on Neural Networks, Perth, Australia, Vol. 4, 1942–1948, 1995, 27 November – 1 December.
Klausnitzer and Lasch, R., Optimal facility layout and material handling network design, Computers and Operations Research, 237–251, 2019.
Kulturel-Konak, S., Approaches to uncertainties in facility layout problems: Perspectives at the beginning of the 21st Century, Journal of Intelligent Manufacturing, 18, 273–284, 2007.
Lee, J. E., Gen, M., & Rhee, K. G., Network model and optimization of reverse logistics by hybrid genetic algorithm, Computers and Industrial Engineering, 56(3), 951–964, 2009.
Li, J., Tan, X., and Li, J. Research on dynamic facility layout problem of manufacturing unit considering human factors, Mathematical Problems in Engineering, 2018, 1-13, 2018.
Liu, J., and Liu, J., Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout problems, Applied Soft Computing Journal, 74, 167–189, 2019.
Liu, J., Zhang, H., He, K., and Jiang, S., Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem, Expert Systems with Applications, 102, 179–192, 2018.
Long, Q., Wu, X., and Wu, C., Non-dominated sorting methods for multi-objective optimization: review and numerical comparison, Journal of Industrial and Management Optimization, 17(2), 1001–1023, 2021.
Matai, R., Singh, S.P., and Mittal, M.L., Facility layout problem: A state-of-the-art review, XIMB Journal of Management, 7, 81–106, 2010.
Montgomery, D.C., Applied Statistics and Probability for Engineers. John Wiley & Sons, 2003.
Ning, X., Qi, J., Wu, C., and Wang, W., Reducing noise pollution by planning construction site layout via a multi-objective optimization model, Journal of Cleaner Production, 222, 218–230, 2019.
Ojaghi, Y., Khademi, A., Yusof, N.M., Renani, N.G., and Hassan, S.A.H.B.S., Production layout optimization for small and medium scale food industry, Procedia CIRP, 247–251, 2015.
Pérez-Gosende, P., Mula, J., and Díaz-Madroñero, M., Facility layout planning. An extended literature review, International Journal of Production Research, 12, 1-16, 2021.
Rabbani, M., Navazi, F., Farrokhi-Asl, H, dan Balali, M. H., A sustainable transportation-location-routing problem with soft time windows for distribution systems, Uncertain Supply Chain Management, 6(3), 229–254, 2018.
Safarzadeh, S. and Koosha, H., Solving an extended multi-row facility layout problem with fuzzy clearances using GA, Applied Soft Computing Journal, 819–831, 2017.
Saifurrahman, A., Facility Layout Design for CNC Batik Machine Fabrication Using Systematic Layout Planning, Universitas Gadjah Mada, 2020.
Saraswat, A., Venkatadri, U., and Castillo, I., A framework for multi-objective facility layout design, Computers & Industrial Engineering, 90, 167–176, 2015.
Taghavi, A. and Murat, A., A heuristic procedure for the integrated facility layout design and flow assignment problem, Computers & Industrial Engineering, 61, 55–63, 2011.
Tayal, A. and Singh, S. P., Integrating big data analytic and hybrid firefly-chaotic simulated annealing approach for facility layout problem, Annals of Operations Research, 270(1–2), 489–514, 2018.
Tompkins, J. A., White, J. A., Bozer, Y. A., and Tanchoco, J. M. A., Facilities Planning, Wiley, 2010.
Wang, R., Zhao, H., Wu, Y., Wang, Y., Feng, X., and Liu, M., An industrial facility layout design method considering energy saving based on surplus rectangle fill algorithm, Energy, 1038–1051, 2018.