On the on-line maintenance scheduling problem

Shamsaei, Fahimeh;Telha, Claudio;Van Vyve, Mathieu
(2018) Optimization Letters — Vol. 12, n° 2, p. 387-397 (2018)

Files

Rep2978.pdf
  • Closed Access
  • Adobe PDF
  • 892.96 KB
Request a copy

Details

Authors
  • Shamsaei, FahimehUCLouvain
    Author
  • Telha, ClaudioUCLouvain
    Author
  • Van Vyve, Mathieuorcid-logoUCLouvain
    Author
Abstract
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 2L/(3L − 1). We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Shamsaei, F., Telha, C., & Van Vyve, M. (2018). On the on-line maintenance scheduling problem. Optimization Letters, 12(2), 387-397. https://doi.org/10.1007/s11590-017-1198-6 (Original work published 2018)