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 K_min>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(Formula presented.) of these operations. We argue, however, that this algorithm could be improved on instances where the setup costs are generally "very large" compared with K_min. This leads us to introduce a notion of input-size parameter σ that is significantly smaller than OPT/K_min on instances of this type, and then to define an approximation scheme that executes O(Formula presented.)) operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.