Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates - Mines Saint-Étienne Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2010

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

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.

Dates et versions

emse-00551467 , version 1 (03-01-2011)

Identifiants

Citer

Boris Detienne, Eric Pinson, David Rivreau. Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates. European Journal of Operational Research, 2010, 201 (1), pp.45-54. ⟨10.1016/j.ejor.2009.02.005⟩. ⟨emse-00551467⟩
170 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More