CS Paper Radar

Pareto-optimal Non-Clairvoyant Scheduling with Predictions

Ziyad Benomar, Vianney Perchet

cs.DS cs.GT ·submitted 2026-10-23 11:26 UTC · v2
theory

Abstract

We study preemptive single-machine non-clairvoyant scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\varepsilon$ is achievable with robustness $\varepsilon^{-1/2}+\frac16+O(\sqrt\varepsilon)$, whereas all previous algorithms required robustness $Θ(1/\varepsilon)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions. Furthermore, we give a simple randomized algorithm, using predicted sizes, with consistency $1+\varepsilon$ and robustness $(3\varepsilon)^{-1/2}+O(1)$, strictly below the deterministic frontier. The question of determining the Pareto-optimal frontier among randomized algorithms remains open.

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling

cs.DS ·2026-10-21 ·Sizhe Li, Nicolas Christianson, Tongxin Li
theory similarity 0.79
Abstract

We study the problem of characterizing the optimal consistency--robustness tradeoff for single-machine non-clairvoyant scheduling with predicted processing times. For a fixed number of jobs $n$, Wei and Zhang (2020) established a lower bound on the achievable consistency--robustness tradeoff which is known to be tight only in a few restrictive cases, leaving the optimal tradeoff for general $n$ unresolved. A different worst-case-$n$ regime was introduced by Benomar et al. (2025), who applied the former work's construction to show that for $λ\in (0, 1)$, any $(1+λ)$-consistent algorithm must be $1 + Ω(\sqrt{1/λ})$-robust. On the other hand, the best known upper bound gives $(1+λ)$-consistency and $1+O(1/λ)$-robustness, leaving a polynomial gap. In this work, we develop a new lower bound using a multi-stage adversarial construction and a new algorithm that together give a near-optimal characterization of the consistency--robustness tradeoff: for every $n$, our upper bound is within a multiplicative factor $3/2$ of our lower bound, and thus our algorithm is within a multiplicative factor $3/2$ of the online optimal. In particular, our lower bound shows that any $(1+λ)$-consistent algorithm must have robustness at least $1/\sqrtλ$ as $n \to \infty$, while our algorithm achieves robustness at most $\frac{1}{2}+\sqrt{\frac{5}{4}+1/λ}$ for any $n$, matching the lower bound in the leading term as $λ\downarrow 0$; our upper bound also closes the polynomial gap in the worst-case-$n$ regime. We additionally show how our algorithm can be made error-tolerant, preserving the near-optimal consistency-robustness tradeoff while incurring only slightly degraded performance under bounded prediction errors.

0.45

Robust Non-Clairvoyant Scheduling with Classification Models

cs.LG cs.DS ·2026-10-01 ·Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli
similarity 0.74
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 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.

0.43

Consistency-Robustness Tradeoffs for Strategyproof Scheduling with Predictions

cs.GT ·2026-09-12 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.67
Abstract

We study strategyproof scheduling on \(n\) unrelated machines with predictions. Each machine is controlled by an agent with privately known processing times, while the mechanism receives a public prediction of the processing-time matrix before the agents report. The objective is to minimize the makespan subject to strategyproofness. We measure performance by consistency, the approximation guarantee for correct predictions, and robustness, the worst-case guarantee for arbitrary predictions. We introduce \textsc{EdgeSkip}, a deterministic strategyproof member of the class of job-wise weighted mechanisms. Such mechanisms allocate each job independently using prediction-dependent weights. Using a polynomial-time \(2\)-approximate reference schedule computed from the prediction and a standard tradeoff parameter, \textsc{EdgeSkip} is \(4\)-consistent and \((2n-2)\)-robust, improving on the \((6,2n)\) guarantee of Balkanski, Gkatzelis, and Tan. Without computational restrictions, \textsc{EdgeSkip} with an optimal reference schedule is \(C\)-consistent and \(\max\{n,(n-1)C/(C-1)\}\)-robust for every \(C>1\). We prove a matching information-theoretic lower bound for all job-wise weighted mechanisms, thereby determining the exact consistency--robustness tradeoff for this class. For arbitrary deterministic strategyproof mechanisms, we establish the robustness lower bound \(\max\{n,C/(C-1)\}\) for every \(C>1\). We also study an error-tolerant variant and improve upon prior guarantees. Experiments demonstrate that our mechanisms achieve good empirical performance.

0.36

What to Predict for Efficient Scheduling on Parallel Machines

cs.DS ·2026-11-10 ·Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Giorgos Mitropoulos, Michalis Xefteris
top venue similarity 0.65
Abstract · Accepted at NeurIPS 2026

We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time. We assume that the algorithm has access to noisy information (the prediction) about an optimal solution, expressed through a solution encoding that implicitly quantifies both the amount of information provided and the nature of noise (errors in the prediction). Our central question is to determine the maximum level of noise that still allows for efficiently recovering this optimal solution. We observe that information guiding greedy scheduling to optimality or revealing the optimal assignment of tasks to machines is very sensitive to noise, and prove that recovering an optimal solution from solution encodings capturing either is computationally hard, even for a small (non-constant) number of errors. On the positive side, we show that an order-based encoding, which leads to errors that are dispersed locally, is robust to noise. We present a dynamic programming framework that utilizes this encoding and solves optimally several classical scheduling problems, including makespan and total weighted completion time minimization on identical or unrelated machines.

0.36

Non-Clairvoyant Scheduling is Hard Even for Trees

cs.DS ·2026-10-07 ·Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao
theory similarity 0.64
Abstract

We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $Ω(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $Ω(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $Ω(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $Ω(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.

0.34

Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff

cs.DS cs.LG ·2026-10-27 ·Zhong Han
theory similarity 0.63
Abstract · 45 pages, 4 figures. Streamlined appendix and clarified proof sketches and advice diagnostics. Includes ancillary evidence tables. Extended …

We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency under finite strict robustness is $d=(3+\sqrt5)/2$ when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above $d$ at every robustness budget below $4\varphi+3\approx9.472$, whereas our deterministic algorithm attains $d$ with exact robustness $\varphi^5\approx11.090$, where $\varphi=(1+\sqrt5)/2$. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. Tuning the replacement costs and both special thresholds gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including $(C,R)=(25/9,10)$ and $(4,7)$. Randomization permits expected consistency approaching one with finite expected robustness, whereas almost-sure robustness forces expected consistency strictly above two at every finite budget.

0.20

Speed-Robust Scheduling for Total Completion Time

cs.DS cs.DM ·2026-11-16 ·Moritz Buchem, Nicole Megow, Morten Weber
similarity 0.63
Abstract

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into $M$ bags before an adversary reveals the speeds of at most $M$ machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~$13/12$, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between $31/30\approx1.0333$ and $28/27\approx1.0370$, well below the optimal makespan factor of about $1.2071$. General speeds make the problem strictly harder: no deterministic algorithm is better than $1.2669$-robust, already for infinitesimally small jobs. We give a $25/16$-robust algorithm for arbitrary processing times and improve the guarantee to $1681/1152\approx1.4592$ for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

0.18

Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs

cs.DS math.OC ·2026-08-13 ·Tianhang Lu
theory similarity 0.61
Abstract

We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location $y$ clears all pending requests in $[0,y]$ at cost $y$. In the classical adversarial setting, we propose an $e$-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus $e$ is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter $λ\in(0,1]$, our deterministic learning-augmented algorithm is $(1+3/λ)$-robust and $(1+3λ)$-consistent. We also propose a randomized learning-augmented algorithm that is $(e+e/λ)$-robust and $(e-1+λ)$-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.

0.04