Research map / Bandits and online learning / Online convex optimization and games
Non-Clairvoyant Scheduling with Progress Bars
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.
Introduces non-clairvoyant scheduling with progress bars (adversarial and stochastic), giving consistency-robustness-smoothness guarantees, a general combining algorithm for scheduling with computable delays, and an asymptotically optimal repeated explore-then-commit algorithm for stochastic progress bars.
Problem
Minimizing total job completion time on a single machine (or m machines) without knowing processing times in advance, when the scheduler receives progress-bar feedback that may be adversarial or stochastic.
Approach
Model online scheduling where each job emits progress-bar signals at unknown or random fractions of its processing; design SETF-based robust algorithms with perfect consistency and smoothness, a general randomized combining method for algorithms with computable delays, and a repeated explore-then-commit algorithm matching a lower bound in the stochastic Poisson model.
Key results
- Single-signal algorithm is (1+alpha)-consistent and (1+1/(rho alpha))-robust with smoothness bound; a lower bound shows any (1+alpha)-consistent algorithm has robustness 1+Omega(sqrt(1/alpha)).
- Repeated explore-then-commit achieves competitive ratio 1+O(g^{-1/3}) with stochastic progress bars, matched by a 1+Omega(g^{-1/3}) lower bound.
- Combining algorithm achieves E[ALG] <= min_h A^(h) + O(n^{5/3} (log g)^{1/3} max p_i), yielding consistency 1+o(1) and robustness 2+o(1) when max p_i = o(n^{-5/3} OPT).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Give a job preferential execution after its accurate signal | Single-signal scheduling · Accurate single-signal progress bar | competitive ratio: 2 -> 1 + \alpha | Helped |
| Use the untrusted-signal algorithm with parameter \rho | Single-signal scheduling · Untrusted single-signal progress bar | robustness: 1 + \nicefrac{1}{\rho \alpha} | Mixed |
| Increase progress-bar granularity g | Repeated Explore-Then-Commit · Stochastic progress bar | expected competitive ratio: 1+ (12/g)^{1/3} | Helped |
| Use the threshold k = \lceil (g/2)^{2/3}\rceil + 1 | Repeated Explore-Then-Commit · Stochastic progress bar, g \geq 12 | expected competitive ratio: 1+ (12/g)^{1/3} | Helped |
| Use the proposed repeated explore-then-commit algorithm rather than Round-Robin or generic ETC | Stochastic progress bar scheduling · Stochastic progress bar | empirical competitive ratio | Helped |
| Set \rho close to 1 rather than using smaller \rho | Untrusted-signal algorithm · Noisy job-size predictions | robustness | Helped |
| Use smaller \rho rather than setting \rho close to 1 | Untrusted-signal algorithm · Noisy job-size predictions | smoothness | Helped |
| Use the combining algorithm rather than time sharing or delayed predictions | Robustification strategies · Noisy job-size predictions | robustness and consistency | Helped |
| Use delayed predictions rather than time sharing | Robustification strategies · Noisy job-size predictions | robustness | Helped |
Surprising findings
- The SETF-based robust algorithm with rho=1 is brittle: arbitrarily small signal-time errors can push its ratio to 2.
Limitations
- Gap of Theta(alpha^{-1/2}) between upper and lower bounds on the single-signal consistency-robustness tradeoff.
- No improvement over competitive ratio 2 for granularity g <= 12 in the stochastic model.
- Parallel-machine extension only gives a preliminary (1+alpha)-consistent, (1+1/alpha)-robust result.
Experimental setup
Metrics: competitive ratio total completion time
Baselines: Round-Robin time sharing delayed predictions generic explore-then-commit
Builds on: Round-Robin Shortest Elapsed Time First time sharing for learning-augmented scheduling Lattanzi et al. combining permutation predictions
Closest papers by meaning
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.89)
- Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints (ICML 2023 · similarity 0.88)
- The Road Less Scheduled (NeurIPS 2024 · similarity 0.84)
- The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Training (ICML 2025 · similarity 0.84)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.83)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.82)
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.