Geodesic
A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures
Kybernetika, Tome 48 (2012) no. 2, pp. 329-345 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 65K05, 68W99, 90B30
Keywords: heuristics; capacitated lot-sizing; restricted cost structures 
@article{KYB_2012_48_2_a11,
     author = {Haugen, Kjetil K. and Lanquepin-Chesnais, Guillaume and Olstad, Asmund},
     title = {A fast {Lagrangian} heuristic for large-scale capacitated lot-size problems with restricted cost structures},
     journal = {Kybernetika},
     pages = {329--345},
     year = {2012},
     volume = {48},
     number = {2},
     mrnumber = {2954330},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a11/}
}
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
SP  - 329
EP  - 345
VL  - 48
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a11/
LA  - en
ID  - KYB_2012_48_2_a11
ER  - 
%0 Journal Article
%A Haugen, Kjetil K.
%A Lanquepin-Chesnais, Guillaume
%A Olstad, Asmund
%T A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures
%J Kybernetika
%D 2012
%P 329-345
%V 48
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a11/
%G en
%F KYB_2012_48_2_a11
Haugen, Kjetil K.; Lanquepin-Chesnais, Guillaume; Olstad, Asmund. A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures. Kybernetika, Tome 48 (2012) no. 2, pp. 329-345. http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a11/

[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: Computational complexity of the capacitated lot size problem. Management Sci. 28 (1982), 1174-1186. | DOI | MR | Zbl

[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. | MR

[4] W. H. Chen, J. M. Thizy: Analysis of relaxation for the multi-item capacitated lot-sizing problem. Ann. Oper. Res. 26 (1990), 29-72. | DOI | MR

[5] M. Diaby, H. C. Bahl, M. H. Karwan, S. Zionts: A Lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Management Sci. 38 (1992), 9, 1329-1340. | DOI | Zbl

[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: Progressive Hedging as a meta-heuristic applied to stochastic lot-sizing. European J. Oper. Res. 132 (2001), 116-122. | DOI | MR

[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. | MR

[10] K. K. Haugen, A. Olstad, B. I. Pettersen: The profit maximizing capacitated lot-size (PCLSP) problem. European J. Oper. Res. 176 (2007), 165-176. | DOI | MR | Zbl

[11] K. K. Haugen, A. Olstad, B. I. Pettersen: Solving large-scale profit maximization capacitated lot-size problems by heuristic methods. J. Math. Modelling Algorithms 6 (2007), 135-149. | DOI | MR | Zbl

[12] T. Helgasson, S. W. Wallace: Approximate scenario solutions in the progressive hedging algorithm. Ann. Oper. Res. 31 (1991), 425-444. | DOI | MR

[13] B. Karimi, S. M. T. Fatemi Ghomi, J. M. Wilson: The capacitated lot sizing problem: a review of models and algorithms. Omega 31 (2003), 365-378. | DOI

[14] O. Kirca, M. Kokten: A new heuristic approach for the multi-item lot sizing problem. European J. Oper. Res. 75 (1994), 2, 332-341. | DOI

[15] J. Maes, J. O. McClain, L. N. Van Wassenhove: Multilevel capacitated lot sizing complexity and LP-based heuristics. European J. Oper. Res. 53 (1991), 2, 131-148. | DOI

[16] A. S. Manne: Programming of economic lot-sizes. Management Sci. 4 (1958), 2, 115-135. | DOI

[17] S. Nahmias: Production and Operations Analysis. Sixth edition. McGraw Hill, Boston 2009.

[18] J. M. Thizy, L. N. Van Wassenhove: Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation. IEE Trans. 17 (1985), 4, 308-313. | DOI

[19] W. W. Trigeiro, L. J. Thomas, J. O. McClain: Capacitated lot sizing with setup times. Management Sci. 35 (1989), 3, 353-366. | DOI

[20] H. M. Wagner, T. M. Whitin: Dynamic version of the economic lot size model. Management Sci. 5 (1958), 3, 89-96. | DOI | MR | Zbl

[21] A. Wagelmans, S. Vanhoesel, 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. | DOI | MR