A new lower bound for one-machine earliness-tardiness scheduling

Francis Sourd(francis.sourdlip6.fr)

Abstract: In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound algorithms are then presented for the earliness-tardiness scheduling problem with either common or general due dates. In both cases, our algorithms outperform the previously published approaches.

Keywords: Time-indexed formulation, Lagrangian relaxation, earliness-tardiness scheduling, common due date, general due dates.

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

Citation: LIP6 working paper

Download: [Postscript][PDF]

Entry Submitted: 06/22/2007
Entry Accepted: 06/22/2007
Entry Last Modified: 06/22/2007

Modify/Update this entry