Fanjul Peyró, L.; Ruiz García, R. (2011). Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers and Operations Research. 38(1):301-309. doi:10.1016/j.cor.2010.05.005
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/35334
Title:
|
Size-reduction heuristics for the unrelated parallel machines scheduling problem
|
Author:
|
Fanjul Peyró, Luis
Ruiz García, Rubén
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat
Universitat Politècnica de València. Instituto Universitario Mixto Tecnológico de Informática - Institut Universitari Mixt Tecnològic d'Informàtica
|
Issued date:
|
|
Abstract:
|
[EN] In this paper we study the unrelated parallel machines problem where n independent jobs must be
assigned to one out of m parallel machines and the processing time of each job differs from machine to
machine. We deal ...[+]
[EN] In this paper we study the unrelated parallel machines problem where n independent jobs must be
assigned to one out of m parallel machines and the processing time of each job differs from machine to
machine. We deal with the objective of the minimisation of the maximum completion time of the jobs,
usually referred to as makespan or Cmax. This is a type of assignment problem that has been frequently
studied in the scienti¿c literature due to its many potential applications. We propose a set of
metaheuristics based on a size-reduction of the original assignment problem that produce solutions of
very good quality in a short amount of time. The underlying idea is to consider only a few of the best
possible machine assignments for the jobs and not all of them. The results are simple, yet powerful
methods. We test the proposed algorithms with a large benchmark of instances and compare them with
current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results
that are statistically proven to be better by a signi¿cant margin.
& 2010 Elsevier Ltd. All rights reserved
[-]
|
Subjects:
|
Unrelated parallel machines
,
Makespan
,
Size-reduction
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
Computers and Operations Research. (issn:
0305-0548
)
|
DOI:
|
10.1016/j.cor.2010.05.005
|
Publisher:
|
Elsevier
|
Publisher version:
|
http://dx.doi.org/10.1016/j.cor.2010.05.005
|
Conference name:
|
11th International Workshop on Project Management and Scheduling
|
Conference place:
|
Estambul, Turkey
|
Conference date:
|
August 28-30, 2008
|
Project ID:
|
IMPIVA/IMIDIC/2008/137
UPV/PPAR/3147
MICINN/DPI2008-03511/DPI
|
Thanks:
|
This work is partially funded by the Spanish Ministry of Science and Innovation, under the project ‘‘SMPA—Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances’’ with references number DPI2008-03511/DPI. ...[+]
This work is partially funded by the Spanish Ministry of Science and Innovation, under the project ‘‘SMPA—Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances’’ with references number DPI2008-03511/DPI. The
authors should also thank the IMPIVA—Institute for the Small and Medium Valencian Enterprise, for the project OSC with
reference IMIDIC/2008/137 and the Polytechnic University of Valencia, for the project PPAR with reference 3147.
[-]
|
Type:
|
Artículo
Comunicación en congreso
|