An O(T3) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
提出一个O(T³)算法，解决具有凹生产成本和线性持有成本的常数容量经济批量问题，比现有O(T⁴)算法更高效。
We develop an algorithm that solves the constant capacities economic lot-sizing problem with concave production costs and linear holding in O(T 3 ) time. The algorithm is based on the standard dynamic programming approach which requires the computation of the minimal costs for all possible subplans of the production plan. Instead of computing these costs in a straightforward manner, we use structural properties of optimal subplans to arrive at a more efficient implementation. Our algorithm improves upon the O(T 4 ) running time of an earlier algorithm.