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.
Type de document :
Chapitre d'ouvrage
Maniezzo, Vittorio; Stützle, Thomas; Voß, Stefan. Matheuristics, Springer US, pp.189-208, 2010, 〈10.1007/978-1-4419-1306-7_7〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00673081
Contributeur : Florent Breuil <>
Soumis le : mercredi 22 février 2012 - 16:21:41
Dernière modification le : mardi 22 mars 2016 - 01:15:59

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

78