Iterated greedy local search methods for unrelated parallel machine scheduling

Área de Investigación: Articulos Año: 2010
Tipo de publicación: Artículo
Autores: Fanjul, Luis; Ruiz, Rubén
Revista: European Journal of Operational Research Volumen: 207
Número: 1 Páginas: 55-69
Also available at
This work deals with the parallel machines scheduling problem which consists in the assignment of n jobs on m parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machines problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (Cmax). Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.
Versión digital