The practical running time of some lot-sizing algorithms

In this paper we consider both the uncapacitated and the capacitated economic lot-sizing model, in which demand is a deterministic function of the price. We use a constant price for all periods. Van den Heuvel and Wagelmans [2006] propose an exact algorithm to determine the optimal price and lot-sizing decisions, using an heuristic algorithm from Kunreuther and Schrage [1973]. They propose a theorem on the maximum number of breakpoints dependent on T. However, the proof contains a flaw discovered by the authors themselves. Geunes et al. [2009] apply the algorithm and results from Van den Heuvel and Wagelmans [2006] on the capacitated variant, but with the flaw in the proof it is uncertain whether their results still hold. The goal of this paper is to determine whether the flaw in the proof has effect on the proposed theorem and the obtained results. First, we will try to disprove the theorem by looking for a contradicting result. After which we will look at whether the flaw has any effect on the results of Geunes et al. [2009]