This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ahuja, R. K. Articles by Hochbaum, D. S. Search for Related Content

TECHNICAL NOTE—Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time

Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Department of Industrial Engineering and Operations Research, and Haas School of Management, University of California, Berkeley, California 94720
ahuja{at}ufl.edu
hochbaum{at}ieor.berkeley.edu

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²) 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.

Subject classifications: inventory/production; lot sizing; production/scheduling; networks/graphs; flow algorithms.
History: Received March 2004; revision received July 2006; accepted July 2006.