Abstract
The capacitated lot-sizing problem (CLSP) is a standard formulation for big bucket lot-sizing problems with a discrete period segmentation and deterministic demands. We present a literature review on problems that incorporate one of the following extensions in the CLSP: back-orders, setup carry-over, sequencing, and parallel machines. We illustrate model formulations for each of the extensions and also mention the inclusion of setup times, multi-level product structures and overtime in a study. For practitioners, this overview allows to check the availability of successful solution procedures for a specific problem. For scientists, it identifies areas that are open for future research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aras OA and Swanson LA (1982). A lot sizing and sequencing algorithm for dynamic demands upon a single facility. J Oper Manage 2(3): 177–185
Bahl HC, Ritzman LP and Gupta JND (1987). Determining lot sizes and resource requirements: a review. Oper Res 35(3): 329–345
Baker T, Muckstadt J Jr (1989) The CHES problems. Working paper, Chesapeake Decision Sciences, Inc., NJ
Belvaux G and Wolsey LA (2000). bc – prod: a specialized branch-and-cut system for lot-sizing problems. Manage Sci 46(5): 724–738
Billington PJ, McClain JO and Thomas LJ (1983). Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Manage Sci 29(10): 1126–1141
Bitran GR and Yanasse HH (1982). Computational complexity of the capacitated lot size problem. Manage Sci 28(10): 1174–1186
Cheng CH, Madan MS, Gupta Y and So S (2001). Solving the capacitated lot-sizing problem with backorder consideration. J Oper Res Soc 52: 952–959
Cooke DL and Rohleder TR (2006). Inventory evaluation and product slate management in large-scale continuous process industries. J Oper Manage 24(3): 235–249
Derstroff MC (1995). Mehrstufige Losgrößenplanung mit Kapazitätsbeschränkungen. Physica, Heidelberg
Diaby M, Bahl HC, Karwan MH and Zionts S (1992). A lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Manage Sci 38(9): 1329–1340
Dillenberger C, Escudero LF, Wollensak A and Zhang W (1993). On solving a large-scale resource allocation problem in production planning. In: Fandel, G, Gulledge, T, and Jones, A (eds) Operations research in production planning and control, pp 105–119. Springer, Berlin
Dillenberger C, Escudero LF, Wollensak A and Zhang W (1994). On practical resource allocation for production planning and scheduling with period overlapping setups. Eur J Oper Res 75(2): 275–286
Drexl A and Kimms A (1997). Lot sizing and scheduling—survey and extensions. Eur J Oper Res 99: 221–235
Eppen GD and Martin RK (1987). Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper Res 35(6): 832–848
Erickson R, Monma C and Veinott A (1987). Send-and-split methods for minimum-concave-cost network flows. Math Oper Res 12: 634–664
Fleischmann B and Meyr H (1997). The general lotsizing and scheduling problem. OR Spektrum 19: 11–21
Gao Y (2000). A heuristic procedure for the capacitated lot sizing problem with set-up carry-over. Control Theory Appl 17(6): 937–940
Gopalakrishnan M (2000). A modified framework for modelling set-up carryover in the capacitated lotsizing problem. Int J Prod Res 38(14): 3421–3424
Gopalakrishnan M, Miller D and Schmidt C (1995). A framework for modelling setup carryover in the capacitated lot sizing problem. Int J Prod Res 33: 1973–1988
Gopalakrishnan M, Ding K, Bourjolly JM and Mohan S (2001). A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Manage Sci 47(6): 851–863
Grünert T (1998). Multi-level sequence-dependent dynamic lotsizing and scheduling. Shaker, Aachen
Haase K (1994). Lotsizing and scheduling for production planning. Springer, Berlin
Haase K (1996). Capacitated lot-sizing with sequence dependent setup costs. OR Spektrum 18: 51–59
Haase K (1998). Capacitated lot-sizing with linked production quantities of adjacent periods. In: Drexl, A and Kimms, A (eds) Beyond manufacturing resource planning (MRP II)—advanced models and methods for production planning, pp 127–146. Springer, Berlin
Haase K and Kimms A (2000). Lot sizing and scheduling with sequence dependent setup costs and times and efficient rescheduling opportunities. Int J Prod Econ 66: 159–169
Helber S (1994). Kapazitätsorientierte Losgrößenplanung in PPS-Systemen. M&P Verlag für Wissenschaft und Forschung, Stuttgart
Heuts RMJ, Seidel HP and Selen WJ (1992). A comparison of two lot sizing-sequencing heuristics for the process industry. Eur J Oper Res 59: 413–424
Hindi KS (1995a). Algorithms for capacitated, multi-item lot-sizing without set-ups. J Oper Res Soc 46: 465–472
Hindi KS (1995b). Solving the single-item, capacitated dynamic lot-sizing problem with startup and reservation costs by tabu search. Comput Ind Eng 28(4): 701–707
Hung YF and Chien KL (2000). A multi-class multi-level capacitated lot sizing model. J Oper Res Soc 51(11): 1309–1318
Kang S, Malik K and Thomas LJ (1999). Lotsizing and scheduling on parallel machines with sequence-dependent setup costs. Manage Sci 45(2): 273–289
Karimi B, Fathemi Ghomi SMT and Wilson JM (2003). The capacitated lot sizing problem: a review of models and algorithms. Omega Int J Manage Sci 31(5): 365–378
Karimi B, Fathemi Ghomi SMT and Wilson JM (2006). A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over. J Oper Res Soc 57(2): 140–147
Katok E, Lewis HS and Harrison TP (1998). Lot sizing in general assembly systems with setup costs, setup times, and multiple constrained resources. Manage Sci 44(6): 859–877
Kleindorfer P and Newson E (1975). A lower bounding structure for lot-size scheduling problems. Oper Res 23(2): 299–311
Kuik R, Salomon M and Van Wassenhove LN (1994). Batching decisions: structure and models. Eur J Oper Res 75(2): 243–263
Laguna M (1999). A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup-times. IIE Trans 31: 125–134
Maes J and Van Wassenhove LN (1988). Multi-item single-level capacitated dynamic lot-sizing heuristics: a general review. J Oper Res Soc 39(11): 991–1004
Maes J, McClain JO and Van Wassenhove LN (1991). Multilevel capacitated lotsizing complexity and LP-based heuristics. Eur J Oper Res 53: 131–148
Meyr H (1999). Simultane Losgrößen- und Reihenfolgeplanung für kontinuierliche Produktionslinien – Modelle und Methoden im Rahmen des Supply Chain Management. Gabler, Wiesbaden
Meyr H (2000). Simultaneous lotsizing and scheduling by combining local search with dual reoptimization. Eur J Oper Res 120(2): 311–326
Meyr H (2002). Simultaneous lotsizing and scheduling on parallel machines. Eur J Oper Res 139(2): 277–292
Millar HH and Yang M (1993). An application of lagrangean decomposition to the capacitated multi-item lot sizing problem. Comput Oper Res 20(4): 409–420
Millar HH and Yang M (1994). Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering. Int J Prod Econ 34(1): 1–15
Miller AJ, Nemhauser GL and Savelsbergh MWP (2000). On the capacitated lot-sizing and continuous 0–1 knapsack polyhedra. Eur J Oper Res 125: 298–315
Moursli O and Pochet Y (2000). A branch-and-bound algorithm for the hybrid flowshop. Int J Prod Econ 64: 113–125
Özdamar L and Barbarosoglu G (1999). Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem. J Oper Res Soc 50: 810–825
Özdamar L and Birbil SI (1998). Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions. Eur J Oper Res 110(3): 525–547
Özdamar L and Bozyel MA (2000). The capacitated lot sizing problem with overtime decisions and setup times. IIE Trans 32(11): 1043–1057
Pochet Y and Wolsey L (1988). Lot size models with back-logging: strong reformulations and cutting planes. Math Program 40: 317–335
Quadt D (2004) Lot-sizing and scheduling for flexible flow lines. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin
Quadt D, Kuhn H (2004) Capacitated lot-sizing and scheduling with parallel machines, back-orders and setup carry-over. Working paper, Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, Ingolstadt, Germany
Quadt D and Kuhn H (2005). A conceptual framework for lot-sizing and scheduling of flexible flow lines. Int J Prod Res 43(11): 2291–2308
Riane F (1998) Scheduling hybrid flowshops: algorithms and applications. Ph.D. thesis, Facultés Universitaires Catholiques de Mons
Selen WJ and Heuts RMJ (1990). Operational production planning in a chemical manufacturing environment. Eur J Oper Res 45: 38–46
Smith-Daniels VL and Ritzman LP (1988). A model for lot-sizing and sequencing in process industries. Int J Prod Res 26: 647–674
Smith-Daniels VL and Smith-Daniels DE (1986). A mixed integer programming model for lot sizing and sequencing packaging lines in the process industries. IIE Trans 18: 278–285
Sox CR and 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(3): 561–581
Sürie C (2005) Time continuity in discrete time models. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin
Sürie C and Stadtler H (2003). The capacitated lot-sizing problem with linked lot-sizes. Manage Sci 49(8): 1039–1054
Tempelmeier H and Derstroff M (1996). A lagrangean-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Manage Sci 42(5): 738–757
Tempelmeier H and Helber S (1994). A heuristic for the dynamic multi-item multi-level capacitated lotsizing for general product structures. Eur J Oper Res 75: 296–311
Tempelmeier H and Helber S (1995). Lot sizing in capacitated production planning and control systems. OR Spectrum 17(1): 5–18
Thizy JM and Van Wassenhove LN (1985). Lagrangean relaxation for the multi-item capacitated lot-sizing problem: a heuristic implementation. IIE Trans 17(4): 308–313
Trigeiro WW, Thomas LJ and McClain JO (1989). Capacitated lot sizing with setup times. Manage Sci 35(3): 353–366
Voss S (1999). The steiner tree problem with hop constraints. Ann Oper Res 86: 321–345
Wittrock RJ (1988). An adaptable scheduling algorithm for flexible flow lines. Oper Res 36(4): 445–453
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Quadt, D., Kuhn, H. Capacitated lot-sizing with extensions: a review. 4OR 6, 61–83 (2008). https://doi.org/10.1007/s10288-007-0057-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-007-0057-1