Kybernetika 48 no. 2, 329-345, 2012

A fast Lagrangian heuristic for large-scale Capacitated Lot-size Problems with restricted cost structures

Kjetil K. Haugen, Guillaume Lanquepin-Chesnais and Asmund Olstad


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.


heuristics, capacitated lot-sizing, restricted cost structures


65K05, 90B30, 68W99


  1. G. Belvaux and L. A. Wolsey: LOTSIZELIB: A library of Models and Matrices for Lot-Sizing Problems. Internal Report, Universite Catholique de Louvain 1999.   CrossRef
  2. G. R. Bitran and H. H. Yanasse: Computational complexity of the capacitated lot size problem. Management Sci. 28 (1982), 1174-1186.   CrossRef
  3. L. Buschlkühl, F. Sahling, S. Helber and H. Tempelmeier: Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. OR Spectrum 132 (2008), 2, 231-261.   CrossRef
  4. W. H. Chen and J. M. Thizy: Analysis of relaxation for the multi-item capacitated lot-sizing problem. Ann. Oper. Res. 26 (1990), 29-72.   CrossRef
  5. M. Diaby, H. C. Bahl, M. H. Karwan and S. Zionts: A Lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Management Sci. 38 (1992), 9, 1329-1340.   CrossRef
  6. C. Gicquel, M. Minoux and Y. Dallery: Capacitated Lot Sizing Models: A Literature Review. Open Access Article hal-00255830, Hyper Articles en Ligne 2008.   CrossRef
  7. F. W. Harris: How many parts to make at once. Factory, the Magazine of Management 10 (1913), 2, 135-136.   CrossRef
  8. K. K. Haugen, A. Løkketangen and D. Woodruff: Progressive Hedging as a meta-heuristic applied to stochastic lot-sizing. European J. Oper. Res. 132 (2001), 116-122.   CrossRef
  9. K. K Haugen, A. Olstad, K. Bakhrankova and 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.   CrossRef
  10. K. K. Haugen, A. Olstad and B. I. Pettersen: The profit maximizing capacitated lot-size (PCLSP) problem. European J. Oper. Res. 176 (2007), 165-176.   CrossRef
  11. K. K. Haugen, A. Olstad and B. I. Pettersen: Solving large-scale profit maximization capacitated lot-size problems by heuristic methods. J. Math. Modelling Algorithms 6 (2007), 135-149.   CrossRef
  12. T. Helgasson and S. W. Wallace: Approximate scenario solutions in the progressive hedging algorithm. Ann. Oper. Res. 31 (1991), 425-444.   CrossRef
  13. B. Karimi, S. M. T. Fatemi Ghomi and J. M. Wilson: The capacitated lot sizing problem: a review of models and algorithms. Omega 31 (2003), 365-378.   CrossRef
  14. O. Kirca and M. Kokten: A new heuristic approach for the multi-item lot sizing problem. European J. Oper. Res. 75 (1994), 2, 332-341.   CrossRef
  15. J. Maes, J. O. McClain and L. N. Van Wassenhove: Multilevel capacitated lot sizing complexity and LP-based heuristics. European J. Oper. Res. 53 (1991), 2, 131-148.   CrossRef
  16. A. S. Manne: Programming of economic lot-sizes. Management Sci. 4 (1958), 2, 115-135.   CrossRef
  17. S. Nahmias: Production and Operations Analysis. Sixth edition. McGraw Hill, Boston 2009.   CrossRef
  18. J. M. Thizy and L. N. Van Wassenhove: Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation. IEE Trans. 17 (1985), 4, 308-313.   CrossRef
  19. W. W. Trigeiro, L. J. Thomas and J. O. McClain: Capacitated lot sizing with setup times. Management Sci. 35 (1989), 3, 353-366.   CrossRef
  20. H. M. Wagner and T. M. Whitin: Dynamic version of the economic lot size model. Management Sci. 5 (1958), 3, 89-96.   CrossRef
  21. A. Wagelmans, S. Vanhoesel and A. Kolen: Economic lot sizing - an $O(nłog n)$ algorithm that runs in linear time in the Wagner-Whitin case. Oper. Res. 40 (1992), 5145-5156.   CrossRef