Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một phương pháp tìm kiếm thích nghi chiến lược khu phố biến đổi mới cho bài toán SALBP-2 với giới hạn về số loại máy
Tóm tắt
Bài báo này trình bày phương pháp mới mang tên chiến lược khu phố biến đổi tìm kiếm thích nghi (VaNSAS) nhằm giải quyết đặc biệt bài toán cân bằng dây chuyền lắp ráp loại 2 (SALBP-2S), trong đó xem xét giới hạn của công nhân đa kỹ năng. Mục tiêu là tối thiểu hóa thời gian chu kỳ trong khi xem xét số lượng hạn chế các loại máy tại một trạm làm việc cụ thể. VaNSAS bao gồm hai bước: (1) tạo ra một tập hợp các đường đi và (2) thực hiện quy trình du lịch đường đi (TTP). Trong quá trình TTP, các đường đi được chọn và sử dụng một hộp đen với chiến lược khu phố nhằm cải thiện giải pháp thu được từ bước (1). Ba chiến lược khu phố cải tiến đã được thiết kế để sử dụng như các hộp đen: (1) thuật toán tiến hóa vi thế cải tiến (MDE), (2) tìm kiếm khu phố lớn (LNS) và (3) hoán đổi thời gian xử lý ngắn nhất (SPT-SWAP). Phương pháp đề xuất đã được thử nghiệm với hai tập dữ liệu, bao gồm (1) 128 trường hợp kiểm tra tiêu chuẩn của SALBP-2 và (2) 21 tập dữ liệu ngẫu nhiên của SALBP-2S. Kết quả tính toán từ tập dữ liệu đầu tiên cho thấy VaNSAS vượt trội hơn phương pháp tốt nhất đã biết (tìm kiếm chùm lặp (IBS)) và tất cả các phương pháp tiêu chuẩn khác. VaNSAS có thể tìm thấy 98,4% giải pháp tối ưu trong tất cả các trường hợp thử nghiệm, trong khi IBS chỉ tìm thấy 95,3% giải pháp tối ưu. MDE, LNS và SPT-SWAP có thể tìm thấy giải pháp tối ưu tương ứng là 85,9%, 83,6% và 82,8%. Ở nhóm các trường hợp kiểm tra thứ hai, chúng tôi phát hiện rằng VaNSAS có thể tìm thấy 100% giải pháp tối thiểu trong số tất cả các phương pháp, trong khi MDE, LNS và SPT-SWAP chỉ tìm thấy lần lượt 76,19%, 61,90% và 52,38% giải pháp tối thiểu.
Từ khóa
#SALBP-2 #chiến lược khu phố biến đổi #tìm kiếm thích nghi #công nhân đa kỹ năng #tối thiểu hóa thời gian chu kỳTài liệu tham khảo
Akpınar, Ş. (2017). Large neighbourhood search algorithm for type-II assembly line balancing problem. Pamukkale University Journal of Engineering Sciences, 23(4), 444–450. https://doi.org/10.5505/pajes.2016.75975
Álvarez-Miranda, E., Chace, S., & Pereira, J. (2020). Assembly line balancing with parallel workstations. International Journal of Production Research. https://doi.org/10.1080/00207543.2020.1818000
Amous, M., Toumi, S., Jarboui, B., & Eddaly, M. (2017). A variable neighborhood search algorithm for the capacitated vehicle routing problem. Electronic Notes in Discrete Mathematics, 58, 231–238. https://doi.org/10.1016/j.endm.2017.03.030
Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 168(3), 694–715. https://doi.org/10.1016/j.ejor.2004.07.023
Blum, C. (2011). Iterative beam search for simple assembly line balancing with a fixed number of work stations. Sort, 35(2), 145–164.
Çil, Z. A., Mete, S., Özceylan, E., & Ağpak, K. (2017). A beam search approach for solving type II robotic parallel assembly line balancing problem. Applied Soft Computing, 61, 129–138. https://doi.org/10.1016/j.asoc.2017.07.062
Gutjahr, A. L., & Nemhauser, G. L. (1964). An Algorithm for the line balancing problem. Management Science, 11(2), 308–315. https://doi.org/10.1287/mnsc.11.2.308
Lei, D., & Guo, X. (2016). Variable neighborhood search for the second type of two-sided assembly line balancing problem. Computers and Operations Research, 72(1), 183–188. https://doi.org/10.1016/j.cor.2016.03.003
Li, Y., Wang, H., & Yang, Z. (2019). Type II assembly line balancing problem with multi-operators. Neural Computing and Applications, 31(s1), 347–357. https://doi.org/10.1007/s00521-018-3834-1
Li, Z., Janardhanan, M. N., Tang, Q., & Nielsen, P. (2018). Mathematical model and metaheuristics for simultaneous balancing and sequencing of a robotic mixed-model assembly line. Engineering Optimization, 50(5), 877–893. https://doi.org/10.1080/0305215X.2017.1351963
Li, Z., Kucukkoc, I., & Zhang, Z. (2020). Branch, bound and remember algorithm for two-sided assembly line balancing problem. European Journal of Operational Research, 284(3), 896–905. https://doi.org/10.1016/j.ejor.2020.01.032
Lotfi, R., Mehrjerdi, Y. Z., Pishvaee, M. S., Sadeghieh, A., & Weber, G. W. (2019). A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization. https://doi.org/10.3934/naco.2020023
Mete, S., Çil, Z. A., Özceylan, E., Ağpak, K., & Battaïa, O. (2018). An optimisation support for the design of hybrid production lines including assembly and disassembly tasks. International Journal of Production Research, 56(24), 7375–7389. https://doi.org/10.1080/00207543.2018.1428774
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2
Nanthamroeng, N. (2010). Development of meta-heuristics for multiobjective and multi stage location routing problem. Thesis for Doctor of Philosophy in Industrial Engineering, Ubon Ratchathani University.
Nearchou, A. C. (2005). A differential evolution algorithm for simple assembly line balancing. In IFAC proceedings volumes (IFAC-PapersOnline) (Vol. 16). Doi: https://doi.org/10.3182/20050703-6-cz-1902.01463
Otto, A., & Otto, C. (2014). How to design effective priority rules: Example of simple assembly line balancing. Computers & Industrial Engineering, 69, 43–52. https://doi.org/10.1016/j.cie.2013.12.013
Phonganant, S. (2017). Expert system for mixed-model assembly line balancing. Journal of Thonburi University., 1(1), 37–46.
Pitakaso, R., & Sethanan, K. (2016). Modified differential evolution algorithm for simple assembly line balancing with a limit on the number of machine types. Engineering Optimization, 48(2), 253–271. https://doi.org/10.1080/0305215X.2015.1005082
Pitakaso, R., Sethanan, K., & Jamrus, T. (2020a). Hybrid PSO and ALNS algorithm for a software and mobile application for transportation in the ice manufacturing industry 3.5. Computers & Industrial Engineering, 144, 106461. https://doi.org/10.1016/j.cie.2020.106461
Pitakaso, R., Sethanan, K., & Theeraviriya, C. (2020b). Variable neighborhood strategy adaptive search for solving green 2-echelon location routing problem. Computers and Electronics in Agriculture, 173, 105406. https://doi.org/10.1016/j.compag.2020.105406
Promseenong, Y. (2015). Variable neighborhood search algorithms for dynamic vehicle routing problem with time windows. Thesis M.Eng in Management Engineering, Naresuan University.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135
Roshani, A., & Giglio, D. (2015). A simulated annealing approach for multi-manned assembly line balancing problem type II. IFAC-PapersOnLine, 28(3), 2299–2304. https://doi.org/10.1016/j.ifacol.2015.06.430
Sadeghi, P., Rebelo, R. D., & Ferreira, J. S. (2018). Balancing mixed-model assembly systems in the footwear industry with a variable neighbourhood descent method. Computers & Industrial Engineering, 121, 161–176. https://doi.org/10.1016/j.cie.2018.05.020
Scholl, A. (1993). Data of assembly line balancing problem. https://assembly-line-balancing.de/.
Scholl, A., & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168(3), 666–693. https://doi.org/10.1016/j.ejor.2004.07.022
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher & J.-F. Puget (Eds.), BT—Principles and practice of constraint programming—CP98. Springer.
Sikora, C. G. S., Lopes, T. C., Lopes, H. S., & Magatão, L. (2016). Genetic algorithm for type-2 assembly line balancing. 2015 Latin-America Congress on Computational Intelligence, LA-CCI 2015, (November 2016). Doi: https://doi.org/10.1109/LA-CCI.2015.7435951.
Sivasankaran, P., & Shahabudeen, P. (2014). Literature review of assembly line balancing problems. International Journal of Advanced Manufacturing Technology, 73(9–12), 1665–1694. https://doi.org/10.1007/s00170-014-5944-y
Storn, R., & Price, K. (1997). Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359. https://doi.org/10.1023/A:1008202821328
Wu, C., Hu, X., Zhang, Y., & Wang, P. (2019). A modified Monte-Carlo tree search algorithm for two-sided assembly line balancing problem. IFAC-PapersOnLine, 52(13), 1920–1924. https://doi.org/10.1016/j.ifacol.2019.11.483
Zare Mehrjerdi, Y., & Lotfi, R. (2019). Development of a mathematical model for sustainable closed-loop supply chain with efficiency and resilience systematic framework. International Journal of Supply and Operations Management, 6(4), 360–388. https://doi.org/10.22034/2019.4.6
Zhang, H. Y. (2017). An improved immune algorithm for simple assembly line balancing problem of type 1. Journal of Algorithms & Computational Technology, 11(4), 317–326. https://doi.org/10.1177/1748301817710924
Zheng, Q., Li, M., Li, Y., & Tang, Q. (2013). Station ant colony optimization for the type 2 assembly line balancing problem. International Journal of Advanced Manufacturing Technology, 66(9–12), 1859–1870. https://doi.org/10.1007/s00170-012-4465-9