This thesis primarily discusses dynamic lot sizing problems for a single item with time-varying deterministic demand. In particular, we carefully review the literature on how special cost assumptions affect the optimal policy structure so as to develop an efficient solution pro-cedure. Our main focus is placed on the development of efficient dynamic programming (DP) procedures, especially a well-known Wagner-Whitin forward DP method for seeking an ex-act optimal solution. This Wagner-Whitin DP algorithm can solve the N-period problem in O(N2) under the concave cost assumptions. In the literature, however, some statements can be found that oppose this exact Wagner-Whitin DP algorithm, misleading the readers to approx-imate heuristic procedures. This is our initial impetus for this thesis to investigate why such misperception of the Wagner-Whitin DP method has arisen in the literature.

Through our early investigation of the literature, we shall carefully describe the develop-ment of various DP procedures. To this end, we begin with a (standard) straight-forward DP that can work under no particular cost assumption, but it works painfully slow, evaluating all the possible inventory levels at each period and also all the possible decisions at each state of inventory level. In practice, however, certain cost structure often entails in the objective func-tion to be minimized. Exploiting such posed special cost structure is often useful in narrowing down the DP search space for an optimal solution. In an extreme case, where the cost func-tion and constraints are all linear functions, the standard linear programming (LP) can apply, and an optimal solution can be found at an extreme point in the feasible solution space. Un-der the concave cost assumptions, Wagner and Whitin (1958) discovered such similar solution structure, and then developed a so-called regeneration-point DP approach, which is called the Wagner-Whitin DP algorithm above.

Furthermore, Wagner and Whitin discovered what they called “Planning Horizon Theo-rem” based on the special concave cost assumption; this makes the procedure more computationally attractive than the above-mentioned Wagner-Whitin DP that works in O(N2). In the literature, some investigators appeared to ignore the special cost assumptions; in consequence, some misleading results and statements can be found that a heuristic method can outperform the Wagner-Whitin DP method for rolling-horizon schedules, some of which are totally outside the special assumptions required for the “Planning Horizon Theorem” to hold. We shall discuss this issue in this thesis.

Finally, we also describe how to improve the (standard) straight-forward DP in order to make it as attractive as the Wagner-Whitin regeneration point approach. This is motivated by Dreyfus and Law (1977, Chapter 2), where the straight-forward DP and a regeneration-point DP work equally well in solving an equipment replacement problem, although the straight-forward DP has two state variables whereas the regeneration-pint DP has only one state variable. We compare them in some detail since this comparison is new to the dynamic lot sizing literature to the best of our knowledge.

This thesis primarily discusses dynamic lot sizing problems for a single item with time-varying deterministic demand. In particular, we carefully review the literature on how special cost assumptions affect the optimal policy structure so as to develop an efficient solution pro-cedure. Our main focus is placed on the development of efficient dynamic programming (DP) procedures, especially a well-known Wagner-Whitin forward DP method for seeking an ex-act optimal solution. This Wagner-Whitin DP algorithm can solve the N-period problem in O(N2) under the concave cost assumptions. In the literature, however, some statements can be found that oppose this exact Wagner-Whitin DP algorithm, misleading the readers to approx-imate heuristic procedures. This is our initial impetus for this thesis to investigate why such misperception of the Wagner-Whitin DP method has arisen in the literature.

Through our early investigation of the literature, we shall carefully describe the develop-ment of various DP procedures. To this end, we begin with a (standard) straight-forward DP that can work under no particular cost assumption, but it works painfully slow, evaluating all the possible inventory levels at each period and also all the possible decisions at each state of inventory level. In practice, however, certain cost structure often entails in the objective func-tion to be minimized. Exploiting such posed special cost structure is often useful in narrowing down the DP search space for an optimal solution. In an extreme case, where the cost func-tion and constraints are all linear functions, the standard linear programming (LP) can apply, and an optimal solution can be found at an extreme point in the feasible solution space. Un-der the concave cost assumptions, Wagner and Whitin (1958) discovered such similar solution structure, and then developed a so-called regeneration-point DP approach, which is called the Wagner-Whitin DP algorithm above.

Furthermore, Wagner and Whitin discovered what they called “Planning Horizon Theo-rem” based on the special concave cost assumption; this makes the procedure more computationally attractive than the above-mentioned Wagner-Whitin DP that works in O(N2). In the literature, some investigators appeared to ignore the special cost assumptions; in consequence, some misleading results and statements can be found that a heuristic method can outperform the Wagner-Whitin DP method for rolling-horizon schedules, some of which are totally outside the special assumptions required for the “Planning Horizon Theorem” to hold. We shall discuss this issue in this thesis.

Finally, we also describe how to improve the (standard) straight-forward DP in order to make it as attractive as the Wagner-Whitin regeneration point approach. This is motivated by Dreyfus and Law (1977, Chapter 2), where the straight-forward DP and a regeneration-point DP work equally well in solving an equipment replacement problem, although the straight-forward DP has two state variables whereas the regeneration-pint DP has only one state variable. We compare them in some detail since this comparison is new to the dynamic lot sizing literature to the best of our knowledge.

[1] Stuart E. Dreyfus and Averill M. Law. Art and Theory of Dynamic Programming. Academic Press, Inc. Orlando, FL, USA, 1977.

[2] E.A. Silver, D.F. Pyke, and R. Peterson. Inventory Management and Production Planning and Scheduling : Third Edition. Wiley, 1998.

[3] Harvey M. Wagner and Thomson M. Whitin. Dynamic version of the economic lot size model. Management Science, 5(1):89–96, 1958.

[4] Joseph D Blackburn and Robert A Millen. Heuristic lot-sizing performance in a rolling-schedule environment. Decision Sciences, 11(4):691–701, 1980.

[5] E.A. Silver and H.C. Meal. A simple modification of the eoq for the case of varying demand rate. Production and Inventory Management, 10:52–65, 1969.

[6] Gabriel R Bitran, Thomas L Magnanti, and Horacio H Yanasse. Approximation methods for the uncapacitated dynamic lot size problem. Management Science, 30(9):1121–1140, 1984.

[7] John J. DeMatteis. An economic lot-sizing technique, i: The part-period algorithm. IBM systems Journal, 7(1):30–38, 1968.

[8] S. Nahmias and T.L. Olsen. Production and Operations Analysis: Seventh Edition. Wave-land Press, Inc., 2015.

[9] James R. Evans, Cem Saydam, and Mark McKnew. A note on solving the concave cost dynamic lot-sizing problem in almost linear time. Journal of Operations Management, 8(2):159–167, 1989.

[10] Awi Federgruen and Michal Tzur. A simple forward algorithm to solve general dynamic lot sizing models with n periods in o(nlogn) or o(n) time. Management Science, 37(8):909– 925, 1991.

[11] Nusrat T. Chowdury, M.F. Baki, and A. Azab. Dynamic economic lot-sizing problem: A new o(t) algorithm for the wagner-whitin model. Computers & Industrial Engineering, 117:6–18, 2018.

[12] Kenneth R. Baker. An experimental study of the effectiveness of rolling schedules in production planning. Decision Sciences, 8:19–27, 1977.

57

[13] Tianbing Qian, Philip C. Jones, and Yinyu Ye. Worst case analysis of forward wagner whitin algorithm with rolling horizon. unpublished, 1996.

[14] Robert C. Carlson, Sara L. Beckman, and Dean H. Kropp. The effectiveness of extending the horizon in rolling production scheduling. Decision Sciences, 13:129–145, 1982.

[15] James R. Evans. An efficient implementation of the wagner-whitin algorithm for dynamic lot-sizing. Journal of Operation Management, 5(2):229–235, 1985.

[16] Kenneth R. Baker and David W. Peterson. An analytic framework for evaluating rolling schedules. Management Science, 25(4):341–351, 1979.

[17] Richard Bellman. Dynamic programming approach to optimal inventory processes with delay in delivery. Quarterly of Applied Mathematics, 18(4):399–403, 1961.

[18] Albert P.M. Wagelmans, A. van Hoesel, and Antoon Kolen. Economic lot-sizing: An o(n log n) algorithm that runs in linear time in the wagner-whitin case. Operations Research, 40(Supp. 1):145–156, 1992.

[19] Alok Aggarwal and James K. Park. Improved algorithms for economic lot size problems Operations Research, 41(3):549–571, 1993.

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

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

[22] M. Florian, J.K. Lenstra, and A. Rinnooy Kan. Deterministic production planning: algo-rithms and complexity. Management Science, 26(7):669–679, 1980.

[23] A. Lambert and H. Luss. Production planning with time-dependent capacity bounds. Eu-ropean Journal of Operational Research, 9:275–280, 1982.

[24] Gabriel R. Bitran and Horacio H. Yanasse. Computational complexity of the capacitated lot size problem. Management Science, 28:1–13, 1982.

[25] Chia Shin Chung and Chien Hua Mike Lin. An O(T 2) algorithm for the N I=G=N I=N D capacitated lot size problem. Management Science, 34:420–426, 1988.

[26] O. Kirca. An efficient algorithm for the capacitated single item dynamic lot size problem. European Journal of Operational Research, 45(1):15–24, 1990.

[27] Hsin-Der Chen, Donald W. Hearn, and Chung Yee Lee. A new dynamic programming algorithm for the single item capacitated dynamic lot size model. Journal of Global Opti-mization, 4:285–300, 1994.

[28] C. P. M. van Hoesel and Albert P.M. Wagelmans. An O(T 3) algorithm for the economic lot-sizing problem with constant capacities. Management Science, 42:142–150, 1996.

58

[29] Dong X. Shaw and Albert P.M. Wagelmans. An algorithm for single-item capacitated lot sizing with piecewise linear production costs and general holding costs. Management Science, 44:831–838, 1998.

[30] Wilco van den Heuvel and Albert P.M. Wagelmans. An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem. Computers & Operations Research, 33:3583–3599, 2006.

[31] Yi Feng, Shaoxiang Chen, Arun Kumar, and Bing Lin. Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory in o(nlogn) time. Computers & Operations Research, 38:717–722, 2011.

[32] Jinwen Ou. Economic lot-sizing with constant capacity and concave inventory costs. Naval Research Logistics, 59:717–722, 2012.

[33] H.M. Wagner. Principles of Operations Research with Applications to Managerial Deci-sions: 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, Inc., 1975.

[34] Kenneth R. Baker. An analysis of terminal conditions in rolling schedules. European Journal of Operational Research, 7:355–361, 1981.

[35] Eiji Mizutani and Stuart Dreyfus. Stage-lookahead dynamic programming algorithms for stochastic problems with time-lagged control dynamics. IEEE IEEM, 2009.

[36] S. Dreyfus. An analytic solution of the warehouse problem. Operations Research, 1:99– 104, 1957.

[37] R. Bellman. On the Theory of Dynamic Programming – a Warehouse Problem. Manage-ment Science, 2(3):272–274, 1956.

[38] R. Bellman. Dynamic programming approach to optimal inventory processes with delay in delivery Naval Research Logistics, XVIII(4):399–403, 1960.

[39] H. M. Wagner. A postscript to “Dynamic problems in the theory of the firm” Naval Research Logistics Quarterly, 7(1):7–12, 1960.

[40] Eiji Mizutani and Brigitte Trista. On two new dynamic programming procedures com-parable to the Wagner-Whitin regeneration point type in dynamic lot sizing. unpublished, 2019.