A balance-first sequence-last algorithm to design RMS: a matheuristic with performance guaranty to balance reconfigurable manufacturing systems

Youssef Lahrichi (), Laurent Deroussi (), Nathalie Grangeon () and Sylvie Norre ()
Additional contact information
Youssef Lahrichi: Université Clermont Auvergne
Laurent Deroussi: Université Clermont Auvergne
Nathalie Grangeon: Université Clermont Auvergne
Sylvie Norre: Université Clermont Auvergne

Journal of Heuristics, 2021, vol. 27, issue 1, No 5, 107-132

Abstract: Abstract The Reconfigurable Transfer Line Balancing Problem (RTLB) is considered in this paper. This problem is quite recent and motivated by the growing need of reconfigurability in the new industry 4.0 context. The problem consists into allocating a set of operations necessary to machine a single part to different workstations placed into a serial line. Each workstation can contain multiple machines operating in parallel and the tasks allocated to a workstation should be sequenced since sequence-dependent setup times between operations are needed to perform tool changes. Besides, precedence constraints, inclusion, exclusion and accessibility constraints between operations are considered. In this article we propose an efficient matheuristic of type Balance First, Sequence Last (BFSL). This method is a two-step heuristic with a constructive phase and an improvement phase. It contains several components from exact methods (linear programming, constraint generation and dynamic programming) and metaheuristics (simulated annealing). In addition, we show that the constructive algorithm approximates the optimal solution when the setup times are bounded by the processing times and give an approximation ratio. The obtained results show the effectiveness of the proposed approach. The matheuristic clearly outperforms a genetic algorithm from literature on quite large benchmark instances.

Keywords: RTLB; Line balancing; Constraint generation; Simulated annealing; Matheuristic; Approximation algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-021-09473-1 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:joheur:v:27:y:2021:i:1:d:10.1007_s10732-021-09473-1

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

DOI: 10.1007/s10732-021-09473-1

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

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