---
title: "Robust Scheduling Against Machine Failures"
authors:
  - "Zhenwei Liu"
  - "Guochuan Zhang"
  - "Yifan Zhao"
doi: "10.24963/ijcai.2026/687"
url: "https://ijcai.org/proceedings/2026/687"
pdf: "https://ijcai.org/proceedings/2026/0687.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "6175-6182"
track: "Main Track"
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"
---

# Robust Scheduling Against Machine Failures

Zhenwei Liu, Guochuan Zhang, Yifan Zhao

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 6175-6182. DOI: [10.24963/ijcai.2026/687](https://doi.org/10.24963/ijcai.2026/687)

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