Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2016

Autores

Goncalves, TC (Autor) Outra; Jorge M S Valente (Autor) FEP; Schaller, JE (Autor) Outra

Revista

Título: Computers and Operations Research

Vol. 70

Páginas: 115-126

ISSN: 0305-0548

Editora: Elsevier

Indexação

ISI Web of Knowledge - 10 Citações

Scopus - 10 Citações

Outras Informações

ID Authenticus: P-00K-3BG

DOI: 10.1016/j.cor.2016.01.004

Abstract (EN): This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed. The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12