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

Boris Detienne 1 Eric Pinson 2, 3 David Rivreau 2, 3
1 SFL-ENSMSE - Département Sciences de la Fabrication et Logistique
2 LISA - Laboratoire d'Ingéniérie des Systèmes Automatisés
3 IMA - Institut de Mathématiques Appliquées
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.
Keywords : Scheduling Just-in-time Elimination rules Lagrangian relaxation Exact method
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

Collections

UNIV-ANGERS | EMSE | CMP-ENSMSE | SFL-ENSMSE | UNAM | LISA-ANGERS | INSTITUT-TELECOM

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

397

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD