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

Murat Şahin () and Talip Kellegöz ()
Additional contact information
Murat Şahin: Celal Bayar University
Talip Kellegöz: Gazi University

Annals of Operations Research, 2023, vol. 321, issue 1, No 19, 507-540

Abstract: Abstract 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.

Keywords: Mathematical programming; Multi-manned assembly lines; Benders; Decomposition; Exact solution method; Assembly line balancing (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-05118-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:321:y:2023:i:1:d:10.1007_s10479-022-05118-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-05118-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().