Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

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

Authors

Jorge M S Valente (Author) FEP; Rui A F S Alves (Author) FEP

Journal

Title: Computers and Operations Research

Vol. 35 No. 11

Pages: 3696-3713

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 18 Citations

ISI Web of Science

Scopus - 29 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-003-V2A

DOI: 10.1016/j.cor.2007.04.006

Abstract (EN): In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule. The computational experiments show that the best results are provided by the heuristics that explicitly consider both early and tardy costs, and the quadratic objective function. Therefore, it is indeed important to specifically address the quadratic feature of the cost function, instead of simply using procedures originally developed for a linear objective function. The heuristics are quite fast, and are capable of quickly solving even very large instances. The use of an improvement step is recommended, since it usually improves the solution quality with little additional computational effort.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18