Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

• Type: Article in International Scientific Journal
• Date: 2016

Authors

Goncalves, TC (Author) Other; Jorge M S Valente (Author) FEP; Schaller, JE (Author) Other

Journal

Title: Computers and Operations Research

Vol. 70

Pages: 115-126

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 9 Citations

Scopus - 10 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12