MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines

Alexandre Dolgui 1 Anton Eremeev Olga Guschinskaya 2, 3
1 Laboratoire en Sciences et Technologies de l'Information
MSGI-ENSMSE - Département Méthodes Scientifiques pour la Gestion Industrielle, ROGI-ENSMSE - Equipe : Recherche Opérationnelle pour le Génie Industriel
Abstract : Abstract In this chapter, we consider a problem of balancing transfer lines with multi-spindle machines. The problem has a number of distinct features in comparison with the well-studied assembly line balancing problem, such as parameterized operation times, non-strict precedence constraints, and parallel operations execution. We propose a mixed-integer programming (MIP)-based greedy randomized adaptive search procedure (GRASP) and a genetic algorithm (GA) for this problem using a MIP formulation. Both algorithms are implemented in GAMS using the CPLEX MIP solver and compared to problem-specific heuristics on randomly generated instances of different types. The results of computational experiments indicate that on large-scale problem instances the proposed methods have an advantage over the methods from literature for finding high quality solutions. The MIP-based recombination operator that arranges the elements of parent solutions in the best possible way is shown to be useful in the GA.
Document type :
Book sections
Liste complète des métadonnées

Contributor : Florent Breuil <>
Submitted on : Wednesday, February 22, 2012 - 4:21:41 PM
Last modification on : Monday, January 14, 2019 - 12:08:18 PM



Alexandre Dolgui, Anton Eremeev, Olga Guschinskaya. MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines. Maniezzo, Vittorio; Stützle, Thomas; Voß, Stefan. Matheuristics, Springer US, pp.189-208, 2010, ⟨10.1007/978-1-4419-1306-7_7⟩. ⟨emse-00673081⟩



Record views