Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482006 | European Journal of Operational Research | 2008 | 13 Pages |
Abstract
We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Sergei Chubanov, Mikhail Y. Kovalyov, Erwin Pesch,