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

• 成果类型: Article
• 署名作者: Chubanov, S; Kovalyov, MY; Pesch, E
• 署名单位: Belarusian State University; Universitat Siegen; National Academy of Sciences of Belarus (NASB); United Institute of Informatics Problems of the National Academy of Sciences of Belarus
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0641-0
• 发表日期: 2006
• 页码: 453-466
• 关键词: Approximation; algorithms

摘要

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error epsilon in time polynomial in the problem size and in 1/epsilon. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.