|
|||||
|
|
An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure |
|
| Authors: | Sergei Chubanov Mikhail Y. Kovalyov Erwin Pesch |
| Affiliation: | (1) Faculty of Economics, Belarus State University and the Institute of Information Systems at the University of Siegen, Germany;(2) Faculty of Economics, Belarus State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Skorini 4, 220050 Minsk, Belarus;(3) Institute of Information Systems at the University of Siegen, , Germany |
| Abstract: | 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 ɛ in time polynomial in the problem size and in 1/ɛ. 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. |
| Keywords: | Capacitated economic lot-sizing problem Dynamic programming Fully polynomial time approximation scheme |
| 本文献已被 SpringerLink 等数据库收录！ | |