Iterated greedy local search methods for unrelated parallel machine scheduling
| Area d'investigacio: | Articulos | Any: | 2010 | ||||
|---|---|---|---|---|---|---|---|
| Tipus de publicacio: | Articul | ||||||
| Autors: | Fanjul, Luis; Ruiz, Rubén | ||||||
| Revista: | European Journal of Operational Research | Volum: | 207 | ||||
| Número: | 1 | Pagines: | 55-69 | ||||
| Nota: | Also available at http://www.upv.es/deioac/Investigacion/Paralelas_Fanjul.pdf |
||||||
| Abstract: | 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. |
||||||
| Versio digital | |||||||