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

Chi To Ng, Mikhail Y. Kovalyov, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)621-624
Number of pages4
JournalEuropean Journal of Operational Research
Volume200
Issue number2
DOIs
Publication statusPublished - 16 Jan 2010

Keywords

  • Capacitated economic lot-sizing problem
  • Fully polynomial time approximation scheme

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this