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

摘要

Abstract 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 ( T 4 ) time (Florian and Klein, 1971). We show that the problem can be solved in O ( m T 3 ) time when the ordering cost functions are piecewise linear concave and have