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

摘要

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(~(n4 ε2)+□) arithmetic operations and calls to an oracle computing the cost functions.