In this article, we propose novel reformulations for capacitated lot sizing problem. These reformulations are the result of reducing the number of variables (by eliminating the backorder variable) or increasing the number of constraints (time capacity constraints) in the standard problem formulation. These reformulations are expected to reduce the computational time complexity of the problem. Their computational efficiency is evaluated later in this article through numerical analysis on randomly generated problems.
References
[1]
Billington, P.J., McClain, J.O. and Joseph Thomas, L. (1983) Mathematical Programming Approaches to Capacity-Constrained MRP Systems: Review, Formulation and Problem Reduction. Management Science, 29, 1126-1141. https://doi.org/10.1287/mnsc.29.10.1126
[2]
Wagner, H.M. and Whitin, T.M. (1958) Dynamic Version of the Economic Lot Size Model. Management Science, 5, 89-96. https://doi.org/10.1287/mnsc.5.1.89
[3]
Dillenberger, C., Escudero, L.F., Wollensak, A. and Zhang, W. (1993) On Solving a Large-Scale Resource Allocation Problem in Production Planning. Operations Research in Production Planning and Control, Springer, Berlin, 105-119. https://doi.org/10.1007/978-3-642-78063-9_7
[4]
Haase, K. (2012) Lotsizing and Scheduling for Production Planning. Vol. 408, Springer Science & Business Media. https://books.google.co.in/books?hl=en&lr=&id=QVL-CAAAQBAJ&oi=fnd&pg=PA1&dq=Lot
sizing+and+scheduling+for+production+planning&ots=HSTSWCFLRT&sig=nDlJCwQpjGkD0DPW
ZUGI2RMa3Kg#v=onepage&q=Lotsizing%20and%20scheduling%20for%20production%20pl
anning&f=false
[5]
Suerie, C. and Stadtler, H. (2003) The Capacitated Lot-Sizing Problem with Linked Lot Sizes. Management Science, 49, 1039-1054. https://doi.org/10.1287/mnsc.49.8.1039.16406
[6]
Eppen, G.D. and Kipp Martin, R. (1987) Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition. Operations Research, 35, 832-848. https://doi.org/10.1287/opre.35.6.832
[7]
Tempelmeier, H. and Helber, S. (1994) A Heuristic for Dynamic Multi-Item Multi-Level Capacitated Lotsizing for General Product Structures. European Journal of Operational Research, 75, 296-311. https://doi.org/10.1016/0377-2217(94)90076-0
[8]
Stadtler, H. (1996) Mixed Integer Programming Model Formulations for Dynamic Multi-Item Multi-Level Capacitated Lotsizing. European Journal of Operational Research, 94, 561-581. https://doi.org/10.1016/0377-2217(95)00094-1
[9]
Stadtler, H. (1997) Reformulations of the Shortest Route Model for Dynamic Multi-Item Multi-Level Capacitated Lotsizing. Operations-Research-Spektrum, 19, 87-96. https://doi.org/10.1007/BF01545506
[10]
Rosling, K. (1986) Optimal Lot-Sizing for Dynamic Assembly Systems. Multi-Stage Production Planning and Inventory Control, Springer, Berlin, 119-131. https://doi.org/10.1007/978-3-642-51693-1_7
[11]
Maes, J., McClain, J.O. and Van Wassenhove, L.N. (1991) Multilevel Ca-pacitated Lotsizing Complexity and LP-Based Heuristics. European Journal of Operational Research, 53, 131-148. https://doi.org/10.1016/0377-2217(91)90130-N
[12]
Denizel, M., Tevhide Altekin, F., Süral, H. and Stadtler, H. (2008) Equivalence of the LP Relaxations of Two Strong Formulations for the Capacitated Lot-Sizing Problem with Setup Times. OR Spectrum, 30, 773-785. https://doi.org/10.1007/s00291-007-0094-3
[13]
Barany, I., Van Roy, T.J. and Wolsey, L.A. (1984) Strong Formulations for Multi-Item Capacitated Lot Sizing. Management Science, 30, 1255-1261. https://doi.org/10.1287/mnsc.30.10.1255
[14]
Pochet, Y. and Wolsey, L.A. (1991) Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes. Management Science, 37, 53-67. https://doi.org/10.1287/mnsc.37.1.53
[15]
Clark, P.W. and Armentano, L.E. (1997) Replacement of Alfalfa Neutral Detergent Fiber with a Combination of Nonforage Fiber Sources. Journal of Dairy Science, 80, 675-680. https://doi.org/10.3168/jds.S0022-0302(97)75986-1
[16]
Miller, A.J., Nemhauser, G.L. and Savelsbergh, M.W.P. (2000) On the Capacitated Lot-Sizing and Continuous 0-1 Knapsack Polyhedra. European Journal of Operational Research, 125, 298-315. https://doi.org/10.1016/S0377-2217(99)00461-0
