Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case

Albert Wagelmans, Stan van Hoesel and Antoon Kolen
Additional contact information
Albert Wagelmans: Erasmus University, Rotterdam, The Netherlands
Stan van Hoesel: Erasmus University, Rotterdam, The Netherlands
Antoon Kolen: Limburg University, Maastricht, The Netherlands

Operations Research, 1992, vol. 40, issue 1-supplement-1, S145-S156

Abstract: We consider the n -period economic lot sizing problem, where the cost coefficients are not restricted in sign. In their seminal paper, H. M. Wagner and T. M. Whitin proposed an O ( n 2 ) algorithm for the special case of this problem, where the marginal production costs are equal in all periods and the unit holding costs are nonnegative. It is well known that their approach can also be used to solve the general problem, without affecting the complexity of the algorithm. In this paper, we present an algorithm to solve the economic lot sizing problem in O ( n log n ) time, and we show how the Wagner-Whitin case can even be solved in linear time. Our algorithm can easily be explained by a geometrical interpretation and the time bounds are obtained without the use of any complicated data structure. Furthermore, we show how Wagner and Whitin's and our algorithm are related to algorithms that solve the dual of the simple plant location formulation of the economic lot sizing problem.

Keywords: analysis of algorithms; computational complexity: economic lot sizing problem; dynamic programming; applications: economic lot sizing by dynamic programming; inventory/production: complexity of economic lot sizing (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (98)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S145 (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:40:y:1992:i:1-supplement-1:p:s145-s156

Access Statistics for this article

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