Resumen
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(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 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(Formula presented.)) operations. Besides dynamic programming, this second approximation scheme builds on a novel algorithmic approach for Economic Lot Sizing problems.
Idioma original | Inglés |
---|---|
Páginas (desde-hasta) | 23-39 |
Número de páginas | 17 |
Publicación | Discrete Optimization |
Volumen | 20 |
DOI | |
Estado | Publicada - may. 2016 |
Publicado de forma externa | Sí |
Nota bibliográfica
Funding Information:We are extremely grateful to the referees for their extensive comments that substantially improved the quality of the paper, and especially for pointing out to us the work of Denardo et al. [7] . The first author was supported by FSR Incoming Post-doctoral Fellowship of the Catholic University of Louvain (UCL), funded by the French Community of Belgium. This text presents the second author’s research results of the Belgian Program on Interuniversity Poles of Attraction P7/36 initiated by the Belgian State, Prime Minister Office, Science Policy Programming. The second author was also supported by MINO project from the Marie-Curie ITN programme, and COST project Td1207, both funded by the EU. The scientific responsibility is assumed by the authors.
Publisher Copyright:
© 2016 Elsevier B.V. All rights reserved.