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

# Keywords:

heuristics, capacitated lot-sizing, restricted cost structures

# Classification:

65K05, 90B30, 68W99

# References:

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