Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
heuristics; capacitated lot-sizing; restricted cost structures
heuristics; capacitated lot-sizing; restricted cost structures
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.
References:
[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 10.1287/mnsc.28.10.1174 | MR 0688762 | Zbl 0502.90046
[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
[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 10.1007/BF02248584 | MR 1087815
[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 10.1287/mnsc.38.9.1329 | Zbl 0758.90020
[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 10.1016/S0377-2217(00)00116-8 | MR 1831860
[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
[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 10.1016/j.ejor.2005.08.001 | MR 2265141 | Zbl 1137.90619
[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 10.1007/s10852-006-9053-2 | MR 2284077 | Zbl 1143.90003
[12] T. Helgasson, S. W. Wallace: Approximate scenario solutions in the progressive hedging algorithm. Ann. Oper. Res. 31 (1991), 425-444. DOI 10.1007/BF02204861 | MR 1118910
[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 10.1016/S0305-0483(03)00059-8
[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 10.1016/0377-2217(94)90078-7
[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 10.1016/0377-2217(91)90130-N
[16] A. S. Manne: Programming of economic lot-sizes. Management Sci. 4 (1958), 2, 115-135. DOI 10.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: Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation. IEE Trans. 17 (1985), 4, 308-313. DOI 10.1080/07408178508975308
[19] W. W. Trigeiro, L. J. Thomas, J. O. McClain: Capacitated lot sizing with setup times. Management Sci. 35 (1989), 3, 353-366. DOI 10.1287/mnsc.35.3.353
[20] H. M. Wagner, T. M. Whitin: Dynamic version of the economic lot size model. Management Sci. 5 (1958), 3, 89-96. DOI 10.1287/mnsc.5.1.89 | MR 0102442 | Zbl 0977.90500
[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 10.1287/opre.40.1.S145 | MR 1152747
Search
Partner of
