Benders’ decomposition based exact solution method for multi-manned assembly line balancing problem with walking workers

Şahin M., KELLEGÖZ T.

Annals of Operations Research, cilt.321, sa.1-2, ss.507-540, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 321 Sayı: 1-2
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1007/s10479-022-05118-z
  • Dergi Adı: Annals of Operations Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Computer & Applied Sciences, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.507-540
  • Anahtar Kelimeler: Mathematical programming, Multi-manned assembly lines, Benders, Decomposition, Exact solution method, Assembly line balancing
  • Gazi Üniversitesi Adresli: Evet

Özet

© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.This article considers multi-manned assembly line balancing problems with walking workers. The objective of the problem is the minimization of number of workers and workstations simultaneously. Several exact-solution algorithms based on Benders’ decomposition are proposed to solve the problem optimally. In one of the algorithms a constructive heuristic that generates effective task-worker assignments and some problem-specific symmetry breaking constraints are used. Moreover, the solutions obtained by meta-heuristic in the literature are used as starting points to increase the performance of proposed decomposition methods. A benchmark set of 99 instances are used to analyze the performance of the proposed exact methods, contribution of the developed heuristic and the ability of Benders’ decomposition on improving the starting solutions. Our results indicate a significiant improvement in the optimal solvability of the problem for larger-sized instances. Suggested methods also improve the results of the meta-heuristic method for significant number of instances. Consequntly, proposed methods solved most of instances optimally and they are able to find the optimal solutions of 17 instances that cannot be solved optimally with previous methods.