| Title:
|
A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures (English) |
| Author:
|
Haugen, Kjetil K. |
| Author:
|
Lanquepin-Chesnais, Guillaume |
| Author:
|
Olstad, Asmund |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
2 |
| Year:
|
2012 |
| Pages:
|
329-345 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
heuristics |
| Keyword:
|
capacitated lot-sizing |
| Keyword:
|
restricted cost structures |
| MSC:
|
65K05 |
| MSC:
|
68W99 |
| MSC:
|
90B30 |
| idMR:
|
MR2954330 |
| . |
| Date available:
|
2012-05-15T16:22:16Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142818 |
| . |
| Reference:
|
[1] G. Belvaux, L. A. Wolsey: LOTSIZELIB: A library of Models and Matrices for Lot-Sizing Problems..Internal Report, Universite Catholique de Louvain 1999. |
| Reference:
|
[2] G. R. Bitran, H. H. Yanasse: Computational complexity of the capacitated lot size problem..Management Sci. 28 (1982), 1174-1186. Zbl 0502.90046, MR 0688762, 10.1287/mnsc.28.10.1174 |
| Reference:
|
[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 2594622 |
| Reference:
|
[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. MR 1087815, 10.1007/BF02248584 |
| Reference:
|
[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. Zbl 0758.90020, 10.1287/mnsc.38.9.1329 |
| Reference:
|
[6] C. Gicquel, M. Minoux, Y. Dallery: Capacitated Lot Sizing Models: A Literature Review..Open Access Article hal-00255830, Hyper Articles en Ligne 2008. |
| Reference:
|
[7] F. W. Harris: How many parts to make at once..Factory, the Magazine of Management 10 (1913), 2, 135-136. |
| Reference:
|
[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. MR 1831860, 10.1016/S0377-2217(00)00116-8 |
| Reference:
|
[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 2676079 |
| Reference:
|
[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. Zbl 1137.90619, MR 2265141, 10.1016/j.ejor.2005.08.001 |
| Reference:
|
[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. Zbl 1143.90003, MR 2284077, 10.1007/s10852-006-9053-2 |
| Reference:
|
[12] T. Helgasson, S. W. Wallace: Approximate scenario solutions in the progressive hedging algorithm..Ann. Oper. Res. 31 (1991), 425-444. MR 1118910, 10.1007/BF02204861 |
| Reference:
|
[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. 10.1016/S0305-0483(03)00059-8 |
| Reference:
|
[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. 10.1016/0377-2217(94)90078-7 |
| Reference:
|
[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. 10.1016/0377-2217(91)90130-N |
| Reference:
|
[16] A. S. Manne: Programming of economic lot-sizes..Management Sci. 4 (1958), 2, 115-135. 10.1287/mnsc.4.2.115 |
| Reference:
|
[17] S. Nahmias: Production and Operations Analysis. Sixth edition..McGraw Hill, Boston 2009. |
| Reference:
|
[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. 10.1080/07408178508975308 |
| Reference:
|
[19] W. W. Trigeiro, L. J. Thomas, J. O. McClain: Capacitated lot sizing with setup times..Management Sci. 35 (1989), 3, 353-366. 10.1287/mnsc.35.3.353 |
| Reference:
|
[20] H. M. Wagner, T. M. Whitin: Dynamic version of the economic lot size model..Management Sci. 5 (1958), 3, 89-96. Zbl 0977.90500, MR 0102442, 10.1287/mnsc.5.1.89 |
| Reference:
|
[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. MR 1152747, 10.1287/opre.40.1.S145 |
| . |
