# Robust Non-Clairvoyant Scheduling with Classification Models

arXiv: https://arxiv.org/abs/2610.01343 · HTML: https://mlsanity.com/paper/2610.01343/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Builds on (most cited first, 14 of 14)

- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Estimating Model Performance Under Covariate Shift Without Labels](https://mlsanity.com/paper/2401.08348/) (2024)
- [Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems](https://mlsanity.com/paper/2502.00841/) (2025)
- [An Adversarial Model for Scheduling with Testing](https://mlsanity.com/paper/1709.02592/) (2017)
- [Non-Clairvoyant Scheduling with Progress Bars](https://mlsanity.com/paper/2509.19662/) (2025)
- [Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2211.02044/) (2022)
- [Performance Estimation in Binary Classification Using Calibrated Confidence](https://mlsanity.com/paper/2505.05295/) (2025)
- [Single machine scheduling problems with uncertain parameters and the OWA criterion](https://mlsanity.com/paper/1405.5371/) (2014)
- [Scheduling with a processing time oracle](https://mlsanity.com/paper/2005.03394/) (2020)

## Abstract (arXiv)

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 a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry (k,ℓ) indicates the number of jobs predicted to belong to class~k but that actually belong to class~ℓ. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.