Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

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

Authors

Jorge M S Valente (Author) FEP

Journal

Title: Computers and Industrial Engineering

Vol. 52 No. 4

Pages: 434-447

ISSN: 0360-8352

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 7 Citations

ISI Web of Science

Scopus - 9 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-004-A7Q

DOI: 10.1016/j.cie.2007.02.001

Abstract (EN): In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, 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 each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed. The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14