Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems
Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems
复制标题
DOI：
10.1287/moor.26.2.339.10552
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
S. Hoesel;A. Wagelmans
中科院分区：
文献类型：
--
作者：
S. Hoesel;A. Wagelmans
单件有能力批量问题的NP-Hard情形一直是人们广泛研究的主题，并继续受到相当大的关注。然而，令人惊讶的是，关于这些问题的近似方法的理论结果却很少发表。就我们所知，到目前为止，还没有一种多项式近似方法能产生与最优性相对偏差的解，该解由一个常数限定。在本文中，我们通过给出一个更强的结果：完全多项式逼近格式的存在性，证明了这种方法确实存在。首先给出了一个非常一般的模型的近似格式，该模型具有凹形的缺货和生产成本函数，以及任意的(单调)保持成本函数。随后，我们讨论了模型的重要特例以及近似格式对更一般模型的推广。
NP-hard cases of the single-item capacitated lot-sizing problem have been the topic of extensive research and continue to receive considerable attention. However, surprisingly few theoretical results have been published on approximation methods for these problems. To the best of our knowledge, until now no polynomial approximation method is known which produces solutions with a relative deviation from optimality that is bounded by a constant. In this paper we show that such methods do exist, by presenting an even stronger result: the existence of fully polynomial approximation schemes. The approximation scheme is first developed for a quite general model, which has concave backlogging and production cost functions and arbitrary (monotone) holding cost functions. Subsequently we discuss important special cases of the model and extensions of the approximation scheme to even more general models.