Efficient approximation schemes for Economic Lot-Sizing in continuous time

We consider a continuous-time variant of the classical Economic Lot-Sizing (ELS) problem. In this variant, the setup cost is a continuous function with lower bound Kmin>0, the demand and holding costs are integrable functions of time and arbitrary replenishment policies are allowed. Starting from the assumption that certain operations involving the setup and holding cost functions can be carried out efficiently, we show that this variant admits a simple approximation scheme based on dynamic programming: if the optimal cost of an instance is OPT, we can find a solution with cost at most (1+ϵ)OPT using no more than O(1ϵ2OPTKminlogOPTKmin) of these operations. We argue, however, that this algorithm could be improved on instances where the setup costs are generally “very large” compared with Kmin. This leads us to introduce a notion of input-size parameter σ that is significantly smaller than OPT/Kmin on instances of this type, and then to define an approximation scheme that executes O(1ϵ2σ2log2(OPTKmin)) operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.