Article ID: | iaor2007676 |
Country: | Netherlands |
Volume: | 34 |
Issue: | 5 |
Start Page Number: | 591 |
End Page Number: | 598 |
Publication Date: | Sep 2006 |
Journal: | Operations Research Letters |
Authors: | Sourd Francis |
Keywords: | heuristics |
A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness–tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also present experimental results.