Robust Scheduling Against Machine Failures

Liu, Zhenwei; Zhang, Guochuan; Zhao, Yifan

doi:10.24963/ijcai.2026/687

Robust Scheduling Against Machine Failures

Zhenwei Liu, Guochuan Zhang, Yifan Zhao

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 6175-6182.

https://doi.org/10.24963/ijcai.2026/687

Keywords

Planning and Scheduling: Scheduling
Game Theory and Economic Paradigms: Noncooperative games
Agent-based and Multi-agent Systems: Resource allocation
Planning and Scheduling: Theoretical foundations of planning

Abstract

We study a robust scheduling problem on identical machines in which machines may fail after the initial assignment. The goal is to compute an initial schedule together with a recovery strategy that minimizes the post-failure makespan, under the constraint that jobs on available machines cannot be moved.

We consider two failure models: a strong adversary, which selects the failed machines, and a weak adversary, which selects only the number of failures. For up to k failures, we give algorithms with robustness ratios 1.618 for the strong adversary and 1.5 for the weak adversary. For the single-failure case, k = 1, we obtain best possible ratios 1.387 and 1.281, respectively, matching our lower bounds.

Zhenwei Liu, Guochuan Zhang, and Yifan Zhao. 2026. Robust Scheduling Against Machine Failures. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 6175–6182. https://doi.org/10.24963/ijcai.2026/687

@inproceedings{ijcai2026p687,
  title     = {Robust Scheduling Against Machine Failures},
  author    = {Liu, Zhenwei and Zhang, Guochuan and Zhao, Yifan},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {6175--6182},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/687},
  url       = {https://doi.org/10.24963/ijcai.2026/687},
}

TY  - CPAPER
TI  - Robust Scheduling Against Machine Failures
AU  - Liu, Zhenwei
AU  - Zhang, Guochuan
AU  - Zhao, Yifan
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 6175
EP  - 6182
DO  - 10.24963/ijcai.2026/687
UR  - https://doi.org/10.24963/ijcai.2026/687
ER  -