Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
复制标题
DOI：
10.1287/opre.40.1.s145
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
A. Wagelmans;S. Hoesel;A. Kolen
中科院分区：
文献类型：
--
作者：
A. Wagelmans;S. Hoesel;A. Kolen
考虑成本系数不受符号限制的n周期经济批量问题。在他们的开创性论文中，H. M. Wagner和T. M. whtin提出了一个O（n2）算法来解决这个问题的特殊情况，其中边际生产成本在所有时期都是相等的，并且单位持有成本是非负的。众所周知，他们的方法也可以用来解决一般问题，而不影响算法的复杂性。本文给出了一种在O（n log n）时间内解决经济批量问题的算法，并证明了wagner - whtin情况甚至可以在线性时间内解决。我们的算法可以很容易地用几何解释来解释，并且不需要使用任何复杂的数据结构就可以得到时间边界。此外，我们还展示了Wagner和whtin的算法以及我们的算法如何与解决经济批量问题的简单工厂选址公式的对偶算法相关联。
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(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, 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.