Abstract
This paper presents a review of four decades of research on dynamic lot-sizing with capacity constraints. We discuss both different modeling approaches to the optimization problems and different algorithmic solution approaches. The focus is on research that separates the lot-sizing problem from the detailed sequencing and scheduling problem. Our conceptional point of reference is the multi-level capacitated lot-sizing problem (MLCLSP). We show how different streams of research emerged over time. One result is that many practically important problems are still far from being solved in the sense that they could routinely be solved close to optimality in industrial practice. Our review also shows that currently mathematical programing and the use of metaheuristics are particularly popular among researchers in a vivid and flourishing field of research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akartunalı K, Miller AJ (2008) A heuristic approach for big bucket multi-level production planning problems. Eur J Oper Res. doi:10.1016/j.ejor.2007.11.033
Alfieri A, Brandimarte P, D’Orazio S (2002) LP-based heuristics for the capacitated lot-sizing problem: the interaction of model formulation and solution algorithm. Int J Prod Res 40: 441–458
Armentano VA, França PM, de Toledo FMB (1999) A network flow model for the capacitated lot-sizing problem. Omega 27: 275–284
Bahl HC (1983) Column generation based heuristic algorithm for multi-item scheduling. IIE Trans 15: 136–141
Bahl HC, Ritzman LP, Gupta JND (1987) Determining lot sizes and resource requirements: a review. Oper Res 35: 329–345
Barany I, van Roy TJ, Wolsey LA (1984) Strong formulations for multi-item capacitated lot sizing. Manage Sci 30: 1255–1261
Barbarosoglu G, Özdamar L (2000) Analysis of solution space-dependent performance of simulated annealing: the case of the multi-level capacitated lot sizing problem. Comput Oper Res 27: 895–903
Belvaux G, Wolsey LA (2000) bc-prod: a specialized branch-and-cut system for lot-sizing problems. Manage Sci 46: 724–738
Belvaux G, Wolsey LA (2001) Modelling practical lot-sizing problems as mixed-integer programs. Manage Sci 47: 993–1007
Berretta R, Rodrigues LF (2004) A memetic algorithm for a multistage capacitated lot-sizing problem. Int J Prod Econ 87: 67–81
Berretta R, França PM, Armentano VA (2005) Metaheuristic approaches for the multilevel resource-constrained lot-sizing problem with setup and lead times. Asia Pac J Oper Res 22: 261–286
Billington PJ, McClain JO, Thomas LJ (1983) Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Manage Sci 29: 1126–1141
Billington PJ, McClain JO, Thomas LJ (1986) Heuristics for multilevel lot-sizing with a bottleneck. Manage Sci 32: 989–1006
Bitran GR, Matsuo H (1986) The multi-item capacitated lot size problem: error bounds of Manne’s formulations. Manage Sci 32: 350–359
Bitran GR, Yanasse HH (1982) Computational complexity of the capacitated lot size problem. Manage Sci 28: 1174–1186
Blackburn JD, Millen RA (1984) Simultaneous lot-sizing and capacity planning in multi-stage assembly processes. Eur J Oper Res 16: 84–93
Boctor FF, Poulin P (2005) Heuristics for N-product, M-stage, economic lot sizing and scheduling problem with dynamic demand. Int J Prod Res 43: 2809–2828
Bourjolly J-M, Ding K, Gopalakrishnan M, Gramani MCN, Mohan S (2001) On a tactical/operational production planning problem in supply chain management: balancing inventory and setup costs. In: MIC’2001—4th metaheuristics international conference, pp 569–571
Brahimi N, Dauzère-Pérès S, Najid NM (2006a) Capacitated multi-item lot-sizing problems with time windows. Oper Res 54: 951–967
Brahimi N, Dauzère-Pérès S, Najid NM, Nordli A (2006b) Single item lot sizing problems. Eur J Oper Res 168: 1–16
Campbell GM, Mabert VA (1991) Cyclical schedules for capacitated lot sizing with dynamic demands. Manage Sci 37: 409–427
Cattrysse D, Maes J, van Wassenhove LN (1990) Set partitioning and column generation heuristics for capacitated dynamic lotsizing. Eur J Oper Res 46: 38–47
Chen H, Chu C (2003) A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints. J Syst Sci Syst Eng 12: 98–110
Chen W-H, Thizy J-M (1990) Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann Oper Res 26: 29–72
Clark AR, Armentano VA (1995) A heuristic for a resource-capacitated multi-stage lot-sizing problem with lead times. J Oper Res Soc 46: 1208–1222
Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8: 101–111
Degraeve Z, Jans R (2003) A new Dantzig–Wolfe reformulation and branch-and-price algorithm for the capacitated lot sizing problem with set up times. (April 2003, 03). In: ERIM report series reference no. ERS-2003-010-LIS. Available at SSRN: http://ssrn.com/abstract=411647
DeMatteis JJ (1968) An economic lot-sizing technique i—the part-period algorithm. IBM Syst J 7: 30–38
Denizel M, Altekin FT, Süral H, Stadtler H (2008) Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times. OR Spectr 30: 773–785
Diaby M, Bahl HC, Karwan MH, Zionts S (1992a) Capacitated lot-sizing and scheduling by Lagrangean relaxation. Eur J Oper Res 59: 444–458
Diaby M, Bahl HC, Karwan MH, Zionts S (1992b) A lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Manage Sci 38: 1329–1340
Dillenberger C, Escudero LF, Wollensak A, Zhang W (1993) On solving a large-scale resource allocation problem in production planning. In: Fandel G, Gulledge T, Jones A (eds) Operations research in production planning and control. Springer, Heidelberg, pp 105–119
Dillenberger C, Escudero LF, Wollensak A, Zhang W (1994) On practical resource allocation for production planning and scheduling with period overlapping setups. Eur J Oper Res 75: 275–286
Dixon PS, Silver EA (1981) A heuristic solution procedure for the multi-item, single-level, limited capacity, lot-sizing problem. J Oper Manage 2: 23–39
Dogramaci A, Panayiotopoulos JC, Adam NR (1981) The dynamic lot-sizing problem for multiple items under limited capacity. AIIE Trans 13: 294–303
Drexl A, Haase K (1995) Proportional lotsizing and scheduling. Int J Prod Econ 40: 73–87
Drexl A, Kimms A (1997) Lot sizing and scheduling: survey and extensions. Eur J Oper Res 99: 221–235
Dzielinski BP, Gomory RE (1965) Optimal programming of lot sizes, inventory and labor allocations. Manage Sci 11: 874–890
Eisenhut PS (1975) A dynamic lot sizing algorithm with capacity constraints. AIIE Trans 7: 170–176
Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper Res 35: 832–848
Evans JR (1985) An efficient implementation of the Wagner-Whitin algorithm for dynamic lot-sizing. J Oper Manage 5: 229–235
Federgruen A, Tzur M (1991) A simple forward algorithm to solve general dynamic lot sizing models with n periods in o(n log n) or o(n) time. Manage Sci 37: 909–925
Federgruen A, Meissner J, Tzur M (2007) Progressive interval heuristics for multi-item capacitated lot-sizing problems. Oper Res 55: 490–502
Fleischmann B (1990) The discrete lot-sizing and scheduling problem. Eur J Oper Res 44: 337–348
Fleischmann B, Meyr H (1997) The general lotsizing and scheduling problem. OR Spektrum 19: 11–21
Florian M, Lenstra J, Kan AR (1980) Deterministic production planning: algorithms and complexity. Manage Sci 26: 669–679
França PM, Armentano VA, Berretta RE, Clark AR (1997) A heuristic method for lot-sizing in multi-stage systems. Comput Oper Res 24: 861–874
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York
Gelders LF, Maes J, van Wassenhove LN (1986) A branch and bound algorithm for the multi item single level capacitated dynamic lotsizing problem. In: Axsäter S, Schneeweiss C, Silver E (eds) Multi-stage production planning and inventory control. Springer, Berlin, pp 92–108
Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13: 533–549
Gopalakrishnan M, Ding K, Bourjolly J-M, Mohan S (2001) A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Manage Sci 47: 851–863
Groff G (1979) A lot sizing rule for time-phased component demand. Prod Inventory Manage 20: 47–53
Günther H-O (1987) Planning lot sizes and capacity requirements in a single stage production sytem. Eur J Oper Res 31: 223–231
Gupta YP, Keung Y (1990) A review of multi-stage lot-sizing models. Int J Oper Prod Manage 10: 57–73
Gupta D, Magnusson T (2005) The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Comput Oper Res 32: 727–747
Gutierrez E, Hernández W, Süer GA (2001) Genetic algorithms in capacitated lot sizing decisions. In: Computer research conference
Haase K (1994) Lotsizing and scheduling for production planning. Lecture notes in economics and mathematical systems, vol 408. Springer, Berlin
Haase K (1998) Capacitated lot-sizing with linked production quantities of adjacent periods. In: Drexl A, Kimms A (eds) Beyond manufacturing resource planning (MRP II)—advanced models and methods for production planning. Springer, Berlin, pp 127–146
Haase K (2005) Solving large-scale capacitated lot-sizing problems close to optimality. Working paper, Technische Universität Dresden
Haase K, Kohlmorgen U (1995) Parallel genetic algorithm for the capacitated lot-sizing problem. In: Kleinschmidt P, Bachem A, Derigs U, Fischer D, Leopold-Wildburger U, Möhring R (eds) Operations research proceedings. Springer, Berlin, pp 370–375
Hansen P, Mlaydenović N (1999) An introduction to variable neighborhood search. In: Voß S, Martello S, Osman I, Roucairol C (eds) Metaheuristics: advances and trends in local search paradigms for optimization. Kluwer, Dordrecht, pp 433–458
Hansen P, Mlaydenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130: 449–467
Harrison TP, Lewis HS (1996) Lot sizing in serial assembly systems with multiple constrained resources. Manage Sci 42: 19–36
Helber S (1994) Kapazitätsorientierte Losgröß enplanung in PPS-Sytemen. M&P
Helber S (1995) Lot sizing in capacitated production planning and control systems. OR Spektrum 17: 5–18
Hindi KS (1995) Computationally efficient solution of the multi-item, capacitated lot-sizing problem. Comput Ind Eng 28: 709–719
Hindi KS (1996) Solving the CLSP by a tabu search heuristic. J Oper Res Soc 47: 151–161
Hindi KS, Fleszar K, Charalambous C (2003) An effective heuristic for the CLSP with set-up times. J Oper Res Soc 54: 490–498
Huisman D, Jans R, Peeters M, Wagelmans APM (2003) Combining column generation and Lagrangian relaxation (1 January 2003). In: ERIM report series reference no. ERS-2003-092-LIS. Available at SSRN: http://ssrn.com/abstract=496704
Hung Y-F, Chien KL (2000) A multi-class multi-level capacitated lot sizing model. J Oper Res Soc 51: 1309–1318
Hung Y-F, Hu Y-C (1998) Solving mixed integer programming production planning problems with setups by shadow price information. Comput Oper Res 25: 1027–1042
Hung Y-F, Shih C-C, Chen C-P (1999) Evolutionary algorithms for production planning problems with setup decisions. J Oper Res Soc 50: 857–866
Hung Y-F, Chen C-P, Shih C-C, Hung M-H (2003) Using tabu search with ranking candidate list to solve production planning problems with setups. Comput Ind Eng 45: 615–634
Jacobs F, Khumawala B (1982) Multi-level lot sizing in material requirements planning: an empirical investigation. Comput Oper Res 9: 139–144
Jans R, Degraeve Z (2007) Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches. Eur J Oper Res 177: 1855–1875
Karimi B, Ghomi SMTF, Wilson JM (2003) The capacitated lot sizing problem: a review of models and algorithms. Omega 31: 365–378
Karmarkar US, Schrage L (1985) The deterministic dynamic product cycling problem. Oper Res 66: 326–345
Karni R, Roll Y (1982) A heuristic algorithm for the multi-item lot sizing problem with capacity constraints. IIE Trans 14: 249–256
Katok E, Lewis HS, Harrison TP (1998) Lot sizing in general assembly systems with setup costs, setup times, and multiple constrained resources. Manage Sci 44: 859–877
Kirca Ö (1990) An efficient algorithm for the capacitated single dynamic lot size problem. Eur J Oper Res 45: 15–24
Kirca Ö, Kökten M (1994) A new heuristic approach for the multi-item dynamic lot sizing problem. Eur J Oper Res 75: 332–341
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220: 671–680
Kohlmorgen U, Schmeck H, Haase K (1999) Experiences with fine-grained parallel genetic algorithms. Ann Oper Res 90: 203–219
Krarup J, Bilde O (1977) Plant location, set covering and economic lot size: An o(mn)-algorithm for structured problems. In: Collatz L, Meinardus G, Wetterling W (eds) Numerische Methoden bei Optimierungsaufgaben Band 3. Birkhäuser, Basel, pp 155–180
Kuik R, Salomon M (1990) Multi-level lot-sizing problem: evaluation of a simulated-annealing heuristic. Eur J Oper Res 45: 25–37
Kuik R, Salomon M, van Wassenhove LN, Maes J (1993) Linear programming, simulated annealing and tabu search heuristics for lotsizing in bottleneck assembly systems. IIE Trans 25: 62–72
Kuik R, Salomon M, van Wassenhove LN (1994) Batching decisions: structure and models. Eur J Oper Res 75: 243–263
Lambrecht MR, Vanderveken H (1979) Heuristic procedures for the single operation, multi-item loading problem. AIIE Trans 11: 319–326
Lasdon LS, Terjung RC (1971) An efficient algorithm for multi-item scheduling. Oper Res 19: 946–969
Maes J, van Wassenhove LN (1986a) Multi item single level capacitated dynamic lotsizing heuristics: a computational comparison (part I: static case). IIE Trans 18: 114–123
Maes J, van Wassenhove LN (1986b) Multi item single level capacitated dynamic lotsizing heuristics: a computational comparison (part II: rolling horizon). IIE Trans 18: 124–129
Maes J, van Wassenhove LN (1986c) A simple heuristic for the multi item single level capacitated lotsizing problem. Oper Res Lett 4: 265–273
Maes J, van Wassenhove L (1988) Multi-item single-level capacitated dynamic lot-sizing heuristics: a general review. J Oper Res Soc 39: 991–1004
Maes J, McClain JO, van Wassenhove LN (1991) Multilevel capacitated lotsizing complexity and LP-based heuristics. Eur J Oper Res 53: 131–148
Manne AS (1958) Programming of economic lot sizes. Manage Sci 4: 115–135
Mercé C, Fontan G (2003) MIP-based heuristics for capacitated lotsizing problems. Int J Prod Econ 85: 97–111
Millar HH, Yang M (1994) Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering. Int J Prod Econ 34: 1–15
Miller AJ, Nemhauser GL, Savelsbergh MWP (2000) Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut. Université Catholique de Louvain, Belgium. Core discussion paper 00/39
Moorkanat J (2000) Studies in certain resource loading, scheduling and production control problems in multi-stage production control problems in multi-stage production inventory systems. Ph.D. thesis, Indian Institute of Technology, Bombay
Newson EFP (1975a) Multi-item lot size scheduling by heuristic, part I: with fixed resources. Manage Sci 21: 1186–1193
Newson EFP (1975b) Multi-item lot size scheduling by heuristic, part II: with variable resources. Manage Sci 21: 1194–1203
Özdamar L, Barbarosoglu G (1999) Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem. J Oper Res Soc 50: 810–825
Özdamar L, Barbarosoglu G (2000) An integrated Lagrangean relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem. Int J Prod Econ 68: 319–331
Özdamar L, Bozyel MA (2000) The capacitated lot sizing problem with overtime decisions and setup times. IIE Trans 32: 1043–1057
Özdamar L, Birbil ŞI, Portmann M-C (2002) Technical note: new results for the capacitated lot sizing problem with overtime decisions and setup times. Prod Plann Control 13: 2–10
Pitakaso R, Almeder C, Doerner KF, Hartl RF (2006) Combining exact and population-based methods for the constrained multilevel lot sizing problem. Int J Prod Res 44: 4755–4771
Pochet Y, Wolsey LA (1991) Solving multi-item lot-sizing problems using strong cutting planes. Manage Sci 37: 53–67
Quadt D, Kuhn H (2008) Capacitated lot-sizing with extensions: a review. 4OR Q J Oper Res 6: 61–83
Rogers J (1958) A computational approach to the economic lot scheduling problem. Manage Sci 4: 264–291
Rosling K (1986) Optimal lot-sizing for dynamic assembly systems. In: Axsäter S, Schneeweiss C, Silver E (eds) Multi-stage production planning and inventory control. Springer, Berlin, pp 119–131
Salomon M (1991) Deterministic lotsizing models for production planning. Lecture notes in economics and mathematical systems, vol 355. Springer, Berlin
Salomon M, Kroon LG, Kuik R, van Wassenhove LN (1991) Some extensions of the discrete lotsizing and scheduling problem. Manage Sci 37: 801–812
Salomon M, Kuik R, van Wassenhove LN (1993) Statistical search methods for lotsizing problems. Ann Oper Res 41: 453–468
Sambasivan M, Yahya S (2005) A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers. Comput Oper Res 32: 537–555
Sambasivan M, Schmidt CP (2002) A heuristic procedure for solving multi-plant, multi-item, multi-period capacitated lot-sizing problems. Asia Pac J Oper Res 19: 87–105
Selen WJ, Heuts RM (1989) A modified priority index for Günther’s lot-sizing heuristic under capacitated single stage production. Eur J Oper Res 41: 181–185
Silver EA, Meal HC (1969) A simple modification of the EOQ for the case of a varying demand rate. Prod Inventory Manage 10: 51–55
Silver EA, Meal HC (1973) A heuristic for selecting lot size quantities for the case of a deterministic time-varying demand rate and discrete opportunities for replenishment. Prod Inventory Manage 14: 64–74
Sox CR, Gao Y (1999) The capacitated lot sizing problem with setup carry-over. IIE Trans 31: 173–181
Stadtler H (1996) Mixed integer programming model formulations for dynamic multi-item multi-level capacitated lotsizing. Eur J Oper Res 94: 561–581
Stadtler H (1997) Reformulations of the shortest route model for dynamic multi-item multi-level capacitated lotsizing. OR Spektrum 19: 87–96
Stadtler H (2000) Improved rolling schedules for the dynamic single-level lot-sizing problem. Manage Sci 46: 318–326
Stadtler H (2003) Multilevel lot sizing with setup times and multiple constrained resources: internally rolling schedules with lot-sizing windows. Oper Res 51: 487–502
Staggemeier AT, Clark AR (2001) A survey of lot-sizing and scheduling models. In: 23rd annual symposium of the Brazilian Operational Research Society (SOBRAPO), Campos do Jordao SP, Brazil, pp 938–947
Sürie C, Stadtler H (2003) The capacitated lot-sizing problem with linked lot sizes. Manage Sci 49: 1039–1054
Tempelmeier H, Derstroff M (1993) Mehrstufige Mehrprodukt-Losgröß enplanung bei beschränkten Ressourcen und genereller Erzeugnisstruktur. OR Spektrum 15: 63–73
Tempelmeier H, Derstroff M (1996) A Lagrangean-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Manage Sci 42: 738–757
Tempelmeier H, Helber S (1994) A heuristic for dynamic multi-item multi-level capacitated lotsizing for general product structures. Eur J Oper Res 75: 296–311
Thizy J-M, van Wassenhove LN (1985) Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation. IIE Trans 17: 308–313
Trigeiro WW (1987) A dual-cost heuristic for the capacitated lot sizing problem. IIE Trans 19: 67–72
Trigeiro WW (1989) A simple heuristic for lot sizing with setup times. Decis Sci 20: 294–303
Trigeiro WW, Thomas LJ, McClain JO (1989) Capacitated lot sizing with setup times. Manage Sci 35: 353–366
van Nunen JAEE, Wessels J (1978) Multi-item lot size determination and scheduling under capacity constraints. Eur J Oper Res 2: 36–41
Wagelmans A, van Hoesel S, Kolen A (1992) Economic lot sizing: An o (n log n) algorithm that runs in linear time in the Wagner–Whitin case. Oper Res 40: 145–156
Wagner HM, Whitin TM (1958) Dynamic version of the economic lot size model. Manage Sci 5: 89–96
Wolsey LA (1995) Progress with single-item lot-sizing. Eur J Oper Res 86: 395–401
Xie J, Dong J (2002) Heuristic genetic algorithms for general capacitated lot-sizing problems. Comput Math Appl 44: 263–276
Zangwill WI (1966) A deterministic multi-period production scheduling model with backlogging. Manage Sci 13: 105–119
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Buschkühl, L., Sahling, F., Helber, S. et al. Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. OR Spectrum 32, 231–261 (2010). https://doi.org/10.1007/s00291-008-0150-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-008-0150-7