Exact and heuristic methods for solving the Robotic Assembly Line Balancing Problem

Leonardo Borba, Marcus Ritt and Cristóbal Miralles

European Journal of Operational Research, 2018, vol. 270, issue 1, 146-156

Abstract: In robotic assembly lines, the task times depend on the robots assigned to each station. Robots are considered an unlimited resource and multiple robots of the same type can be assigned to different stations. Thus, the Robotic Assembly Line Balancing Problem (RALBP) consists of assigning a set of tasks and a type of robot to each station, subject to precedence constraints between the tasks. This paper proposes a lower bound, and exact and heuristic algorithms for the RALBP. The lower bound uses chain decomposition to explore the graph dependencies. The exact approaches include a novel linear mixed-integer programming model and a branch-bound-and-remember algorithm with problem-specific dominance rules. The heuristic solution is an iterative beam search with the same rules. To fully explore the different characteristics of the problem, we also propose a new set of instances. The methods and algorithms are extensively tested in computational experiments showing that they are competitive with the current state of the art.

Keywords: Production; Robotic assembly line balancing; Branch-bound-and-remember; Beam search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718302200
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:270:y:2018:i:1:p:146-156

DOI: 10.1016/j.ejor.2018.03.011

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 ().