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

Ravindra K. Ahuja () and Dorit S. Hochbaum ()
Additional contact information
Ravindra K. Ahuja: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Dorit S. Hochbaum: Department of Industrial Engineering and Operations Research, and Haas School of Management, University of California, Berkeley, California 94720

Operations Research, 2008, vol. 56, issue 1, 255-261

Abstract: 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.

Keywords: inventory/production; lot sizing; production/scheduling; networks/graphs; flow algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0508 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:56:y:2008:i:1:p:255-261

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().