A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure

The single-item capacitated economic lot-sizing (CELS) problem is a fundamental problem of production and inventory management. The first fully polynomial approximation scheme (FPTAS) for this problem with concave cost functions was developed by Van Hoesel and Wagelmans [C.P.M. Van Hoesel, A.P.M. Wagelmans, Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems, Mathematics of Operations Research 26 (2001) 339-357]. Chubanov et al. [S. Chubanov, M.Y. Kovalyov, E. Pesch, An FPTAS for a single-item capacitated economic lot-sizing problem, Mathematical Programming Series A 106 (2006) 453-466] later presented a sophisticated FPTAS for the general case of the CELS problem with a monotone cost structure. In this paper, we present a better FPTAS for this case. The ideas and presentation of our FPTAS are simple and straightforward. Its running time is about frac(n4, ε2) times faster than that of Chubanov et al. [5], where n is the number of production periods and ε is the anticipated relative error of the approximate solution.