A polynomial time algorithm to the economic lot sizing problem with constant capacity and piecewise linear concave costs

It is well-known that the classical economic lot-sizing problem with constant capacity and general concave ordering/inventory cost functions can be solved in O(T4) time (Florian and Klein, 1971). We show that the problem can be solved in O(mT3) time when the ordering cost functions are piecewise linear concave and have m line segments with different slopes in a time period in average. Our algorithm makes use of the data structure of range minimum query (RMQ).