Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5128383 | Operations Research Letters | 2017 | 5 Pages |
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(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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jinwen Ou,