Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

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

Authors

Jorge M S Valente (Author) FEP; Jeffrey E Schaller (Author) Other

Journal

Title: Computers and Operations Research

Vol. 39 No. 9

Pages: 2223-2231

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 18 Citations

ISI Web of Science

Scopus - 21 Citations

COMPENDEX

INSPEC

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-002-6ST

DOI: 10.1016/j.cor.2011.11.005

Abstract (EN): In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered. The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances. The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 9