Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints
Francis Sourd (Francis.Sourdlip6.fr)
Abstract: The one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties is addressed. This problem is NP-complete, so that local search approaches are very useful to efficiently find good feasible schedules. In this paper, we present an extension of the dynasearch neighborhood for this problem. Finding the best schedule in this neighborhood is shown to be NP-complete in the ordinary sense. However, the neighborhood can be efficiently explored in pseudo-polynomial time. Computational tests are finally presented.
Keywords: Earliness-tardiness scheduling, dynasearch, local search.
Category 1: Applications -- OR and Management Sciences (Scheduling )
Citation: to appear in Operations Research Letters
Entry Submitted: 02/02/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|