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.
Figures & tables
Figure 1 : Confusion matrix of a binary classifier (2 classes). The entry on row i and column j indicates the number of items of class cj predicted as ci . The entries highlighted in red (first column) represent the 6 items actually in class c1 (among which 2 are correctly classified and 4 are misclassified in c2 ). Those highlighted in blue (second row) represent the 9 items classified as c2 (among which 4 are actually in c1 ).
Figure 2 : Examples of confusion matrices. (a) and (b) are both examples of clairvoyant classifiers. Although the classifier in (b) is wrong about the interpretation of the classes, the confusion matrix allows to infer the reality; for example, we immediately know that all the jobs labelled as class 2 are actually in class 1. (c) shows an example of a classifier that only over-estimates the jobs, and (d) is an example of a classifier that confuses class 1 and class 3 but is always correct for class 2. Finally, (e) shows a non-clairvoyant classifier.
Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include O(1)-competitive algorithms for single and unrelated parallel machines with only O(1) preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.
Mugen Blue, Sungjin Im, Alexander Lindermayr
University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.
Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by R∥Cmax. By using predictions of heavy job assignments, we achieve a polynomial-time (1+ε)-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.
Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos
The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Humans facing algorithmic decision systems have been found to ``game'' them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier's decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today's decisions influence tomorrow's costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.
Sura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh
Department of Integrated Systems Engineering, The Ohio State University, Ohio, USA · Department of Industrial Engineering, Jordan University of Science and Technology, Irbid, Jordan · Department of Electrical and Computer Engineering, University of California, San Diego, USA