Economic lot sizing: An O(nlogn) algorithm that runs in linear time in the Wagner-Whitin case

Economic lot sizing: An O(nlogn) algorithm that runs in linear time in the Wagner-Whitin case

0.00 Avg rating0 Votes
Article ID: iaor19921697
Country: United States
Volume: 40
Start Page Number: 11
End Page Number: 22
Publication Date: Jan 1992
Journal: Operations Research
Authors: , ,
Keywords: programming: dynamic
Abstract:

The authors 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(n2) 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, the authors present an algorithm to solve the economic lot sizing problem in O(nlogn) time, and they show how the Wagner-Whitin case can even be solved in linear time. The present algorithm can easily be explained by a geometrical interpretation and the time bounds are obtained without the use of any complicated data structure. Furthermore, the authors show how Wagner and Whitin’s and the present algorithm are related to algorithms that solve the dual of the simple plant location formulation of the economic lot sizing problem.

Reviews

Required fields are marked *. Your email address will not be published.