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

Download:

Entry Submitted: 02/02/2004
Entry Accepted: 02/02/2004
Entry Last Modified: 11/02/2005

Modify/Update this entry