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

TitreLagrangian domain reductions for the single machine earliness–tardiness problem with release dates
Type de publicationArticle de revue
Année de publication2010
Titre de la revueEuropean Journal of Operational Research
Titre de la série/collection1
Volume201
Pagination 45 - 54
Date de publication2010
Langueeng
Auteur(s)Detienne, B., Pinson E. et Rivreau D.
Mots-clésElimination, exact, Just-in-time, Lagrangian, Scheduling
Résumé

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.