No Access

Polynomial-Time Solvability of Dynamic Lot Size Problems

Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

E-mail Address: chung-lun.li@polyu.edu.hk

Corresponding author.

and

Glorious Sun School of Business and Management, Donghua University, 1882 West Yan’an Road, Shanghai, China, 200051, China

E-mail Address: liqingying@dhu.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0217595916500184Cited by:0 (Source: Crossref)

Abstract

There has been a lot of research on dynamic lot sizing problems with different nonlinear cost structures due to capacitated production, minimum order quantity requirements, availability of quantity discounts, etc. Developing optimal solutions efficiently for dynamic lot sizing models with nonlinear cost functions is a challenging topic. In this paper, we present a set of sufficient conditions such that if a single-item dynamic lot sizing problem satisfies these conditions, then the existence of a polynomial-time solution method for the problem is guaranteed. Several examples are presented to demonstrate the use of these sufficient conditions.

Keywords:

References

Aggarwal, A and JK Park (1993). Improved algorithms for economic lot size problems. Operations Research, 41(3), 549–571. Crossref, Web of Science, Google Scholar
Akbalik, A and Y Pochet (2009). Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs. European Journal of Operational Research, 198(2), 412–434. Crossref, Web of Science, Google Scholar
Akbalik, A and C Rapine (2012). Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost. Operations Research Letters, 40(5), 390–397. Crossref, Web of Science, Google Scholar
Akbalik, A and C Rapine (2013). The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases. European Journal of Operational Research, 229(2), 353–363. Crossref, Web of Science, Google Scholar
Archetti, C, L Bertazzi and MG Speranza (2014). Polynomial cases of the economic lot sizing problem with cost discounts. European Journal of Operational Research, 237(2), 519–527. Crossref, Web of Science, Google Scholar
Atamtürk, A and S Küçükyavuz (2008). An $O (n^{2})$ $O (n^{2})$ algorithm for lot sizing with inventory bounds and fixed costs. Operations Research Letters, 36(3), 297–299. Crossref, Web of Science, Google Scholar
Bitran, GR and HH Yanasse (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10), 1174–1186. Crossref, Web of Science, Google Scholar
Brahimi, N, S Dauzere-Peres, NM Najid and A Nordli (2006). Single item lot sizing problems. European Journal of Operational Research, 168(1), 1–16. Crossref, Web of Science, Google Scholar
Buschkühl, L, F Sahling, S Helber and H Tempelmeier (2010). Dynamic capacitated lot-sizing problems: A classification and review of solution approaches. OR Spectrum, 32(2), 231–261. Crossref, Web of Science, Google Scholar
Chan, LMA, A Muriel, Z-J Shen and D Simchi-Levi (2002). On the effectiveness of zero-inventory-ordering policies for the economic lot-sizing model with a class of piecewise linear cost structures. Operations Research, 50(6), 1058–1067. Crossref, Web of Science, Google Scholar
Chen, H-D, DW Hearn and C-Y Lee (1994). A new dynamic programming algorithm for the single item capacitated dynamic lot size model. Journal of Global Optimization, 4(3), 285–300. Crossref, Web of Science, Google Scholar
Chubanov, S, MY Kovalyov and E Pesch (2006). An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure. Mathematical Programming, Series A, 106(3), 453–466. Crossref, Web of Science, Google Scholar
Chubanov, S and E Pesch (2012). An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand. Operations Research Letters, 40(6), 445–449. Crossref, Web of Science, Google Scholar
Chung, C-S, DT Chiang and C-Y Lu (1987). An optimal algorithm for the quantity discount problem. Journal of Operations Management, 7(1–2), 165–177. Crossref, Google Scholar
Elmaghraby, SE and VY Bawle (1972). Optimization of batch ordering under deterministic variable demand. Management Science, 18(8), 508–517. Crossref, Web of Science, Google Scholar
Federgruen, A and C-Y Lee (1990). The dynamic lot size model with quantity discount. Naval Research Logistics, 37(5), 707–713. Crossref, Web of Science, Google Scholar
Federgruen, A and M Tzur (1991). A simple forward algorithm to solve general dynamic lot sizing models with $n$ $n$ periods in $O (n log n)$ $O (n log n)$ or $O (n)$ $O (n)$ time. Management Science, 37(8), 909–925. Crossref, Web of Science, Google Scholar
Florian, M and M Klein (1971). Deterministic production planning with concave costs and capacity constraints. Management Science, 18(1), 12–20. Crossref, Web of Science, Google Scholar
Florian, M, JK Lenstra and AHG Rinnooy Kan (1980). Deterministic production planning: Algorithms and complexity. Management Science, 26(7), 669–679. Crossref, Web of Science, Google Scholar
Gutiérrez, J, A Sedeño-Noda, M Colebrook and J Sicilia (2002). A new characterization for the dynamic lot size problem with bounded inventory. Computers & Operations Research, 30(3), 383–395. Crossref, Web of Science, Google Scholar
Gutiérrez, J, A Sedeño-Noda, M Colebrook and J Sicilia (2007). A polynomial algorithm for the production/ordering planning problem with limited storage. Computers & Operations Research, 34(4), 934–937. Crossref, Web of Science, Google Scholar
Halman, N, JB Orlin and D Simchi-Levi (2012). Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data is given by an oracle. Operations Research, 60(2), 429–446. Crossref, Web of Science, Google Scholar
Hellion, B, F Mangione and B Penz (2012). A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs. European Journal of Operational Research, 222(1), 10–16. Crossref, Web of Science, Google Scholar
Hellion, B, F Mangione and B Penz (2013). Corrigendum to “A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs” [Eur. J. Oper. Res. 222 (2012) 10–16]. European Journal of Operational Research, 229(1), 279. Google Scholar
Hwang, H-C (2010). A dynamic lot-sizing problem with backlogging for minimum replenishment policy. Journal of the Korean Institute of Industrial Engineers, 36(1), 7–12. Google Scholar
Hwang, H-C and W Van den Heuvel (2012). Improved algorithms for lot-sizing problem with inventory bounds and backlogging. Naval Research Logistics, 59(3–4), 244–253. Crossref, Web of Science, Google Scholar
Jans, R and Z Degraeve (2007). Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches. European Journal of Operational Research, 177(3), 1855–1875. Crossref, Web of Science, Google Scholar
Jans, R and Z Degraeve (2008). Modeling industrial lot sizing problems: A review. International Journal of Production Research, 46(6), 1619–1643. Crossref, Web of Science, Google Scholar
Koca, E, H Yaman and MS Aktürk (2014). Lot sizing with piecewise concave production costs. INFORMS Journal on Computing, 26(4), 767–779. Crossref, Web of Science, Google Scholar
Lee, C-Y (1989). A solution to the multiple set-up problem with dynamic demand. IIE Transactions, 21(3), 266–270. Crossref, Web of Science, Google Scholar
Lee, C-Y (2004). Inventory replenishment model: Lot sizing versus just-in-time delivery. Operations Research Letters, 32(6), 581–590. Crossref, Web of Science, Google Scholar
Lee, C-Y and X Li (2013). Economic lot sizing: The capacity reservation model. Operations Research Letters, 41(6), 670–674. Crossref, Web of Science, Google Scholar
Lee, S-B and PH Zipkin (1989). A dynamic lot-size model with make-or-buy decisions. Management Science, 35(4), 447–458. Crossref, Web of Science, Google Scholar
Li, C-L, VN Hsu and W-Q Xiao (2004). Dynamic lot sizing with batch ordering and truckload discounts. Operations Research, 52(4), 639–654. Crossref, Web of Science, Google Scholar
Li, C-L, J Ou and VN Hsu (2012). Dynamic lot sizing with all-units discount and resales. Naval Research Logistics, 59(3–4), 230–243. Crossref, Web of Science, Google Scholar
Lippman, SA (1969). Optimal inventory policy with multiple set-up costs. Management Science, 16(1), 118–138. Crossref, Web of Science, Google Scholar
Liu, T (2008). Economic lot sizing problem with inventory bounds. European Journal of Operational Research, 185(1), 204–215. Crossref, Web of Science, Google Scholar
Love, SF (1973). Bounded production and inventory models with piecewise concave costs. Management Science, 20(3), 313–318. Crossref, Web of Science, Google Scholar
Mirmohammadi, HS and K Eshghi (2012). A hybrid polynomial-time algorithm for the dynamic quantity discount lot size model with resale. Computers & Operations Research, 39(7), 1771–1778. Crossref, Web of Science, Google Scholar
Ng, CT, MY Kovalyov and TCE Cheng (2010). A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure. European Journal of Operational Research, 200(2), 621–624. Crossref, Web of Science, Google Scholar
Okhrin, I and K Richter (2011a). An $O (T^{3})$ $O (T^{3})$ algorithm for the capacitated lot sizing problem with minimum order quantities. European Journal of Operational Research, 211(3), 507–514. Crossref, Web of Science, Google Scholar
Okhrin, I and K Richter (2011b). The linear dynamic lot size problem with minimum order quantity. International Journal of Production Economics, 133(2), 688–693. Crossref, Web of Science, Google Scholar
Ou, J (2012). Economic lot sizing with constant capacities and concave inventory costs. Naval Research Logistics, 59(7), 497–501. Crossref, Web of Science, Google Scholar
Piñeyro, P, O Viera and H Cancela (2013). An $O (T^{3})$ $O (T^{3})$ algorithm for the capactitated economic lot-sizing problem with stationary capacities and concave cost functions with non-speculative motives. Lecture Notes in Management Science, 5, 39–45. Google Scholar
Pochet, Y and LA Wolsey (1993). Lot-sizing with constant batches: Formulation and valid inequalities. Mathematics of Operations Research, 18(4), 767–785. Crossref, Web of Science, Google Scholar
Shaw, DX and APM Wagelmans (1998). An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs. Management Science, 44(6), 831–838. Crossref, Web of Science, Google Scholar
Sohn, K-I and H Hwang (1987). A dynamic quantity discount lot size model with resales. European Journal of Operational Research, 28(3), 293–297. Crossref, Web of Science, Google Scholar
Suwondo, E and H Yuliando (2012). Dynamic lot-sizing problems: A review on model and efficient algorithm. Agroindustrial Journal, 1(1), 36–49. Crossref, Google Scholar
Swoveland, C (1975). A deterministic multi-period production planning model with piecewise concave production and holding-backorder costs. Management Science, 21(9), 1007–1013. Crossref, Web of Science, Google Scholar
Van den Heuvel, W and APM Wagelmans (2008). Four equivalent lot-sizing models. Operations Research Letters, 36(4), 465–470. Crossref, Web of Science, Google Scholar
Van Hoesel, CPM and APM Wagelmans (1996). An $O (T^{3})$ $O (T^{3})$ algorithm for the economic lot-sizing problem with constant capacities. Management Science, 42(1), 142–150. Crossref, Web of Science, Google Scholar
Van Hoesel, CPM and APM Wagelmans (2001). Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems. Mathematics of Operations Research, 26(2), 339–357. Crossref, Web of Science, Google Scholar
Van Vyve, M (2007). Algorithms for single-item lot-sizing problems with constant batch size. Mathematics of Operations Research, 32(3), 594–613. Crossref, Web of Science, Google Scholar
Vander Eecken, J (1968). Investigation of a class of constrained inventory problems. Doctoral dissertation, Yale University, New Haven, CT. Google Scholar
Wagelmans, A, S Van Hoesel and A Kolen (1992). Economic lot sizing: An $O (n log n)$ $O (n log n)$ algorithm that runs in linear time in the Wagner-Whitin case. Operations Research, 40(S1), S145–S156. Crossref, Web of Science, Google Scholar
Wagner, HM (1960). A postscript to “Dynamic problems in the theory of the firm.” Naval Research Logistics Quarterly, 7(1), 7–12. Crossref, Google Scholar
Wagner, HM and TM Whitin (1958). Dynamic version of the economic lot size model. Management Science, 5(1), 89–96. Crossref, Web of Science, Google Scholar
Xu, J and LL Lu (1998). The dynamic lot size model with quantity discount: Counterexamples and correction. Naval Research Logistics, 45(4), 419–422. Crossref, Web of Science, Google Scholar
Zangwill, WI (1966). A deterministic multi-period production scheduling model with backlogging. Management Science, 13(1), 105–119. Crossref, Google Scholar
Zangwill, WI (1969). A backlogging model and a multi-echelon model of a dynamic economic lot size production system—A network approach. Management Science, 15(9), 506–527. Crossref, Web of Science, Google Scholar