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
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00673272
Contributor : Florent Breuil <>
Submitted on : Thursday, February 23, 2012 - 11:15:08 AM
Last modification on : Thursday, October 17, 2019 - 12:36:37 PM

Identifiers

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

Share

Metrics

Record views

161