Research ArticleOpen AccessGoogle Scholar indexed
Computationally Efficient Problem Reformulations for Capacitated Lot Sizing Problem
Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
- 1 Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
- 2 Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
- 3 Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India
American Journal of Operations Research·Volume 08 (2018)·Pages 312–322·Published 28 June 2018·DOI10.4236/ajor.2018.84018
Copy link · social · email
Abstract
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.
KeywordsCapacitated Lot Sizing ProblemEfficient Problem FormulationBranch and Bound
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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