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^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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.

Original language	English
Pages (from-to)	387-397
Number of pages	11
Journal	Optimization Letters
Volume	12
Issue number	2
DOIs	https://doi.org/10.1007/s11590-017-1198-6
State	Published - 1 Mar 2018
Externally published	Yes

Bibliographical note

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

Keywords

Competitive analysis
Maintenance scheduling
Randomized algorithms

Access to Document

10.1007/s11590-017-1198-6

Cite this

@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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this