Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates

Abstract : This paper presents new elimination rules for the single machine problem with general earliness and tardiness penalties subject to release dates. These rules, based on a Lagrangian decomposition, allow to drastically reduce the execution windows of the jobs. We measure the efficiency of these properties by integrating them in a branch-and-bound. Tests show that instances with up to 70 jobs without release dates, and up to 40 jobs with release dates, can be optimally solved within 1000 seconds.
Document type :
Journal articles
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00551467
Contributor : Stéphane Dauzère-Pérès <>
Submitted on : Monday, January 3, 2011 - 5:54:59 PM
Last modification on : Thursday, October 17, 2019 - 12:36:32 PM

Identifiers

Citation

Boris Detienne, Eric Pinson, David Rivreau. Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates. European Journal of Operational Research, Elsevier, 2010, 201 (1), pp.45-54. ⟨10.1016/j.ejor.2009.02.005⟩. ⟨emse-00551467⟩

Share

Metrics

Record views

397