×

Two-level lot-sizing with inventory bounds. (English) Zbl 1454.90006

Summary: We study a two-level uncapacitated lot-sizing problem with inventory bounds that occurs in a supply chain composed of a supplier and a retailer. The first level with the demands is the retailer level and the second one is the supplier level. The aim is to minimize the cost of the supply chain so as to satisfy the demands when the quantity of item that can be held in inventory at each period is limited. The inventory bounds can be imposed at the retailer level, at the supplier level or at both levels. We propose a polynomial dynamic programming algorithm to solve this problem when the inventory bounds are set on the retailer level. When the inventory bounds are set on the supplier level, we show that the problem is NP-hard. We give a pseudo-polynomial algorithm which solves this problem when there are inventory bounds on both levels. In the case where demand lot-splitting is not allowed, i.e. each demand has to be satisfied by a single order, we prove that the uncapacitated lot-sizing problem with inventory bounds is strongly NP-hard. This implies that the two-level lot-sizing problems with inventory bounds are also strongly NP-hard when demand lot-splitting is considered.

MSC:

90B05 Inventory, storage, reservoirs
90C39 Dynamic programming
90C23 Polynomial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atamtürk, A.; Küçükyavuz, S., An o \((n^2)\) algorithm for lot sizing with inventory bounds and fixed costs, Oper. Res. Lett., 36, 3, 297-299 (2008) · Zbl 1152.90639
[2] Love, S. F., Bounded production and inventory models with piecewise concave costs, Manage. Sci., 20, 3, 313-318 (1973) · Zbl 0322.90028
[3] Atamtürk, A.; Küçükyavuz, S., Lot sizing with inventory bounds and fixed costs: Polyhedral study and computation, Oper. Res., 53, 4, 711-730 (2005) · Zbl 1165.90304
[4] E. Toczyowski, (1995) An o \(( t^2\); E. Toczyowski, (1995) An o \(( t^2\)
[5] Hwang, H.-C.; van den Heuvel, W., Improved algorithms for a lot-sizing problem with inventory bounds and backlogging, Naval Res. Logist. (NRL), 59, 3-4, 244-253 (2012) · Zbl 1407.90018
[6] Gutiérrez, J.; Sedeo-Noda, A.; Colebrook, M.; Sicilia, J., An efficient approach for solving the lot-sizing problem with time-varying storage capacities, European J. Oper. Res., 189, 3, 682-693 (2008) · Zbl 1146.90313
[7] Wagelmans, A.; van Hoesel, S., Economic lot sizing: An o(n log n) algorithm that runs in linear time in the wagner-whitin case, Oper. Res., 40, S145-S156 (1992) · Zbl 0771.90031
[8] van den Heuvel, W.; Gutirrez, J. M.; Hwang, H.-C., Note on an efficient approach for solving the lot-sizing problem with time-varying storage capacities, European J. Oper. Res., 213, 2, 455-457 (2011) · Zbl 1231.90025
[9] Liu, T., Economic lot sizing problem with inventory bounds, European J. Oper. Res., 185, 1, 204-215 (2008) · Zbl 1146.90008
[10] Önal, M.; van den Heuvel, W.; Liu, T., A note on “The economic lot sizing problem with inventory bounds”, European J. Oper. Res., 223, 1, 290-294 (2012) · Zbl 1253.90029
[11] Atamtürk, A.; Küçükyavuz, S.; Tezel, B., Path cover and path pack inequalities for the capacitated fixed-charge network flow problem, SIAM J. Optim., 27, 3, 1943-1976 (2017) · Zbl 1370.90151
[12] Zangwill, W. I., A backlogging model and a multi-echelon model of a dynamic economic lot size production system—a network approach, Manage. Sci., 15, 9, 506-527 (1969) · Zbl 0172.44603
[13] van Hoesel, S.; Romeijn, H. E.; Morales, D. R.; Wagelmans, A. P.M., Integrated lot sizing in serial supply chains with production capacities, Manage. Sci., 51, 11, 1706-1719 (2005) · Zbl 1232.90201
[14] Melo, R. A.; Wolsey, L. A., Uncapacitated two-level lot-sizing, Oper. Res. Lett., 38, 4, 241-245 (2010) · Zbl 1193.90091
[15] Zhang, M.; Küçükyavuz, S.; Yaman, H., A polyhedral study of multiechelon lot sizing with intermediate demands, Oper. Res., 60, 4, 918-935 (2012) · Zbl 1260.90031
[16] Jaruphongsa, W.; Çetinkaya, S.; Lee, C.-Y., Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain, Int. J. Prod. Econ., 92, 2, 169-180 (2004)
[17] H.-C. Hwang, H.-G. Jung, Warehouse capacitated lot-sizing for a two-stage supply chain, in: The 2011 KORMS/KIIE Spring Joint Conference on 26 May, Incheon, Korea, 2011, pp. 914-917.; H.-C. Hwang, H.-G. Jung, Warehouse capacitated lot-sizing for a two-stage supply chain, in: The 2011 KORMS/KIIE Spring Joint Conference on 26 May, Incheon, Korea, 2011, pp. 914-917.
[18] Zangwill, W. I., Minimum concave cost flows in certain networks, Manage. Sci., 14, 7, 429-450 (1968) · Zbl 0159.49102
[19] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039
[20] Florian, M.; Lenstra, J. K.; Kan, A. H.G. R., Deterministic production planning: Algorithms and complexity, Manage. Sci., 26, 7, 669-679 (1980) · Zbl 0445.90025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.