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
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2010, 201 (1), pp.45-54. 〈10.1016/j.ejor.2009.02.005〉
Liste complète des métadonnées
https://hal-emse.ccsd.cnrs.fr/emse-00551467
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : lundi 3 janvier 2011 - 17:54:59
Dernière modification le : lundi 26 novembre 2018 - 16:12:03

Lien texte intégral

openaccess

Identifiants

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

360

Contact

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