Heuristics for the single machine scheduling problem with early and quadratic tardy penalties

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

Authors

Jorge M S Valente (Author) FEP

Journal

Title: European Journal of Industrial Engineering

Vol. 1

Pages: 431-448

ISSN: 1751-5254

Publisher: Inderscience Publishers

Indexing

ISI Web of Knowledge - 24 Citations

ISI Web of Science

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-004-D3J

DOI: 10.1504/ejie.2007.015391

Abstract (EN): This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of these rules, Linear early/quadratic tardy dispatching rules are also considered, as well as a greedy-type procedure. Extensive experiments are performed to determine appropriate values for the parameters required by some of the heuristics. The computational tests show that the best results are given by the linear early/quadratic tardy dispatching rule. This procedure is also quite efficient, and can quickly solve even very large instances. [Received 15 December 2006; Revised 20 July 2007; Accepted 24 July 2007]

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18