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

1.1 Contributions

• The Modified Two-Stage Schedule (mTSS) achieves (1 + λ)-consistency with robustness within a factor of 3/2 of the lower bound for every n ≥ 2 and admissible λ.Its bounds can be computed for any n and appear empirically to differ by at most approximately 1.0937.Source: §1.1 · p. 3
• As n → ∞, the lower bound improves the leading constant of the Wei–Zhang bound by a factor of 2, while mTSS has robustness at most 1/4 + 1/λ for every n and admissible λ.The lower and upper bounds match in their leading term as λ ↓ 0, and the universal upper bound closes the polynomial gap in the worst-case-n regime.Source: §1.1 · p. 3
• A generic error-tolerant simulation preserves consistency and local smoothness under bounded prediction errors, at the cost of a small increase in worst-case robustness.Local smoothness means performance degrades smoothly as prediction error increases.Source: §1.1 · p. 3
• A multi-stage adversarial construction yields a stronger piecewise lower bound for n ≥ 5 over a nontrivial range of λ, showing the Wei–Zhang bound is not tight generally.The construction allows attacks at different stages, rather than only immediately after the first job completes.Source: §1.1 · p. 3
• mTSS calibrates its initial round-robin stage to exhaust the consistency budget, then processes jobs in predicted order.Its robustness analysis reduces to performance at the time prediction error is detected, yielding a finite-n optimization bound and a closed-form universal bound.Source: §1.1 · p. 4

1.2 Related Work

• For general n, the optimal tradeoff remained open despite exact or asymptotic characterizations for problems including ski rental, online conversion, and metrical task systems.Consistency measures performance with perfect predictions, while robustness measures performance under potentially adversarial prediction error.Source: §1 · p. 1, §1.2 · p. 5

2 Problem Formulation and Preliminaries

• The paper restricts its analysis to deterministic algorithms and establishes notation for natural numbers, nonnegative real vectors, and the asymptotic regime λ → 0.Source: §2 · p. 5

2.1 The Classic Non-Clairvoyant Scheduling Problem

• The scheduler allocates one machine’s capacity among n unfinished jobs whose processing requirements are unknown until completion, minimizing total completion time.Source: §2.1 · p. 5
• With processing requirements known in advance, Shortest Remaining Processing Time minimizes total completion time and is equivalent to Shortest Job First when all jobs arrive at time 0.Source: §2.1 · p. 5
• The competitive ratio compares an algorithm’s total completion time with the clairvoyant optimum across instances.Source: §2.1 · p. 6
• Round-Robin achieves the optimal deterministic competitive ratio 2n/(n + 1) for n jobs, with a tight uniform bound of 2 across all n.Source: §2.1 · p. 6

2.2 Non-Clairvoyant Scheduling with Predictions

• With predictions, each job has a predicted size, but its true processing time remains unknown until completion, and predictions may be arbitrarily inaccurate.Source: §2.2 · p. 6
• Consistency is worst-case performance when predictions are correct, whereas robustness is worst-case performance over all prediction-augmented instances.Source: §2.2 · p. 6
• For fixed λ > 0, the optimal tradeoff is framed as minimizing worst-case robustness subject to maintaining (1 + λ)-consistency.Source: §2.2 · p. 6

3 Lower Bounds

• The lower-bound construction formulates robustness and consistency constraints as a nonlinear optimization problem, then transforms it into an implicit bound for finite n and an asymptotic form as n→∞.Source: §3 · p. 7

3.1 Warmup: Looseness of the Wei and Zhang Lower Bound

• For n≥5, the Wei and Zhang lower bound is not tight, even after optimal padding, for every λ in the stated interval.The earlier construction attacks immediately after the first job completes; the authors show that delaying the attack can increase the competitive ratio.Source: §3.1 · pp. 7–8

3.2 Designing a New Adversarial Strategy

• The α-Instance Attack Set lets an adversary choose among attacks after different numbers of jobs have been processed, forcing the algorithm to hedge across attack times.The set uses identical predictions and candidate instances defined from the algorithm’s processing under accurate predictions.Source: §3.2 · p. 8

3.3 A Strictly Improved Lower Bound

• At optimality, unfinished jobs receive equal processing at each attack, every attack constraint is tight, and the consistency budget is exhausted when the α-th job finishes.This structure reduces the processing variables to common values p(1), …, p(α), which characterize the solution through the Order-α System.Source: §3.3 · p. 10
• For n≥5, any (1 + λ)-consistent algorithm must have robustness at least Φ(n)(λ), strictly improving the Wei and Zhang lower bound in the stated range.The selected attack depth gives Φ(n)(λ) for 0 < λ < (n−1)/(n+1).Source: §3.3 · p. 11

3.4 An Asymptotic Lower Bound as 𝑛→∞

• As n→∞, any (1 + λ)-consistent algorithm for λ∈(0, 1) must have robustness at least the unique solution ˆγ(λ) to the stated equation.Source: §3.4 · p. 12

4.1 An Improved Algorithm: Modified Two-Stage Schedule

• mTSS exhausts its consistency budget during an initial round-robin phase, then commits to jobs in predicted order.The transition is calibrated using the Round-Commit Truncated Cost Function; after a detected error, the algorithm switches back to round robin.Source: §4 · p. 12, §4.1 · pp. 12–13

4.2 Reduction to the Time of Error Detection

• After an error is detected, the robustness analysis reduces to bounding performance at detection, because round robin controls the remaining work.For fixed predictions, the adversarial analysis reduces to a finite family of truncated prediction vectors.Source: §4.2 · pp. 13–14

4.3 A Nearly-Optimal Upper Bound for General 𝑛

• The upper-bound analysis reduces the cost ratio to feasible vectors with at most two positive gaps, then to a maximization over one integer index.A weighted-average decomposition ensures the original ratio cannot exceed the largest component ratio.Source: §4.3 · p. 16
• Within a factor of 3/2 of the best achievable robustness, mTSS is (1 + λ)-consistent and Ψ_n(λ)-robust for general n.The bound is given by a maximization over a single integer index.Source: §4.3 · pp. 15–16

4.4 A Universal Closed-Form Upper Bound

• A quadratic inequality converts the finite-n robustness guarantee into a closed-form upper bound with explicit λ dependence, uniformly over n.The passage states that this bound makes comparison with the lower bounds direct.Source: §4.4 · p. 17

4.5 Ensuring Smoothness via Error-Tolerant Simulation

• For any tolerance τ, prediction-tolerant simulation preserves β-consistency and gives (1 + τ)^2γ-robustness while providing local smoothness when prediction error is at most τ.Applied to mTSS, the robustness guarantee becomes (1 + τ)^2Ψ_n(λ).Source: §4.5 · p. 17

5 Conclusion and Future Directions

• For every n ≥ 2 and admissible λ, mTSS’s upper bound is within a factor of 3/2 of our lower bound; Wei and Zhang (2020)’s lower bound is strictly weaker for n ≥ 5 over a nontrivial λ range.Source: §5 · p. 17
• As n → ∞, the paper establishes an asymptotic picture of the optimal tradeoff for (1 + λ)-consistent algorithms.The supplied passage introduces the result but does not include its formula.Source: §5 · p. 18
• Future directions include weighted scheduling, alternative prediction models, other online problems, and closing the remaining finite-n gap for n ≥ 5.The authors conjecture that optimal robustness may require repeated cycles of round robin and committing to predicted order.Source: §5 · p. 18

AI Use Acknowledgment

• The authors used AI tools for initial proof development and drafting, limited language editing, and help simplifying and checking proofs, with all assisted content reviewed by the authors.The authors state that they take full responsibility for the paper’s content.Source: AI Use Acknowledgment · p. 18

A Properties of the Value Function Φ

• The appendix states that it establishes the well-definedness of Φ(n) and a monotonicity property for Φ_·,n.Source: A Properties of the Value Function Φ · p. 22

A.1 Well-Posedness of the Function Φ(𝑛)

• For each admissible γ, the reversed order-α system has a unique solution, inducing a well-defined mapping from γ to λ.The solution variables p(i) lie in [0, 1].Source: §A.1 · pp. 22–23
• Λ_α,n is continuous and strictly decreasing in γ, so its inverse Φ_α,n is well-defined on the stated ranges.These properties, together with the construction of Φ(n), establish its well-definedness.Source: §A.1 · pp. 23–25

A.2 Monotonicity Property of Function Φ𝛼,𝑛

• For fixed n and λ, Φ_α′,n(λ) > Φ_α,n(λ) whenever α′ > α in the stated domain.The proof compares adjacent branches and applies the comparison successively.Source: §A.2 · pp. 25–26

B.1 Proof of Proposition 3.1

• The proof chooses processing times with x_1 = y_1 = 1 and x_i = d(i, 1) + ε for i ≥ 2, then optimizes the allocation profile under its constraints.An optimal profile has equal d(i, 1) values for jobs i = 2, …, n.Source: §B.1 · pp. 26–27
• A consistent algorithm must allocate all processing time to job 2 immediately after job 1 completes in the specified interval.The argument uses the consistency requirement when all predictions are accurate.Source: §B.1 · p. 27
• In the constructed interval of λ, the resulting ALG/OPT ratio is strictly larger than Wei and Zhang (2020)’s bound, so that bound is not tight there.Source: §B.1 · pp. 27–28

• For all sufficiently large n, the maximum defining Φpad_wz(n, λ) is nonempty.Source: §B.2 · p. 28
• Φpad_wz(n, λ) is nondecreasing in n.Source: §B.2 · p. 28
• Because Φpad_wz(n, λ) is bounded above, its limit exists.Source: §B.2 · p. 28

• For λ ≥ 1/2, the expression in (1) is strictly increasing in the number of jobs.Source: §B.3 · p. 28
• Every (1 + λ)-consistent algorithm for n jobs has robustness strictly greater than Φwz(n, λ), and therefore strictly greater than the padded lower bound.Source: §B.3 · p. 28

• The sorted cumulative-processing profile defines a feasible single-machine schedule, with a fixed work-conserving rule used if completion history departs from the accurate all-unit execution.Source: §B.4 · p. 29
• On the accurate all-unit instance, the constructed algorithm completes jobs at the original algorithm’s completion times and incurs the same total completion time.Source: §B.4 · p. 29
• The two algorithms have the same competitive ratio under perfect predictions because the offline optimum depends only on the instance.Source: §B.4 · p. 29
• Non-clairvoyance makes the executions agree through each attacked completion time, and infinitesimal ε makes corresponding attacks yield the same outcomes.Source: §B.4 · pp. 29–30

Step 1: The attack-based optimization problem

• The optimal value ϕα,n(λ) of Problem 36 lower-bounds the robustness of every algorithm under consideration.Source: §B.5 · p. 31

Step 2: Structure of optimal solutions

• At every optimum, unfinished jobs receive equal processing, and all attack constraints and the consistency budget hold with equality.Source: §B.5 · p. 34

Step 3: Identification with the Order-αSystem

• Substituting the common unfinished-job processing amounts into the tight constraints yields the Order-αSystem equations, whose admissible solution is unique.Source: §B.5 · p. 34

Step 4: Selecting the attack depth and concluding the proof

• The attack-depth selection rule is well-defined and selects a depth whose optimal value lies in the interval where the structural characterization applies.Source: §B.5 · p. 36
• For the selected depth, ϕα,n(λ) equals Φα,n(λ), the corresponding branch of the lower-bound expression.Source: §B.5 · p. 36

B.6 Proof of Theorem 3.10

• The finite-n order-system product formula is converted to a limit using log(1 − u) = −u + O(u^2) and a Riemann sum.The construction chooses γ_n → x > 2 and derives the limiting expression before proving monotonicity.Source: §B.6 · pp. 36–37
• F is continuous and strictly decreasing on [2, ∞], with F(2) = 2 and F(∞) = 1.These properties yield a unique threshold γ̂(λ) > 2 for each λ ∈ (0, 1).Source: §B.6 · pp. 37–38
• As n → ∞, the proof establishes an asymptotic lower bound on robustness for every (1+λ)-consistent algorithm.It first derives the limit from finite-n order systems, then uses strict monotonicity to conclude the bound.Source: §B.6 · pp. 36, 38

C.1 Proof of Theorem 4.4

• At λ = 0, calibration gives v = 1 and r = 0, making Stage 1 zero-duration; with accurate predictions, Stage 2 orders jobs by true processing time, proving 1-consistency.Source: §C.1 · p. 38
• The robustness analysis reduces prediction errors to truncated vectors and a linear-fractional optimization over ordered processing times subject to calibration.A cone decomposition shows it suffices to consider at most two positive gaps.Source: §C.1 · pp. 40–41
• The comparisons increase c and z to n, bounding the ratios by the resulting maximum; that maximum also dominates the remaining ratios, since R_{n,n,1} ≥ ρ_n = 2n/(n + 1).The proof concludes that the algorithm is Ψ_n(0)-robust.Source: §C.1 · pp. 38, 42, 43

C.2 Proof of Theorem 4.6

• Theorem 4.6’s proof bounds the relevant maximum by locating its smallest maximizing index s and applying the corresponding attack constraint.The argument establishes s ≤ α before using the s-th attack constraint.Source: §C.2 · pp. 43–44

C.3 Proof of Theorem 4.7

• Theorem 4.7’s proof shows every ratio in the maximization defining Ψ_n(λ) is at most R, establishing the robustness guarantee.Consistency follows from Theorem 4.4.Source: §C.3 · p. 45

C.4 Proof of Theorem 4.8

• For general bounded errors, the error-tolerant cost is at most (1 + τ)^2 γ OPT(x).The proof compares execution with the original algorithm on simulated processing times and bounds the extra processing by τ times the predictions.Source: §C.4 · p. 46
• For bounded errors with ε ≤ τ, the error-tolerant algorithm’s cost is at most β(1 + ε)^2 OPT(x).In this case the simulated prediction matches y, and the additional-processing phases take at most ε y_i time.Source: §C.4 · p. 46