MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines

A. Dolgui 1, O. Guschinskaya 2, A. Eremeev 3

1 Ecole des Mines de Saint Etienne, Saint Etienne, France
e-mail: dolgui@emse.fr

2 Ecole des Mines de Saint Etienne, Saint Etienne, France
e-mail: oln2000@mail.ru

3 Omsk Branch of Sobolev Institute of Mathematics SB RAS, Omsk, Russia
e-mail: eremeev@ofim.oscsbras.ru

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