A new lower bound for one-machine earliness-tardiness scheduling
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
Entry Submitted: 06/22/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|