On the complexity of a maintenance problem for hierarchical systems

Andreas S. Schulz; Claudio Telha

doi:10.1016/j.orl.2024.107117

On the complexity of a maintenance problem for hierarchical systems

Andreas S. Schulz, Claudio Telha^*

^*Corresponding author for this work

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

Abstract

We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Levi et al. 2014).

Original language	English
Article number	107117
Journal	Operations Research Letters
Volume	54
DOIs	https://doi.org/10.1016/j.orl.2024.107117
State	Published - May 2024

Bibliographical note

Publisher Copyright:
© 2024 Elsevier B.V.

Keywords

Computational complexity
Integer-factorization
Maintenance scheduling

Access to Document

10.1016/j.orl.2024.107117

Cite this

@article{28942746697c4e4992828d9da012f72c,

title = "On the complexity of a maintenance problem for hierarchical systems",

abstract = "We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Levi et al. 2014).",

keywords = "Computational complexity, Integer-factorization, Maintenance scheduling",

author = "Schulz, \{Andreas S.\} and Claudio Telha",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = may,

doi = "10.1016/j.orl.2024.107117",

language = "English",

volume = "54",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the complexity of a maintenance problem for hierarchical systems

AU - Schulz, Andreas S.

AU - Telha, Claudio

PY - 2024/5

Y1 - 2024/5

N2 - We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Levi et al. 2014).

AB - We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Levi et al. 2014).

KW - Computational complexity

KW - Integer-factorization

KW - Maintenance scheduling

UR - https://www.scopus.com/pages/publications/85192973104

U2 - 10.1016/j.orl.2024.107117

DO - 10.1016/j.orl.2024.107117

M3 - Article

AN - SCOPUS:85192973104

SN - 0167-6377

VL - 54

JO - Operations Research Letters

JF - Operations Research Letters

M1 - 107117

ER -

On the complexity of a maintenance problem for hierarchical systems

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this