Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23913
Title: A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure
Authors: Ng, CT 
Kovalyov, MY
Cheng, TCE 
Keywords: Capacitated economic lot-sizing problem
Fully polynomial time approximation scheme
Issue Date: 2010
Publisher: Elsevier
Source: European journal of operational research, 2010, v. 200, no. 2, p. 621-624 How to cite?
Journal: European journal of operational research 
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.
URI: http://hdl.handle.net/10397/23913
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2009.01.040
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
Citations as of Jul 28, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Aug 22, 2017

Page view(s)

58
Last Week
1
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.