Efficient approximation schemes for Economic Lot-Sizing in continuous time
(2016) Discrete Optimization — Vol. 20, n° 1, p. 23-39 (2016)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- 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 ( 1 ¿ 2 OPT K min log OPT 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 parameter ¿ that is significantly smaller than OPT / K min on instances of this type, and then to define an approximation scheme that executes O ( 1 ¿ 2 ¿ 2 log 2 ( OPT K min ) ) operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.
- Affiliations
Louvain School of Management Operations and Information
Citations
Telha Cornejo, C., & Van Vyve, M. (2016). Efficient approximation schemes for Economic Lot-Sizing in continuous time. Discrete Optimization, 20(1), 23-39. https://doi.org/10.1016/j.disopt.2016.02.001 (Original work published 2016)