| 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.