Research map / Bandits and online learning / Online convex optimization and games
Non-clairvoyant Scheduling with Partial Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies non-clairvoyant scheduling when predictions are available for only B of n job sizes, giving near-optimal lower bounds and algorithms for perfect predictions and a learning-augmented algorithm with robustness, consistency and smoothness, revealing a consistency-smoothness tradeoff.
Problem
Preemptive single-machine scheduling to minimize total completion time when the algorithm is non-clairvoyant but has predictions (perfect or imperfect) for only B of the n job sizes.
Approach
Extends learning-augmented non-clairvoyant scheduling to partial predictions: a Switch algorithm alternates round-robin over unpredicted jobs with shortest-predicted-job-first using breakpoints; randomized breakpoints xi*y (xi shifted exponential) yield smoothness, and mixing with round-robin gives robustness. Also gives improved lower bounds via heavy-tailed distributions.
Key results
- For perfect predictions, Switch achieves (n,B)-competitive ratio 2 - B/n - 2(1-B/n)/(n+1), and CRRR achieves ratio between 2 - B/n - 2(1-B/n)/((n+1)(B+1)) and 2 - B/n, improving on the prior 2 - B(B-1)/(n(n-1)).
- Lower bound on the competitive ratio of any algorithm with B = wn + o(n) is 2 - w - (3 - 2*sqrt(2)) w(1-w), improving the earlier 2 - w - (4/e - 1) w(1-w).
- The preferential algorithm ALG_lambda has ratio at most min(2/(1-lambda), C/lambda + S/lambda * n E[eta]/OPT), with C = (2 - B/n) + rho(B/n)(1-(B-1)/(n-1)) and S = (4/rho)(1-B/n) + B/n, exhibiting a consistency-smoothness tradeoff in rho.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact job sizes as Switch breakpoints instead of only their relative order | Switch and CRRR · Single-machine scheduling, finite n and B | competitive ratio: 2 - \frac{B}{n} - \frac{2(1 - \frac{B}{n})}{n+1} vs. 2 - \frac{B}{n} | Helped |
| Randomize between RTC and Switch with the stated probability (ablation) | Switch with exact-size breakpoints · Single-machine scheduling, perfect predictions | competitive ratio: 2 - \frac{B}{n} - \frac{2(1 - \frac{B}{n})(2 - \frac{B}{n})}{n+3 - \frac{2B}{n}} | Helped |
| Use the known jobs' relative order rather than their exact sizes | CRRR · Single-machine scheduling, perfect predictions | competitive ratio: 2 - \frac{B}{n} vs. 2 - \frac{B(B-1)}{n(n-1)} | Helped |
| Set B to 0 (ablation) | Randomized RTC/Switch · Single-machine scheduling | competitive ratio: 2 - \frac{4}{n+3} | Helped |
| Use randomized breakpoints ξy with ξ ~ 1 + E(1/ρ) instead of breakpoints equal to the predictions (ablation) | Switch · Single-machine scheduling, imperfect predictions | smoothness to prediction error | Helped |
| Set ρ closer to zero (ablation) | Switch with randomized breakpoints · Single-machine scheduling, imperfect predictions | consistency | Helped |
| Set ρ closer to zero (ablation) | Switch with randomized breakpoints · Single-machine scheduling, imperfect predictions | sensitivity to prediction error | Hurt |
| Set ρ closer to one (ablation) | Switch with randomized breakpoints · Single-machine scheduling, imperfect predictions | smoothness to prediction error | Helped |
| Set λ below one and mix Switch with round-robin (ablation) | Preferential algorithm · Single-machine scheduling, imperfect predictions | robustness: \frac{2}{1 - \lambda} | Helped |
| Increase the number of predicted jobs B (ablation) | Preferential algorithm with λ = 1 and ρ = 0.5 · Synthetic Pareto job sizes with noisy predictions | consistency | Helped |
| Increase the number of predicted jobs B (ablation) | Preferential algorithm with λ = 1 and ρ = 0.5 · Synthetic Pareto job sizes with high prediction error | performance deterioration | Hurt |
| Increase ρ (ablation) | Switch with randomized breakpoints · Consistency-smoothness experiment, B ∈ {50,95} | competitive ratio at zero prediction noise | Hurt |
Surprising findings
- The consistency-smoothness tradeoff vanishes when B is close to 0 or n.
- Setting rho = 0 (best consistency) yields a discontinuity in competitive ratio as soon as prediction error becomes positive, showing non-smoothness for trivial breakpoints.
Limitations
- Gap between lower bounds and competitive ratios of Switch and CRRR for perfect predictions remains.
- Adapting CRRR to imperfect action predictions is left open.
- Smooth algorithms seem to require consistency above 2 - B/n; whether a smooth (2-B/n)-consistent algorithm exists is open.
Experimental setup
Datasets: synthetic exponential job sizes synthetic Pareto job sizes (shape 1.1) truncated heavy-tailed distribution Phi(0.51, 1e4)
Metrics: competitive ratio empirical ratio versus OPT
Baselines: Round-robin CRRR Shortest predicted job first Preferential round-robin Run To Completion
Builds on: round-robin scheduling shortest predicted job first preferential round-robin (learning-augmented scheduling) Yao's minimax principle
Closest papers by meaning
- Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints (ICML 2023 · similarity 0.93)
- On Smoothness Bounds for Non-Clairvoyant Scheduling with Predictions (ICLR 2026 · similarity 0.90)
- Non-Clairvoyant Scheduling with Progress Bars (NeurIPS 2025 · similarity 0.89)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.85)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.83)
- Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.