Robust Non-Clairvoyant Scheduling with Classification Models
We study non-clairvoyant single-machine scheduling to minimize the sum of completion times, a problem for which no constant-competitive algorithm is possible in the pure setting. The authors introduce a robustness framework that leverages a classifier's confusion matrix to partition jobs into predicted classes, characterizing uncertainty as internal permutations rather than numerical scenarios. This structural information yields an oblivious non-adaptive Min-Cost algorithm that is simultaneously optimal for multiple criteria, alongside new adaptive and randomized extensions.
The paper proposes a novel and theoretically clean framework that bridges machine-learning classifiers with robust scheduling. An oblivious non-adaptive algorithm (Min-Cost) is proven optimal for Min-Max and Min-Expectation and best deterministic for Min-Max Regret on binary classifiers, while separation results show that randomization and adaptivity help only under specific structural conditions. However, the guarantees rest on exact a priori knowledge of the confusion matrix—a limitation the authors candidly flag and explicitly shelve: ``we leave the analysis of inaccurate confusion matrices for future work.''
The strongest contribution is the crisp, simultaneous characterization of Min-Cost as an oblivious non-adaptive algorithm. The authors prove that Min-Cost is ``the best possible deterministic algorithm for the Min-Max and Min-Max Regret problems... and that it is the best possible non-adaptive algorithm for the Min-Expectation problem.'' The adversarial lower-bound argument (Lemma 3) and the exact analysis of the randomized Rand-Half algorithm (Theorem 5), which breaks the deterministic lower bound for confusion matrices with specific structure, are elegant and rigorous.
The primary limitation is the idealized knowledge model. Exact confusion-matrix knowledge ``may seem to be a strong assumption,'' and the paper evaluates only a perfect unsupervised estimator, leaving all noise analysis to future work; in practice, recent estimation methods still suffer calibration error under distributional shift. Second, the adaptive DP for Min-Expectation has complexity $O(K \cdot e_{\max}^{K^2})$, making it pseudo-polynomial and exponential in $K^2$, so it is impractical beyond tiny instances. Third, the $>4/3$ adaptivity gap uses degenerate instances with $\lambda_1 = 0$ and approaches $4/3$ as $K \to \infty$, limiting its practical force. Finally, the strongest positive results for randomization and adaptivity are confined to binary classifiers.
The theoretical evidence supports the formal claims: Lemma 1 identifies the worst-case scenario for Min-Max, Lemma 2 for Min-Max Regret, and Theorems 3 and 4 give matching upper and lower bounds for binary classifiers. The related-work discussion correctly contrasts the approach with learning-augmented algorithms, noting that a single-scalar error $\eta$ is ``too coarse to capture such structured prediction patterns.'' However, the paper provides no empirical validation and does not benchmark Min-Cost against a natural stochastic analogue such as SEPT, even though the confusion matrix gives exact per-queue marginals that make a stochastic baseline obvious.
Reproduction is possible in principle because the paper is self-contained with full proofs and appendices, but several practical barriers exist. No code or data is released. The adaptive DP (Theorem 6) is defined by the Bellman recurrence $f(E^{t}) = \min_{1 \leq k \leq K, |\mathcal{R}_{k}^{t}|>0} \Biggl\{\sum_{\ell=1}^{K}\frac{e_{k\ell}^{t}}{|\mathcal{R}_{k}^{t}|}\cdot\Bigl[n_{t}\lambda_{\ell}+f(E^{t}-\mathbf{e}^{k\ell})\Bigr]\Biggl\}$, yet implementing it requires enumerating a state space of size $O(e_{\max}^{K^2})$, which the authors note is only pseudo-polynomial for constant $K$. Verifying the Rand-Half probabilities requires re-deriving the lengthy three-case LP solution in Appendix B.
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 class~$k$ but that actually belong to class~$\ell$. 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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.