A Benders’ decomposition algorithm with combinatorial cuts for the multi-manned assembly line balancing problem

Adalberto Sato Michels, Thiago Cantos Lopes, Celso Gustavo Stall Sikora and Leandro Magatão

European Journal of Operational Research, 2019, vol. 278, issue 3, 796-808

Abstract: Multi-manned assembly lines are commonly found in industries that manufacture large-size products (e.g. automotive industry), in which multiple workers are assigned to the same station in order to perform different operations simultaneously on the same product. Although the balancing problem of multi-manned assembly lines had been modelled before, the previously presented exact mathematical formulations are only able to solve few small-size instances, while larger cases are solved by heuristics or metaheuristics that do not guarantee optimality. This work presents a new Mixed-Integer Linear Programming model with strong symmetry break constraints and decomposes the original problem into a new Benders’ Decomposition Algorithm to solve large instances optimally. The proposed model minimises the total number of workers along the line and the number of opened stations as weighted primary and secondary objectives, respectively. Besides, feasibility cuts and symmetry break constraints based on combinatorial Benders’ cuts and model’s parameters are applied as lazy constraints to reduce search-space by eliminating infeasible sets of allocations. Tests on a literature dataset have shown that the proposed mathematical model outperforms previously developed formulations in both solution quality and computational processing time for small-size instances. Moreover, the proposed Benders’ Decomposition Algorithm yielded 117 optimal results out of a 131-instances dataset. Compared to previously presented methods, this translates to 19 and 25 new best solutions reached for medium and large-size instances, respectively, of which 19 and 23 are optimal solutions.

Keywords: Combinatorial optimisation; Multi-manned assembly line balancing; Benders’ decomposition; Combinatorial Benders’ cuts; Mixed-integer linear programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719303844
Full text for ScienceDirect subscribers only

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:eee:ejores:v:278:y:2019:i:3:p:796-808

DOI: 10.1016/j.ejor.2019.05.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().