On setup cost reduction in the economic lot-sizing model without speculative motives

An important special case of the economic lot-sizing problem is the one in which there are no speculative motives to hold inventory, i.e., the marginal cost of producing one unit in some period plus the cost of holding it until some future period is at least the marginal production cost in the latter period. It is already known that this special case can be solved in linear time. In this paper we study the effects of reducing all setup costs by the same amount. It turns out that the optimal solution changes in a very structured way. This fact will be used to develop faster algorithms for several problems that can be reformulated as parametric lot-sizing problems. One result, worth a separate mention, is an algorithm for the so-called dynamic lot-sizing problem with learning effects in setups. This algorithm has a complexity that is of the same order as the fastest algorithm known so far, but it is valid for a more general class of models than usually considered.