MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines

Abstract : In this paper, we consider a problem of balancing transfer lines with multi-spindle machines. The problem has a number of distinct features in comparison with the wellstudied Assembly Line Balancing Problem, such as parameterized operation times, nonstrict precedence constraints, and parallel operations execution. We propose MIP-based greedy randomized adaptive search procedure (GRASP) and genetic algorithm (GA) for this problem using MIP formulation [2]. The solution construction and the local improvement stages of GRASP are based on solving sub-problems of smaller size. The same solution construction method is used for initialization of the initial population in the GA. The crossover and mutation in the GA are combined in MIP-recombination operator [1]. Both algorithms are implemented in GAMS using CPLEX MIP solver and compared to the problem-specific heuristics [3] on randomly generated instances of different type. The results of computational experiments indicate that on the large-scale problems the methods proposed are in advantage to the previous methods in finding the high quality solutions
Type de document :
Communication dans un congrès
Second international workshop on model based metaheuristics, Jun 2008, Bertinoro, Italy. 22p, 2008
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00673272
Contributeur : Florent Breuil <>
Soumis le : jeudi 23 février 2012 - 11:15:08
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

  • HAL Id : emse-00673272, version 1

Citation

Alexandre Dolgui, Olga Guschinskaya, Anton Eremeev. MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines. Second international workshop on model based metaheuristics, Jun 2008, Bertinoro, Italy. 22p, 2008. 〈emse-00673272〉

Partager

Métriques

Consultations de la notice

91