Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times

Abstract : In this paper, we solve the capacitated multi item lot-sizing problem with non-customer specific production time windows and setup times using two approaches: (i) using a Lagrangian relaxation-based heuristic and (ii) using reformulations and a commercial software. The results of the two approaches are analyzed and compared based on randomly generated data sets. The results show that the first approach finds feasible solution more rapidly but a steady state is reached very quickly. On the other hand the second approach quickly finds good lower bounds and finds good feasible solutions if more CPU time is allowed. It turns out that, for a wide variety of instances varying in size and other parameters, we can obtain feasible solutions within 1–5% of optimal within 10 s and also obtain solutions that are guaranteed within 1–2% of optimal within 60–120 s.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2010, 37 (1), pp.182-188. 〈10.1016/j.cor.2009.04.005〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00519241
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : dimanche 19 septembre 2010 - 12:34:24
Dernière modification le : lundi 3 décembre 2018 - 15:46:26

Identifiants

Collections

Citation

Nadjib Brahimi, Stéphane Dauzère-Pérès, Laurence A. Wolsey. Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times. Computers and Operations Research, Elsevier, 2010, 37 (1), pp.182-188. 〈10.1016/j.cor.2009.04.005〉. 〈emse-00519241〉

Partager

Métriques

Consultations de la notice

118