A Balance-First Sequence-Last Algorithm to design RMS A Matheuristic with performance guaranty to balance Reconfigurable Manufacturing Systems
| Autor: | Nathalie Grangeon, Sylvie Norre, Youssef Lahrichi, Laurent Deroussi |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Control and Optimization Linear programming Computer Networks and Communications Computer science Heuristic (computer science) 0211 other engineering and technologies Constraint generation 02 engineering and technology Management Science and Operations Research Simulated annealing 020901 industrial engineering & automation Artificial Intelligence Matheuristics Line balancing Metaheuristic 021103 operations research Reconfigurability Approximation algorithm [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Dynamic programming Benchmark (computing) RTLB Software Information Systems |
| Zdroj: | Journal of Heuristics Journal of Heuristics, 2021, 27, pp.107-132. ⟨10.1007/s10732-021-09473-1⟩ Journal of Heuristics, Springer Verlag, 2021, 27, pp.107-132. ⟨10.1007/s10732-021-09473-1⟩ |
| ISSN: | 1381-1231 1572-9397 |
| DOI: | 10.1007/s10732-021-09473-1⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink