| Issue |
RAIRO-Oper. Res.
Volume 41, Number 2, April-June 2007
ROADEF 05
|
|
|---|---|---|
| Page(s) | 193 - 211 | |
| DOI | https://doi.org/10.1051/ro:2007018 | |
| Published online | 15 June 2007 | |
Metaheuristics based on Bin Packing for the line balancing problem
1
Université Blaise Pascal, LIMOS CNRS UMR 6158, ISIMA, BP 10125, 63173 Aubière Cedex, France; grangeon@isima.fr; gourgand@isima.fr
2
Université Blaise Pascal,
LIMOS CNRS UMR 6158,
Antenne IUT de Montluçon,
Avenue Aristide Briand,
03100 Montluçon, France; norre@moniut.univ-bpclermont.fr
Received:
6
October
2006
Accepted:
15
November
2006
The line balancing problem consits in assigning tasks to stations in order to respect precedence constraints and cycle time constraints. In this paper, the cycle time is fixed and the objective is to minimize the number of stations. We propose to use metaheuristics based on simulated annealing by exploiting the link between the line balancing problem and the bin packing problem. The principle of the method lies in the combination between a metaheuristic and a bin packing heuristic. Two representations of a solution and two neighboring systems are proposed and the methods are compared with results from the literature. They are better or similar to tabu search based algorithm.
Mathematics Subject Classification: 90Bxx
Key words: Flow-shop / stochastic / Markovian analysis / simulation / metaheuristic
© EDP Sciences, ROADEF, SMAI, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.