On the on-line maintenance scheduling problem

Fahimeh Shamsaei; Claudio Telha; Mathieu Van Vyve

doi:10.1007/s11590-017-1198-6

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 revista › Artículo › revisión exhaustiva

2 Citas (Scopus)

Resumen

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 original	Inglés
Páginas (desde-hasta)	387-397
Número de páginas	11
Publicación	Optimization Letters
Volumen	12
N.º	2
DOI	https://doi.org/10.1007/s11590-017-1198-6
Estado	Publicada - 1 mar. 2018
Publicado de forma externa	Sí

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.

Acceder al documento

10.1007/s11590-017-1198-6

Otros archivos y enlaces

Enlace a la publicación en Scopus

Citar esto

@article{234f67efe5b84cb38e238bd8d00925e0,

title = "On the on-line maintenance scheduling problem",

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 2 L/ (3 L- 1). We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.",

keywords = "Competitive analysis, Maintenance scheduling, Randomized algorithms",

author = "Fahimeh Shamsaei and Claudio Telha and {Van Vyve}, Mathieu",

note = "Publisher Copyright: {\textcopyright} 2017, Springer-Verlag GmbH Germany.",

year = "2018",

month = mar,

day = "1",

doi = "10.1007/s11590-017-1198-6",

language = "English",

volume = "12",

pages = "387--397",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - On the on-line maintenance scheduling problem

AU - Shamsaei, Fahimeh

AU - Telha, Claudio

AU - Van Vyve, Mathieu

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

KW - Competitive analysis

KW - Maintenance scheduling

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85037972054&partnerID=8YFLogxK

U2 - 10.1007/s11590-017-1198-6

DO - 10.1007/s11590-017-1198-6

M3 - Article

AN - SCOPUS:85037972054

SN - 1862-4472

VL - 12

SP - 387

EP - 397

JO - Optimization Letters

JF - Optimization Letters

IS - 2

ER -

On the on-line maintenance scheduling problem

Resumen

Nota bibliográfica

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto