On the on-line maintenance scheduling problem |
| |
Authors: | Fahimeh Shamsaei Claudio Telha Mathieu Van Vyve |
| |
Institution: | 1.Center for Operations Research and Econometrics,Université Catholique de Louvain,Louvain-la-Neuve,Belgium |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |