Robust Non-Clairvoyant Scheduling with Classification Models

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 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,ell) indicates the number of jobs predicted to belong to classk but that actually belong to classell. 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.

Related

• Can we trust our models? Epistemic calibration in second-order classification
• Simulating Classification Models for Ex-Ante Evaluation of Predict-Then-Optimize Methods
• Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

Source: arXiv cs.LG | 2026-10-02