Name
Title | ||
|---|---|---|
Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems |
Abstract | ||
|---|---|---|
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 that 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1287/moor.26.2.339.10552 | Mathematics of Operations Research |
Keywords | Field | DocType |
general model,polynomial approximation schemes,polynomial approximation method,approximation scheme,np-hard case,polynomial approximation scheme,considerable attention,concave backlogging,cost function,approximation method,single-item capacitated economic lot-sizing,production cost function | Applied mathematics,Approximation algorithm,Mathematical economics,Polynomial,Holding cost,Production cost,Sizing,Mathematics,Monotone polygon,Polynomial-time approximation scheme,Bounded function | Journal |
Volume | Issue | ISSN |
26 | 2 | 0364-765X |
Citations | PageRank | References |
37 | 3.01 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. P. M. Van Hoesel | 1 | 93 | 8.07 |
| A. P. M. Wagelmans | 2 | 53 | 4.83 |