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

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

0.00 Avg rating0 Votes
Article ID: iaor20082407
Country: Netherlands
Volume: 52
Issue: 4
Start Page Number: 434
End Page Number: 447
Publication Date: May 2007
Journal: Computers & Industrial Engineering
Authors:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.