On the on-line maintenance scheduling problem

Fahimeh Shamsaei, Claudio Telha, Mathieu Van Vyve*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish
Pages (from-to)387-397
Number of pages11
JournalOptimization Letters
Issue number2
StatePublished - 1 Mar 2018
Externally publishedYes

Bibliographical note

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


  • Competitive analysis
  • Maintenance scheduling
  • Randomized algorithms


Dive into the research topics of 'On the on-line maintenance scheduling problem'. Together they form a unique fingerprint.

Cite this