Robust Non-Clairvoyant Scheduling with Classification Models

Excerpt

arXiv:2610.01343v1 Announce Type: new Abstract: We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by