Efficient approximation algorithms for the economic lot-sizing in continuous time

We consider a continuous-time variant of the classical Economic Lot-Sizing (ELS) problem. In this model, the setup cost is a continuous function with lower bound $K_min > 0$, the demand and holding costs are integrable functions of time and the replenishment decisions are not restricted to be multiples of a base period. Starting from the assumption that certain operations involving the setup and holding cost functions can be carried out efficiently, we argue 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\over ε^2} {OPT \over K_min} log {OPT \over K_min}$ 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 σ that is significantly smaller than $OPT/K_min$ on instances of this type, and then to define an approximation scheme that executes $O({1\over ε^2}σ^2 ({OPT \over K_min}))$ operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.