Polynomial dynamic programming algorithms for lot sizing models with bounded inventory and stockout and/or backlogging

Abstract

This paper addresses a dynamic lot sizing problem with bounded inventory and stockout where both no backlogging and backlogging allowed cases are considered. The stockout option means that there is outsourcing in a period only when the inventory level at that period is non-positive. The production capacity is unlimited and production cost functions are linear but with fixed charges. The problem is that of satisfying all demands in the planning horizon at minimal total cost. We show that the no backlogging case can be solved in ) O(T ²) time with general concave inventory holding and outsourcing cost functions where T is the length of the planning horizon. The complexity can be reduced to O(T) when the inventory holding cost functions are also linear and have some realistic properties, even if the outsourcing cost functions remain general concave functions. When the inventory holding and outsourcing cost functions are linear, the backlogging case can be solved in O(T ³logT) time whether the outsourcing level at each period is bounded by the sum of the demand of that period and backlogging level from previous periods, or only by the demand of that period.

Keywords

Dynamic lot sizing problem / bounded inventory / outsourcing / backlogging / stockout / dynamic programming

References

[1] Absi N., Kedad-Sidhoum S., Dauzère-Pérès S.. Uncapacitated lot-sizing problem with production time windows, backlogs and lost sales. International Journal of Production Research, 2011, 49(9): 2551-2566.

[2] Aggarwal A., Park J.K.. Improved algorithms for economic lot-size problems. Operations Research, 1993, 41(3): 549-571.

[3] Aksen D., Altinkemer K., Chand S.. The single-item lot-sizing problem with immediate lost sales. European Journal of Operational Research, 2003, 147(3): 558-566.

[4] Aksen D.. Loss of customer goodwill in the uncapaciated lot-sizing problem. Computers & Operations Research, 2007, 34(9): 2805-2823.

[5] Atamtürk A., Hochbaum D.S.. Capacity acquisition, subcontracting, and lot sizing. Management Science, 2001, 47(8): 1081-1100.

[6] Atamtürk A., Küçükyavuz S.. Lot sizing with inventory bounds and fixed costs: polyhedral study and computation. Operations Research, 2005, 53(4): 711-730.

[7] Atamtürk A., Küçükyavuz S.. An O(n2) algorithm for lot sizing with inventory bounds and fixed costs. Operations Research Letters, 2008, 36(3): 297-299.

[8] Baker K., Dixon P., Magazine M., Silver E.. An algorithm for the dynamic lot-size problem with time-varying production capacity constraints. Management Science, 1978, 24(16): 1710-1720.

[9] Bitran G., Yanasse H.. Computational complexity of the capacitated lot size problem. Management Science, 1982, 28(10): 1174-1186.

[10] Blackburn J.D., Kunreuther H.. Planning horizon for the dynamic lot size model with backlogging. Management Science, 1974, 21(3): 1174-1186.

[11] Chen H., Hearn D., Lee C.. A new dynamic programming algorithm for the single item capacitated dynamic lot size model. Journal of Global Optimization, 1994, 4(3): 285-300.

[12] Chu F., C C., X L.. Lot sizing models with backlog or outsourcing. IEEE International Conference: Systems, Man and Cybernetics, 2004, 5: 4342-4347.

[13] Chu F., Chu C.. Polynomial algorithms for single item lot sizing models with bounded inventory and backlogging or outsourcing. IEEE Transactions on Automation Science and Engineering, 2007, 4(2): 233-251.

[14] Chu C., Chu F., Zhong J., Yang S.. A polynomial algorithm for a lot-sizing problem with backlogging, outsourcing and limited inventory. Computers & Industrial Engineering, 2013, 64(1): 200-210.

[15] Chung C., Lin C.. An O(T2) algorithm for the NI/G/NI/ND capacitated lot size problem. Management Science, 1988, 34(3): 420-426.

[16] Federgruen A., Tzur M.. A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time. Management Science, 1991, 37(8): 909-925.

[17] Feng Y., Chen S., Kumar A., Lin B.. Solving single-product economic lotsizing problem with non-increasing setup cost, constant capacity and convex inventory cost in O(NlogN) time. Computers & |Operations Research, 2011, 38(8): 717-722.

[18] Florian M., J L., A R. K.. Deterministic production planning: algorithms and complexity. Management Science, 1980, 26(7): 669-679.

[19] Florian M., Klein M.. Deterministic production planning with concave costs and capacity constraints. Management Science, 1971, 18(1): 12-20.

[20] Ganas L., Papachristos S.. The single-product lot-sizing problem with constant parameters and backlogging: exact results, a new solution, and all parameter stability regions. Operations Research, 2005, 53(1): 170-176.

[21] Gutiérrez J., Sedeno-Noda A., Colebrook M., Sicilia J.. A new characterization for the dynamic lot size problem with bounded inventory. Computer & Operations Research, 2002, 30(3): 383-395.

[22] Gutiérrez J., Sedeno-Noda A., Colebrook M., Sicilia J.. A polynomial algorithm for the production/ordering planning problem with limited storage. Computer & Operations Research, 2007, 34(4): 934-937.

[23] Janannathan R., Rao M.. A class of deterministic production planning problems. Management Science, 1973, 19(11): 1295-1300.

[24] Larmore L.L., Schieber B.. On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 1991, 12(3): 490-515.

[25] Lee H.L., Nahmias S.. Single-product, single-location models. Handbooks in Operations Research and Management Science Logistics of Production and Inventory, 1993, 4: 3-55.

[26] Love S.F.. Bounded production and inventory models with piecewise concave costs. Management Science, 1973, 20(3): 313-318.

[27] Lundin R.E., Morton T.E.. Planning horizon for the dynamic lot size model: zabel versus protective procedure and computational results. Operations Research, 1975, 23(4): 711-734.

[28] Morton T.E.. An improved algorithm for the stationary cost dynamic lot size model with backlogging. Management Science, 1978, 24(8): 869-873.

[29] Shaw D.X., Wagelmans A.. An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs. Management Science, 1998, 44(6): 831-838.

[30] Sandbothe R.A., Thompson G.L.. A forward algorithm for the capacitated lot size model with stockouts. Operation Research, 1990, 38(3): 474-486.

[31] Sandbothe R.A., Thompson G.L.. Decision horizons for the capacitated lot size model with inventory bounds and stockouts. Computer & Operations Research, 1993, 20(5): 455-465.

[32] Swoveland C.. A deterministic multi-period production planning model with piecewise concave production and holding-backorder costs. Management Science, 1975, 21(9): 1007-1013.

[33] Van den Heuvel W., Gutiérriez J. M., Hwang H.-C.. Note on “An efficient approach for solving the lot-sizing problem with time-varying storage capacities”. European Journal of Operational Research, 2011, 213(2): 455-457.

[34] Van den Heuvel W., Wagelmans A. P. M.. An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem. Computers & Operations Research, 2006, 33(12): 3583-3599.

[35] Van Hoesel C., Wagelmans A.. An O(T3) algorithm for the economic lot-sizing problem with constant capacities. Management Science, 1996, 42(1): 142-150.

[36] Van Hoesel C., Wagelmans A.. Fully polynomial approximation schemes for single-item capacitated economic lot-sizng problems. Mathematics of Operations Research, 2001, 26(2): 339-357.

[37] Veinott A.F.. Production planning with convex costs: a parametric study. Management Science, 1964, 10(3): 441-460.

[38] Wagelmans S., Kolen A.. Economic lot-sizing: An O(n log n)algorithm that runs in linear time in the Wagner-Whitin case. Operations Research, 1992, 40(1): 145-156.

[39] Wagner H.M., Whitin T.M.. Dynamic version of the economic lot-size model. Management Science, 1958, 5(1): 89-96.

[40] Zangwill W.I.. A deterministic multi-period production scheduling model with backlogging. Management Science, 1966, 13(1): 105-119.