Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations for which tight storage capacity and high fixed cost of specialized storage are critical. Here we present an O(n^2) dynamic programming algorithm for the lot-sizing problem with inventory bounds and fixed costs, where n is the number of time periods. The algorithm operates on a hierarchy of two layers of value functions to solve the problem efficiently. It improves the complexity bound of the classic O(n^3) algorithm of Love (1973) for lot sizing with concave cost and bounded inventory.
Citation
Appeared in Operations Research Letters. Check http://www.ieor.berkeley.edu/~atamturk/