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


Annals of Operations Research, 2022 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Publication Date: 2022
  • Doi Number: 10.1007/s10479-022-05118-z
  • Journal Name: Annals of Operations Research
  • Journal Indexes: 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
  • Keywords: Assembly line balancing, Benders, Decomposition, Exact solution method, Mathematical programming, Multi-manned assembly lines
  • Gazi University Affiliated: Yes


© 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.