An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand

作者：Chubanov Sergei^*; Pesch Erwin

来源：Operations Research Letters, 2012, 40(6): 445-449.

DOI：10.1016/j.orl.2012.08.011

• Dynamic programming
• Approximation scheme
• Lot-sizing

We present a fully polynomial time approximation scheme (FPTAS) for the single-item capacitated economic lot-sizing problem with an objective function of a general form. The demand values may be negative, i.e., they may represent supply. For n time periods, the FPTAS runs in O (n(4)/epsilon(2) + ...) arithmetic operations and calls to an oracle computing the cost functions.

• 出版日期2012-11