Improved Heuristics for the Early/Tardy Scheduling Problem with No Idle Time
In this paper we consider the single machine earliness/tardiness scheduling problem with no idle time. We present two new heuristics, a dispatch rule and a greedy procedure, and also consider the best of the existing dispatch rules. Both dispatch rules use a lookahead parameter that had previously been set at a fixed value. We develop functions that map some instance statistics into appropriate values for that parameter. We also consider the use of dominance rules to improve the solutions obtained by the heuristics. The computational results show that the function-based versions of the heuristics outperform their fixed value counterparts and that the use of the dominance rules can indeed improve solution quality with little additional computational effort.
|Date of creation:||Apr 2003|
|Date of revision:|
|Contact details of provider:|| Postal: Rua Dr. Roberto Frias, 4200 PORTO|
Web page: http://www.fep.up.pt/
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "Improved Lower Bounds for the Early/Tardy Scheduling Problem with No Idle Time," FEP Working Papers 125, Universidade do Porto, Faculdade de Economia do Porto.
When requesting a correction, please mention this item's handle: RePEc:por:fepwps:126. See general information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.