Heuristics for the early/tardy scheduling problem with release dates

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

Authors

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

Journal

Title: International Journal of Production Economics

Vol. 106

Pages: 261-274

ISSN: 0925-5273

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 16 Citations

Scopus - 20 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

Other information

Authenticus ID: P-004-BG8

DOI: 10.1016/j.ijpe.2006.06.006

Abstract (EN): In this paper, we consider the single machine earliness/tardiness scheduling problem with release dates and no unforced idle time. We analyse the performance of a varied set of heuristics. This set includes simple scheduling rules, early/tardy dispatching heuristics, a greedy procedure and a decision theory heuristic. Two different approaches are considered to calculate a lookahead parameter used in the early/tardy dispatching heuristics, and extensive experiments were performed to determine an appropriate value for this parameter. We also propose an improvement procedure that uses some dominance rules to improve the solution obtained by the heuristics. The computational results show that the use of the improvement step is recommended, since it reduces the objective function value with little additional computational effort. The best results were given by the decision theory heuristic, but this procedure is computationally expensive and therefore limited to small and medium size instances. For large instances, one of the early/tardy dispatching heuristics is then the heuristic of choice.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14