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
Document type :
Conference papers
Liste complète des métadonnées

Contributor : Florent Breuil <>
Submitted on : Thursday, February 23, 2012 - 11:15:08 AM
Last modification on : Monday, January 14, 2019 - 12:08:18 PM


  • HAL Id : emse-00673272, version 1


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. ⟨emse-00673272⟩



Record views