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

Boris Detienne; Eric Pinson; David Rivreau

doi:10.1016/j.ejor.2009.02.005

Journal articles

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

Boris Detienne ¹ 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 MAI - Mathématiques Appliquées et Informatique

UCO - Université Catholique de l'Ouest

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

Domain :

Computer Science [cs] / Operations Research [cs.RO]

Complete list of metadata

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 : Friday, May 21, 2021 - 12:04:01 AM

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

Identifiers

Collections

Citation

Export

Metrics

540

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

Identifiers

Collections

Citation

Export

Share

Metrics

540