Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints

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.