2008/02/01 by Ravindra K. Ahuja, Dorit S. Hochbaum · 2 citations
Business, Management and Accounting · Computer Science · Decision Sciences · #Supply Chain and Inventory Management #Optimization and Search Problems #Auction Theory and Applications
paper · doi:10.1287/opre.1070.0508
openalex publication_date 2008/02/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/06/11
In this paper, we study capacitated dynamic lot-sizing problems with or without backorders, under the assumption that production costs are linear, that is, there are no setup costs. These two dynamic lot-sizing problems (with or without backorders) are minimum-cost flow problems on an underlying network that possess a special structure. We show how the well-known successive shortest-path algorithm for the minimum-cost flow problem can be used to solve these problems in O(n 2 ) time, where n is the number of periods in the dynamic lot-sizing problems, and how, with the use of dynamic trees, we can solve these problems in O(n log n) time. Our algorithm also extends to the dynamic lot-sizing problem with integer variables and convex production costs with running time O(n log n log U), where U is the largest demand value.