MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines - Mines Saint-Étienne Access content directly
Conference Papers Year : 2008

MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines


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
No file

Dates and versions

emse-00673272 , version 1 (23-02-2012)


  • HAL Id : emse-00673272 , version 1


Alexandre Dolgui, Olga Battaïa, 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⟩
103 View
0 Download


Gmail Mastodon Facebook X LinkedIn More