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.
Nota bibliográficaFunding 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.
© 2017, Springer-Verlag GmbH Germany.