Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
478740 | European Journal of Operational Research | 2010 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Boris Detienne, Éric Pinson, David Rivreau,