An Efficient Dynamic Programming Approach to Optimize Capacitated Lot-sizing Problem


1 Young Researchers and Elite Club, Qazvin Branch, Islamic Azad University, Qazvin, Iran

2 Department of Management and Soft Technologies, Malek Ashtar University of Technology, Tehran, Iran


In most industrial applications, determining production quantities are one of the most key decision making. In this paper, an integer mathematical programming model for lot-sizing problem with considering set-up time, safety stock, shortage cost, and different production manners, is presented. The objective is to minimize summation of production, set up, holding, and shortage costs. To solve the model, a forward dynamic programming (DP) approach is presented and compared with classical backward DP method. Finally, different numerical illustrations with different dimension are generated. The statistical analysis on computational results showed that the proposed DP approach is more applicable than the classical DP in terms of computational time.


Main Subjects

[1] Wagner, H. M. and Whitin, T.M. (1958). A dynamic version of the economic lit size model. Management Science, 5, 89-96.
[2] Evans, J.R. (1958). An Efficient Implementation of the Wagner-Whitin Algorithm for Dynamic Lot-Sizing. Journal of Operations Management, 5, 2, 229-235.
[3] Federgruen, A. and Tzur, M. (1991). 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, 37, 909-925.
[4] Wagelmans, A., Van Hoesel, S. and Kolen, A. (1992). Economic lot-sizing: An O (n log n) - algorithm that runs in linear time in the Wagner-Whitin case. Operations Research, 40, 145-156.
[5] Aggrawal, A. and Park, J.K. (1993). Improved algorithms for economic lot-size problem. Operations Research, 41, 549-571.
[6] Heady R.B. and Zhiwei, Z. (1994). An improved implementation of the wagner whitin algorithm. Production and operations management. Volume, 3, 55–63.
[7] Aryanezhad, M.B. (1992). An algorithm based on a new sufficient condition of optimality in dynamic lot size model. European Journal of Operational Research, 59, 425-433.
[8] Bitran, G.R., Magnanti, T.L. and Yanasse, H.H. (1984). Approximation methods for the uncapacitated dynamic lot size problem.  Management Science, 30, 1121-1140.
[9] Aryanezhad, M.B., Kiany, H. (1992). Dynamic lot sizing with backlogging. Iranian Journal of Science & Technology, 16, 43-56.                                                      
[10] Basnet, C. and Leung, J.M.Y. (2005). Inventory lot-sizing with supplier selection. Computers and Operations Research, 32, 1–14.
[11]Li, Y., Chen, J. and Cai, X. (2007). Heuristic genetic algorithm for capacitated production planning problems with batch processing and remanufacturing. International Journal of Production Economics, 105, 301–317.
[12] Pan, Z., Tang, J. and Liu, O. (2009). Capacitated dynamic lot sizing problems in closed- loop supply chain. European Journal of Operational Research, 198, 810–821.
[13] Absi, N. and Kedad-Sidhoum, S. (2009). The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs. Computer and Operations Research, 36, 2926–2936.
Volume 6, Issue 1
April 2016
Pages 89-102
  • Receive Date: 10 November 2014
  • Revise Date: 26 April 2016
  • Accept Date: 08 September 2016
  • First Publish Date: 08 September 2016