Efficient neighborhood search for Just-in-Time scheduling problems

Yann Hendel (Yann.Hendellip6.fr)
Francis Sourd (Francis.Sourdlip6.fr)

Abstract: This paper addresses the one-machine scheduling problem where the objective is to minimize a sum of costs such as earliness-tardiness costs. Since the sequencing problem is NP-hard, local search is very useful for finding good solutions. Unlike scheduling problems with regular cost functions, the scheduling (or timing) problem is not trivial when the sequence is fixed. Therefore, the local search approaches must deal with both job interchanges in the sequence and the timing of the sequenced jobs. We present a new approach that efficiently searches in a large neighborhood that always returns a solution for which the timing is optimal.

Keywords: Scheduling, Earliness-tardiness cost, neighborhoods

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: http://dx.doi.org/10.1016/j.ejor.2004.11.022 EJOR - In press

Download:

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

Modify/Update this entry