Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems

NP-hard cases of the single-item capacitated lot-sizing problem have been t he topic of extensive research and continue to receive considerable attenti on. However. surprisingly few theoretical results have been published on ap proximation methods for these problems. To the best of our knowledge, until now no polynomial approximation method is known that produces solutions wi th a relative deviation from optimality that is bounded by a constant. In t his paper we show that such methods do exist by presenting an even stronger result: the existence of fully polynomial approximation schemes. The appro ximation scheme is first developed for a quite general model, which has con cave backlogging and production cost functions and arbitrary (monotone) hol ding cost functions. Subsequently we discuss important special cases of the model and extensions of the approximation scheme to even more general mode ls.