Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates - Mines Saint-Étienne Access content directly
Journal Articles European Journal of Operational Research Year : 2010

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.

Dates and versions

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

Identifiers

Cite

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⟩
181 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More