On the on-line maintenance scheduling problem

Fahimeh Shamsaei, Claudio Telha, Mathieu Van Vyve*

*Autor correspondiente de este trabajo

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

1 Cita (Scopus)


A machine instantly serves requests but needs to undergo maintenance after serving a maximum of L requests. We want to maximize the number of requests served. In the on-line version, we prove that serving L requests before placing a maintenance is 0.5-competitive and is best possible for deterministic algorithms. We describe a 0.585-competitive randomized algorithm and show an upper bound of 2 L/ (3 L- 1). We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.

Idioma originalInglés
Páginas (desde-hasta)387-397
Número de páginas11
PublicaciónOptimization Letters
EstadoPublicada - 1 mar. 2018
Publicado de forma externa

Nota bibliográfica

Funding Information:
Acknowledgements Second author supported by FSR Incoming Post-doctoral Fellowship of the Catholic University of Louvain (UCL), funded by the French Community of Belgium. This text presents research results of the P7/36 PAI project COMEX, part of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister Office, Science Policy Programming. The scientific responsibility is assumed by the authors.

Publisher Copyright:
© 2017, Springer-Verlag GmbH Germany.


Profundice en los temas de investigación de 'On the on-line maintenance scheduling problem'. En conjunto forman una huella única.

Citar esto