AN O(T-3) ALGORITHM FOR THE ECONOMIC LOT-SIZING PROBLEM WITH CONSTANTCAPACITIES

We develop an algorithm that solves the constant capacities economic l ot-sizing problem with concave production costs and linear holding cos ts in O(T-3) time. The algorithm is based on the standard dynamic prog ramming approach which requires the computation of the minimal costs f or 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 algorith m.