MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines - Mines Saint-Étienne
Book Sections Year : 2010

MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines

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

Dates and versions

emse-00673081 , version 1 (22-02-2012)

Identifiers

Cite

Alexandre Dolgui, Anton Eremeev, Olga Battaïa. 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⟩
81 View
0 Download

Altmetric

Share

More