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

Kjetil K. Haugen; Guillaume Lanquepin-Chesnais; Asmund Olstad

Kybernetika (2012)

  • Volume: 48, Issue: 2, page 329-345
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

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 -

References

top
  1. G. Belvaux, L. A. Wolsey, LOTSIZELIB: A library of Models and Matrices for Lot-Sizing Problems., Internal Report, Universite Catholique de Louvain 1999. 
  2. G. R. Bitran, H. H. Yanasse, 10.1287/mnsc.28.10.1174, Management Sci. 28 (1982), 1174-1186. Zbl0502.90046MR0688762DOI10.1287/mnsc.28.10.1174
  3. L. Buschlkühl, F. Sahling, S. Helber, H. Tempelmeier, Dynamic capacitated lot-sizing problems: a classification and review of solution approaches., OR Spectrum 132 (2008), 2, 231-261. MR2594622
  4. W. H. Chen, J. M. Thizy, 10.1007/BF02248584, Ann. Oper. Res. 26 (1990), 29-72. MR1087815DOI10.1007/BF02248584
  5. M. Diaby, H. C. Bahl, M. H. Karwan, S. Zionts, 10.1287/mnsc.38.9.1329, Management Sci. 38 (1992), 9, 1329-1340. Zbl0758.90020DOI10.1287/mnsc.38.9.1329
  6. C. Gicquel, M. Minoux, Y. Dallery, Capacitated Lot Sizing Models: A Literature Review., Open Access Article hal-00255830, Hyper Articles en Ligne 2008. 
  7. F. W. Harris, How many parts to make at once., Factory, the Magazine of Management 10 (1913), 2, 135-136. 
  8. K. K. Haugen, A. Løkketangen, D. Woodruff, 10.1016/S0377-2217(00)00116-8, European J. Oper. Res. 132 (2001), 116-122. MR1831860DOI10.1016/S0377-2217(00)00116-8
  9. K. K Haugen, A. Olstad, K. Bakhrankova, E. Van Eikenhorst, The single (and multi) item profit maximizing capacitated lot-size problem with fixed prices and no set-up., Kybernetika 47 (2010), 3, 415-422. MR2676079
  10. K. K. Haugen, A. Olstad, B. I. Pettersen, 10.1016/j.ejor.2005.08.001, European J. Oper. Res. 176 (2007), 165-176. Zbl1137.90619MR2265141DOI10.1016/j.ejor.2005.08.001
  11. K. K. Haugen, A. Olstad, B. I. Pettersen, 10.1007/s10852-006-9053-2, J. Math. Modelling Algorithms 6 (2007), 135-149. Zbl1143.90003MR2284077DOI10.1007/s10852-006-9053-2
  12. T. Helgasson, S. W. Wallace, 10.1007/BF02204861, Ann. Oper. Res. 31 (1991), 425-444. MR1118910DOI10.1007/BF02204861
  13. B. Karimi, S. M. T. Fatemi Ghomi, J. M. Wilson, 10.1016/S0305-0483(03)00059-8, Omega 31 (2003), 365-378. DOI10.1016/S0305-0483(03)00059-8
  14. O. Kirca, M. Kokten, 10.1016/0377-2217(94)90078-7, European J. Oper. Res. 75 (1994), 2, 332-341. DOI10.1016/0377-2217(94)90078-7
  15. J. Maes, J. O. McClain, L. N. Van Wassenhove, 10.1016/0377-2217(91)90130-N, European J. Oper. Res. 53 (1991), 2, 131-148. DOI10.1016/0377-2217(91)90130-N
  16. A. S. Manne, 10.1287/mnsc.4.2.115, Management Sci. 4 (1958), 2, 115-135. DOI10.1287/mnsc.4.2.115
  17. S. Nahmias, Production and Operations Analysis. Sixth edition., McGraw Hill, Boston 2009. 
  18. J. M. Thizy, L. N. Van Wassenhove, 10.1080/07408178508975308, IEE Trans. 17 (1985), 4, 308-313. DOI10.1080/07408178508975308
  19. W. W. Trigeiro, L. J. Thomas, J. O. McClain, 10.1287/mnsc.35.3.353, Management Sci. 35 (1989), 3, 353-366. DOI10.1287/mnsc.35.3.353
  20. H. M. Wagner, T. M. Whitin, 10.1287/mnsc.5.1.89, Management Sci. 5 (1958), 3, 89-96. Zbl0977.90500MR0102442DOI10.1287/mnsc.5.1.89
  21. A. Wagelmans, S. Vanhoesel, A. Kolen, 10.1287/opre.40.1.S145, Oper. Res. 40 (1992), 5145-5156. MR1152747DOI10.1287/opre.40.1.S145

NotesEmbed ?

top

You must be logged in to post comments.