IJCAI 20260 citations
Robust Scheduling Against Machine Failures
Zhenwei Liu, Guochuan Zhang, Yifan Zhao
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.
Planning and Scheduling: SchedulingGame Theory and Economic Paradigms: Noncooperative gamesAgent-based and Multi-agent Systems: Resource allocationPlanning and Scheduling: Theoretical foundations of planning
BibTeX
@inproceedings{ijcai2026_robustscheduling,
title = {Robust Scheduling Against Machine Failures},
author = {Zhenwei Liu and Guochuan Zhang and Yifan Zhao},
booktitle = {IJCAI 2026},
year = {2026}
}