A Reactive GRASP and Path Relinking for Balancing Reconfigurable Transfer Lines

Mohamed Essafi 1 Xavier Delorme 2, 3, 4 Alexandre Dolgui 2, 3, 4
1 Laboratoire en Sciences et Technologies de l'Information
LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes, ROGI-ENSMSE - Equipe : Recherche Opérationnelle pour le Génie Industriel, DEMO-ENSMSE - Département Décision en Entreprise : Modélisation, Optimisation
Abstract : A line balancing problem for reconfigurable transfer lines with sequence-dependent setup times and parallel machines was studied. These lines are paced and serial, i.e. a part to be machined passes through a sequence of stations. Stations are composed of CNC (Computer Numerical Control) machines. At least one CNC machine is installed at each station. These CNC machines are mono-spindle head machines, hence setup times between operations have to be taken into account. The origins of setup times are various, for example, the necessity to rotate the part, change and displace the tool, etc. Because of setup times, the station workload depends on the sequence in which the operations are assigned to the station. In addition, accessibility constraints have to be considered. The objective consists of assigning a given set of operations as well as machines to a sequence of workstations in order to minimise the total cost of the line. Keeping in mind the industrial importance of this problem and the lack of available methods in the literature tackling it efficiently, we propose a new heuristic based on GRASP combined with Path Relinking. A MIP approach is used to select the sequences of operations on workstations. Numerical experiments are presented and show that the proposed heuristic can provide good solutions even for large-sized instances while requiring a computational time that is fully compatible with a practical application. An industrial case study is also described.
Document type :
Journal articles
Complete list of metadatas

Contributor : Florent Breuil <>
Submitted on : Thursday, May 3, 2012 - 9:46:15 AM
Last modification on : Thursday, May 9, 2019 - 10:36:04 AM



Mohamed Essafi, Xavier Delorme, Alexandre Dolgui. A Reactive GRASP and Path Relinking for Balancing Reconfigurable Transfer Lines. International Journal of Production Research, Taylor & Francis, 2012, Volume 50 (Issue 18), p. 5213-5238. ⟨10.1080/00207543.2012.677864⟩. ⟨emse-00693913⟩



Record views