Robust Scheduling Against Machine Failures
Robust Scheduling Against Machine Failures
Zhenwei Liu, Guochuan Zhang, Yifan Zhao
Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 6175-6182.
https://doi.org/10.24963/ijcai.2026/687
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.
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
