New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling

In one–machine scheduling, mixed–integer program time–indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. 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.