Single-item lot-sizing with quantity discount and bounded inventory

In this paper, an efficient O ( n 2 ) algorithm is proposed to solve a special case of single-item lot-sizing problems (SILSP) in which both the production and holding costs are piecewise linear, there is an all-unit discount with one breakpoint for the production cost, and the inventory is bounded. The algorithm is based on a key structural property that may be of more general interest, that of a just-in-time ordering policy. Finally, we show that when the problem is extended to two items, it is NP-complete.