A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures

Haugen, Kjetil K., Lanquepin-Chesnais, Guillaume, and Olstad, Asmund. "A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures." Kybernetika 48.2 (2012): 329-345. <http://eudml.org/doc/246843>.

@article{Haugen2012,
abstract = {In this paper, we demonstrate the computational consequences of making a simple assumption on production cost structures in capacitated lot-size problems. Our results indicate that our cost assumption of increased productivity over time has dramatic effects on the problem sizes which are solvable. Our experiments indicate that problems with more than 1000 products in more than 1000 time periods may be solved within reasonable time. The Lagrangian decomposition algorithm we use does of course not guarantee optimality, but our results indicate surprisingly narrow gaps for such large-scale cases - in most cases significantly outperforming CPLEX. We also demonstrate that general CLSP's can benefit greatly from applying our proposed heuristic.},
author = {Haugen, Kjetil K., Lanquepin-Chesnais, Guillaume, Olstad, Asmund},
journal = {Kybernetika},
keywords = {heuristics; capacitated lot-sizing; restricted cost structures; heuristics; capacitated lot-sizing; restricted cost structures},
language = {eng},
number = {2},
pages = {329-345},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures},
url = {http://eudml.org/doc/246843},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Haugen, Kjetil K.
AU - Lanquepin-Chesnais, Guillaume
AU - Olstad, Asmund
TI - A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 2
SP - 329
EP - 345
AB - In this paper, we demonstrate the computational consequences of making a simple assumption on production cost structures in capacitated lot-size problems. Our results indicate that our cost assumption of increased productivity over time has dramatic effects on the problem sizes which are solvable. Our experiments indicate that problems with more than 1000 products in more than 1000 time periods may be solved within reasonable time. The Lagrangian decomposition algorithm we use does of course not guarantee optimality, but our results indicate surprisingly narrow gaps for such large-scale cases - in most cases significantly outperforming CPLEX. We also demonstrate that general CLSP's can benefit greatly from applying our proposed heuristic.
LA - eng
KW - heuristics; capacitated lot-sizing; restricted cost structures; heuristics; capacitated lot-sizing; restricted cost structures
UR - http://eudml.org/doc/246843
ER -