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.
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 5 février 2018 - 15:00:04

Lien texte intégral

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

307