Efficient approximation schemes for Economic Lot-Sizing in continuous time

Claudio Telha, Mathieu Van Vyve*

*Autor correspondiente de este trabajo

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

2 Citas (Scopus)

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 originalInglés
Páginas (desde-hasta)23-39
Número de páginas17
PublicaciónDiscrete Optimization
Volumen20
DOI
EstadoPublicada - may. 2016
Publicado de forma externa

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.

Huella

Profundice en los temas de investigación de 'Efficient approximation schemes for Economic Lot-Sizing in continuous time'. En conjunto forman una huella única.

Citar esto