On Smoothness Bounds for Non-Clairvoyant Scheduling with Predictions
Authors: Tianming Zhao
Albert Zomaya
Venue: ICLR 2026 Poster (2026)
Keywords: Algorithms with predictions
Smoothness
Scheduling
Primary area: optimization
TL;DR: We show smoothness bounds for a few non-clairvoyant scheduling with predictions.

Abstract: Algorithms with predictions leverage predictions for unknown inputs in online decision-making. These algorithms are analyzed by consistency, i.e., competitive ratio under perfect predictions, and robustness, i.e., competitive ratio under worst-case predictions. Smooth degrading performance with an increased prediction error is also desirable. This paper refines the notion of smoothness, a function of prediction error, defined as the competitive ratio over the problem instances where predictions are guaranteed to provide additional information. 

With our refined smoothness metric, we establish smoothness bounds for a few scheduling problems, including online total completion time minimization and makespan minimization. For a single machine to minimize the total completion time, we show a lower bound of $\eta$ and a $\eta^2$-smooth algorithm, where $\eta$ is the prediction error ($\eta \geq 1$); the bound holds for small errors. For parallel identical machines to minimize the makespan, we show a lower bound of $2 - O(\eta^{-2})$ and present an $O(\eta^2)$-smooth algorithm for small errors. Both bounds are tighter than the existing ones. For uniformly-related machines to minimize the makespan, we show a tight lower bound of $\lceil \log \eta \rceil$, matched by an $O(\log \eta)$-smooth algorithm.

Published as a conference paper at ICLR 2026
ON SMOOTHNESS BOUNDS FOR NON-CLAIRVOYANT SCHEDULING WITH PREDICTIONS
Tianming Zhao
Albert Y. Zomaya
The University of Sydney tzha210 01 gma com
The University of Sydney
bert. zoma sydaadeyssyydyy...m..... edu. au
ABSTRACT
Algorithms with predictions leverage predictions for unknown inputs in online decision- decision-making, These algorithms are analyzed by consistency, i.c., competitive ratio under perfect predictions, and robustness, i.e., competitive ratio under worst- case predictions. Smooth degrading performance with an increased prediction error is also desirable. This paper refines the notion of smoothness, a function prediction error, defined as the competitive ratio over the problem instances where predictions are guaranteed to provide additional information.
With our refined smoothness metric, we establish smoothness bounds for few scheduling problems, including online total completion time minimization and makespan minimization. For single machine to minimize the total completion time, we show a lower bound of 7) and a 17" r7"-shooth algorithm, where 1) the prediction error (1) 1); the bound holds for small errors. For parallel identical machines to minimize the makespan, we show lower bound
(1)) and present (n²²) -mmooth algorithm for small emrors. Both bounds tighter than the existing ones. For refformml-relaater machines to minimize the makespan, we show tight lower bound of (log 17), matched by an O(log 7) -smooth algorithm.
INTRODUCTION
Online problems require algorithms to make decisions without complete information. The tradi- tional assumption is that information is either known or unknown, or becomes known after specific events occur (e.g.. job size is learned only after the job completion in non-clairvoyant scheduling). Such treatment of information, however, is suboptimal, either too optimistic or too pessimistic. The framework of algorithms with predictions addresses these limitations by assuming that predictions of unknowns are available to support decision making while admitting potential prediction errors. The framework produces algorithms that leverage additional but possibly inaccurate information against uncertainty. Under this setting, it is desired that the algorithms are consistent and robust, meaning good performance under perfect and the worst-case predictions. The literature also de- mands that such algorithms be smooth against prediction errors, i.e., the algorithm's 's performance should degrade gracefully with worsening predictions.
The existing notion of smoothness-compttiiine ratio written function of the prediction error- can sometimes meaningless. This is because, for a given prediction error, one can often find some problem instances where predictions give additional information, especially if the error is defined in an "absolute" sense, thus essentially turning the analysis into the cases without predic- tions. We illustrate this claim with the following example. Consider the problem of single-machine non-clairvoyant scheduling to minimize the total completion time with job size predictions. The job sizes denoted by Pí .... P", and the predictions pi.... P Suppose that the prediction error is defined as the -idittanee between the predictions and the true values, i.c., Σn= Ip3 - -, Now, take any problem instance I; one can construct I' by scaling the job sizes such that Σソ and setting the predictions all to zero. By construction, the prediction error in I' is 7), but predictions are completely uninformative- any algorithm'' 's performance on I' will match its worst-case perfor- mance without predictions. This argument holds for any prediction error 77. Thus, the smoothness curve (i.c., competitive ratio as a function of the prediction error) can be arbitrarily high and thus fail to reflect genuine marginal benefits from reasonable predictions.

---

Published as a conference paper at ICLR 2026
We propose refined definition of smoothness with the intention that any bounds must reveal the marginal benefit of predictions when they do provide additional information. We define smoothness as the competitive ratio over the problem instances where predictions are guaranteed to provide additional information. Precise definitions and examples are in the later sections, but the high-level idea is here. We partition the universe of problem instances into (1) ones with perfect predictions, (2) ones with the prediction error large enough so predictions potentially cannot distinguish anything (i.e., the worst-case predictions), and (3) ones with 1 small enough so predictions are guaranteed to add information (i.e., reasonable predictions). Smoothness is then defined as the competitive ratio as a function of the prediction error over the problem instances with reasonable predictions. Consistency is that over the instances with perfect predictions, and robustness is that with the worst- case predictions. To solidify the ideas, we look at familiar non-clairvoyant scheduling with job size predictions. We show that lower bounds on smoothness exist for any deterministic algorithm. Some bounds are asymptotically tight, as algorithms with a matching smoothness guarantee exist. Under smoothness notion, the lower bounds can be interpreted as the best possible competitive ratio an algorithm can achieve, even if the predictions always provide additional information, which shows the limits and, at the same time, the potential of algorithms with predictions.
We focus on non-clairvoyant scheduling to study smoothness. There have been extensive develop- ments in scheduling theory since its inception (Graham 1966), offering rich results for clairvoyant and non-clairvoyant scheduling. Algorithms with predictions are a natural advancement to interpo- late the existing algorithms, with the hope that the learning component can further improve decision- making and lower bounds of non-clairvoyant scheduling. Scheduling with predictions is also one of the first fields from which algorithms with predictions have grown (Purohit et al.) 2018). This study aims to understand the limits and potential of predictions by showing bounds on smoothness when predictions are guaranteed to provide additional information. In particular, we consider (a) single-machine scheduling to minimize the total completion time, (b) parallel identical machines scheduling to minimize the makespan, and (c) uniformly-related machines scheduling to minimize the makespan. These concrete scheduling problems have been studied under algorithms with pre- dictions. Our contributions include providing analysis with a different (perhaps more suitable) pre- diction error, tighter bounds, algorithms with improved guarantees, and the first established bound.
Single machine scheduling to minimize the total completion time. We revisit this problem with (to this problem) prediction error metric. The existing works have relied on the L -iittanee error, which is sealeisensitive (Purohit et al. 2018) Wei and Zhang [2020] [aappi et al.] (022). Our error metric, however, is multiplicative without scaling issue. With this new metric, our analysis for smoothness bound demonstrates a strong min-max game-theoretic dynamic between the scheduler and adversary. The game reveals the edge of the scheduler with predictions: predictions constrain the problem instances the adversary is allowed to use. It turns the adversary to face a constrained optimization, thus forcing a much more involved adversarial strategy to yield any non-trivial bound.
Parallel machines scheduling to minimize the makespan. The recent work Bampis et al. (2023) the first to consider this problem under algorithms with predictions. The first lower bound has been given, achieved via static adversary, as well as the first upper bound using Longest Predicted Job Size First. We improve the lower bound using a more adaptive adversary that creates problem instances differently according to different prediction errors. In addition, we improve the upper bound by showing an online algorithm based on the offline (1 + apaapooximmttion algorithm.
Uniform machines scheduling to minimize the makespan. The recent work of Zhao et al. (2022) is the first to consider this problem under algorithms with predictions. An O 11) c)coopettitive algorithm has been proposed. However, a lower bound is missing. We fill this gap by giving the first smoothness bound through an adversarial strategy that forces any algorithms to be 2( n)) competitive. This bound is asymptotically tight, matching the existing O(log 1) competitive ratio.
Technical contributions. We introduce a refined definition of smoothness, which measures the performance of an algorithm as predictions worsen when the predictions are guaranteed provide additional information. For the total completion time minimization with job size predictions, we show a smoothness lower bound of 1 and 1y2-smooth algorithm for small prediction error 7) (S 1. 1.835). For makespan minimization, we show a smoothness lower bound of 2 2 O(n-²) for parallel identical machines, and we give a (1²2 + c)-smooth algorithm for small 17 (< 1.414). For uniformly- related machines to minimize the makespan, we show smoothness lower bound of [log which asymptotically tight, as an Ollo -moohhh algorithm exists.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
We consider non-clairvoyant scheduling with job size predictions. The system consists of m ma- chines and independent jobs. The number m is not fixed and is part of the problem input. A machine is denoted by Mi, 1 S. i I m; a job is denoted by J,. 1 S j S n. Job J has size Pj. but this value stays unknown until J, is completed. We use P= maxis P3 /minjsssn PI to denote the maximum job size ratio. Machine M, has processing speed 8;. For convenience, we sort the machines at a non-increasing speed, i.e., 81 2 #2 2 2 8m- The machine speeds are known to the scheduler. If job J is assigned to machine M,, the processing time for this job will be pj/ 8:. For the single machine case, there is only one machine with speed one. For parallel identical machines, machines have the same speed, i.e., 8, L, i. For uniformly-related machines, machines are al- lowed to have different speeds. The jobs are priority-free meaning there is no dependency between jobs. For completion time minimization, the jobs are preemptive with no cost for preemption. For makespan minimization, jobs are preemptive-restee but can be canceled and restarted later on any machine with no cost of preemption and migration. The job, however, loses its processing when it is canceled. At any time, job can be processed on at most one machine, and a machine can process at most one job. All jobs are available at the start. In completion time minimization, our objective is total completion time, i.c., Dj=1 Cg. For makespan minimization, our objective is makespan, Cmax. i.e., the time when the last job is completed. In Graham's 's notation (Graham et al. 1979), our problems are online-time-nche pmin Cg, Pm online- ceiete--tme-nccttt pest-restart Cmax= and Qm online- online-time-ine tite--imeecy pmmtt
meaning that running jobs are non non-preemptive
Cmaxx
Job size prediction pj is learned when J arrives. Following the works by Lattanzi et al. (2020); Zhao ct al. 22224), we define the prediction error for Jj as 7/ = max {Pa/p] p PJ/P3/ J. the multiplicative gap between prediction and exact value; the prediction error 1) for problem instance I is:
(T( = max Tl = max max p3 15jSn
Observe that 1) 2 1 and predictions are perfect if and only if 1) = 1. This multiplicative error has also been used by Azar et al. (2021 2022). They define the error (A) as the product of the maximum underestimation and overestimation factors. The worst-case predictions can have these factors the same, where A= = n/². We focus on deterministic algorithms and use A to denote an algorithm. A problem instance I consists of the scheduling problem, the number of machines, machine speeds (for uniformly-related machines), job sizes, and job size predictions. Let I be the collection of all problem instances. Let A(T) and (T) )) be the cost of the schedule produced by and an offline optimum. We say an algorithm has a competitive ratio c, or is c-competitive if = suprez
A(I)
RELATED WORKS
There has been a growing body of work on algorithms with predictions. For introduction, we refer to the surveys by Mitzenmacher and Vassilvitskii (202T) 2022). Algorithms with predictions were first introduced in Lykouris and Vassilvtiskii (2018); Purohit al. (2018) for caching, ski-rental, and scheduling, along with the notions of consistency and robustness. Following these foundational works, many problems have been studied in this framework: caching (Chledowski et al. [202]] rent- or-buy (Shin et al., 2023), secretary problems ( (Antoniadis et al.; 2020), graphs (Davies et al.) 2023), and scheduling (Lattanzi et al. 2020 Azar al. 200 1 Lindermayr et al. (023). We recommend the online repository (Lindermayr and Megow| (022a)) for a comprehensive overview of the literature.
Completion time scheduling has been studied under algorithms with predictions, including job size predictions (Purohit et al. 2201 8 Im et al. 2021 Wei and Zhang 20200 [Bampis et al.) (202)) and job ordering predictions (Lindermayr and Megow| 2022b] Dinitz et al. (022). For makespan minimiza- tion with predictions, Lattanzi et al. (2020) proposed competitive algorithm with machine load predictions for unrelated machines; it was later improved by Li and Xian (202T) to attain asymp- totic optimality. For uniformly-relane (2022) gave a competitive algorithm for static scheduling, and later, the algorithm was extended to dynamic scheduling (Zhao et al. 2024). For parallel identical machines, [Bampis et al. (2023) gave the first lower and upper bounds. Additionally, there have been efforts to address the limitations of assessing algorithms solely via consistency and robustness. Azar et al. (2023) proposed the metric of Hiscreteesmoothiie which evaluates performance as a function of prediction error but has the restriction that predictions must have the same form the solution to optimization problem.
machines scheduling with job size predictions, /hao et al.)
3

---

Published as a conference paper at ICLR 2026
RLF) fatse for inssances in this space
constart predicton anate
J22
Ja
RK(2 rnterras
Job 922
2,0
24.0
32.0
probiem relances I: - 1&
prodln instancos I:q tn S.D
probbmn Inssanoss Z:q K.n
J1
J2
J3
J1
J:
J9
J:
J2
J4
J1
J:
J3
J:
J1
J4
Job sizu prediction
2.
24.0
$2.0
3.0
18.5
450
08
800
25.0
7.0
40.0
044
10.0
10.
106
Figure I: visualization predicate R(I). Consider set three jobs: J1, J2, and J3 with job sizes 2, 24, and 32. Let vy(1) = _ max (P//pj.PP pP.p://p) There are problem instances (vectors of job size predictions) generated per level of prediction emorr We show few examples for v 1, 1.5, 3.0, 5.0. For 7 there exists no constant prediction vector, meaning R(() false for all instances with v) 4, i.e. the prediction error in this range reasonable. For n) 2 4, there will always exist constant prediction vector for every crror level. Thus, R(I) is true for any instance with 7 2 4, i.c., the prediction error is too large. The interpretation is that, if 2 4 for this job set, the predictions may provide no information by showing a constant vector. For the analysis of smoothness, we will focus cases where predictions do add information.
3 CONSISTENCY, ROBUSTNESS, AND SMOOTHNESS
This section introduces consistency, robustness, and our refined version of smoothness. The idea is to partition the universe of problem instances I into three sets I,, S I. Consistency, robustness, and smoothness are then defined to be the worst-case performance ratio over I. I, and I, respectively. Set Ie contains problem instances with no prediction error; I, contains problem instances where the error is large enough so that the predictions provide no additional information in the worst case; I, contains instances where the error guarantees additional information.
We use bold symbol to indicate a (n-dimensional) vector, so p= = (pt) denotes a vector of job sizes and p = (py)ısign job size predictions. Define error function m(p.p") to be the prediction error p with respect to p", e.g., mf(,,p)) = maxisişn max 1ps/Pj.p//pp) problem instance we use p² (7) and p(/) to denote the vectors of job sizes and job size predictions in I. and r1) np((T), (I)). We assume is non-decreasing with worsening predictions, i.e., larger error means worse.
For
We will introduce a predicate R(1) to model the worst-case predictions. It takes problem instance as input and outputs true or false, indicating whether the predictions reveal no additional informa- tion. Before presenting its definition, we give its high-level intuition. For a fixed prediction error n,, if one can create the job size predictions with 1) error equal to 1) and 2) all predictions have the same value, the predictions will not allow one partially order jobs, or even partition them according to the predictions. That is, the predictions are as if they are not present. In other words, for the given predictions, the set of possible actual job size vectors includes a constant one, meaning that all per- mutations of the jobs according to their job sizes remain possible. In such a scenario, the predictions reveal no additional information. Define predicate R(T) as: "3 constant p 7p p" (T)) = 77()." The predicate checks if any constant vector of job size predictions exists with error r7(), where constant vector means any arbitrary element is the same value. Intuitively, the predictions reveal no additional information in the worst case if R(() holds. We partition problem instances using It(I).
Definition 3.1 (Problem instances partitions).
I. (T] = "1(p" (T), I, (TIR(T), I, (I)-R()),,
Example 3.1. If (TT) = maxigign max (ps/p/ p3/P3} we have: I {TI((T) II.I. (T]((T) 2 VP(T).n() ((T) > 1) = {7] q(T) < VP(T)), where P(T) maxpz P/ Figure) visualizes the notion of predicate R(I) under this error metric.
The definitions of Ic, I,. and I, may change under different enror metrics and can also be extended to other predictions not just for job sizes. The partition is complete, i.e., I. U I, UI, = I, and disjoint, i.e., I. n I, I. II I, n I 0. giving clear-cuts between the problem instances considered by these metrics. We have developed a way to partition problem instances according to the prediction error. We then define consistency, robustness, and smoothness based on this partition.
4

---

Published as a conference paper at ICLR 2026
bang p02
mAx plasf
sorel jobs
optimel
Set (oo (or mecrrii small (obs) when schedueer
8
50
9-n
Run x jos to up lime:
run (1 at in y) is jobs AR tashion;
run (rp) 8 time
run one job up to time
Adversary
Auaild milgyse Oi constratnts
Schetule
optial
Figure 2: A visualization of the analysis for smoothness bounds for single machine completion time scheduling. The adversary decides the job size distribution using optimization ( The heights the bars (jobs) represent the job sizes. Given such an adversary, the best any scheduler can do is to run optimization (2) and schedule jobs accordingly. We show that the lower bounds derived from such dynamics are as stated in Theorem 4.1
Definition 3.2 (Consistency, robustness, and smoothness). For a minimization problem, we use CA. TA. and A (1) to denote consistency, robustness, and smoothness of algorithm A, defined as:
A(I) suPreI. OpE(T)> suPreI, Ope(T) SUPrEZ,,n()) Ope(T)
A())
A(I)
where A() and OIt(I) denote the costs of the schedules produced by algorithm A and the optimum.
Note that smoothness (1)) is a function of vl over the problem instances where the predictions must always provide additional information. One can view the metrics consistency, robustness, and smoothness as the competitive ratios of an algorithm over subsets of problem instances partitioned by the prediction error. Here, we discuss the connection between our proposed smoothness and the notion of the competitive ratio degrading smoothly with the prediction error, which exists before this work. The existing notion requires an error-dependent competitive ratio, i.e., bound written as function of the error, to be derived for an algorithm. Our smoothness explicitly defines such a func- tion. One can then say that an algorithm is smooth if its smoothness is in low-order form of 7), e.g., log 7 or a polynomial in y. In addition, the lower bounds indicate the limit of how such smoothness go. If a (tolg 1) bound exists, for example, it is impossible to attain better asymptotic func- tional form for the competitive ratio as a function of the error, even if the predictions are revealing additional information. Such explicit smoothness allows one study the limit and potential of the informational advantages carried by the predictions for dearning-augmenter algorithms.
The authors believe smoothness is better metric (than consistency and robustness) to consider. This is because, in practice, one will likely be dealing with predictions having some errors but not adversarial, so neither consistency nor robustness best describes the performance that matches the practice. While it is hard to know the prediction error apriori, it is not so to estimate the range of errors (e.g., through historical backtesting). so practitioners can optimize smoothness over the estimated range of errors. Another advantage is on lower bounds. Roughly speaking, lower bounds indicate the informational advantages carried by the predictions; they inform the marginal value of improving the accuracy of predictive models from business's perspective. To see this, suppose we establish a smoothness lower bound ((r) for some problem; that means improving the prediction error by factor of half may potentially give a doubled improvement on the end goal of the business; this may inform the business decision of allocating more resources to building accurate predictive models. We proceed with showing smoothness bounds for some scheduling problems.
4 SINGLE MACHINE TO MINIMIZE THE TOTAL COMPLETION TIME
This section focuses on single-machine scheduling to minimize the total completion time. Some notable prior results on completion time scheduling with predictions include a consistent and ro- bust algorithm for the single machine case (Purohit et al. 2018), optimal bobustness-consistreee trade-offs /Wei and Zhang 2020), an extension to multiple machines (Bampis et al.) (022), and the analysis for the case with partial predictions (Benomar and Perchet 2024). All these studies rely on the prediction error measured by the -dditaance between the predictions and the actual values, i.e., Σラ= 1p; psl. One drawback of the Li-dstancce metric is scale-sensitive. Consider two
stances: Tn with pi 1.P
p/ 2 and p1 1,p2 ... Pn 3 and Ta with
5

---

Published as a conference paper at ICLR 2026
pi = 11 = scaled I1. The Li-distance will report a 100 times larger prediction error, despite that the compet- itive ratio remains if the scheduled job order remains the same. The multiplicative-bast will report an error of 1.5 for both cases, indifferent to the algorithm from the prediction error's perspective. Thus, it is interesting understand the bounds of algorithms with predictions under the multiplicative measure for errors. An upper bound that can be immediately obtained from from|Azar et al. (0222) is O log n). We show the following lower and (improved) upper bounds on smoothness. Theorem 4.1. If A is an algorithm for single machine to minimize total completion time and n" is the positive root of x² 4x 4 =0 0 (n) x 1.835), SA (A())= 2 11 f 1) S 11", (1( Z X(1) for qf" < 2n o + (1+1)22 +90"="49
_... pi = 100 and P1 1. P2
Pr. 3 100. Roughly, Iz is 100-time
metric
1+ V3, and s an)) 2 2 for 1j > 1+ v3, where X(1) =
7 + +8
Theorem 4.2. For minimizing the total completion time, there exists competiiteee algorithm.
Remark 4.3. We have X(1) 2 0.187 + 1.5 no < S 1+v3, so the piecewise smoothness bound
yields A (n) 2 0.18n 1.5 over (n' +1 v3), simplified lower bound for X(1) in Theorem 4.1
Remark 4.4. A visualization of the smoothness bounds in Theorems 4.1 and is in Figure
The proofs of Theorems 4.1 and 4.2 are given in the appendix. We provide an overview of the analysis here. Fix any 1j. It IS natural to guess that Shortest Predicted Job Size First (SPJF), i.e., running jobs in non-decreasing order of job size predictions, is optimal for small prediction errors and that Gound-Robin (RR), i.e., equally sharing the processor among the active jobs, is optimal for large errors. We will show an adversary strategy to attack any algorithm under the constraint that the predictions guarantee to provide additional information. To do so, we reveal the true size of the smallest job while ensuring that the rest are indistinguisaable via predictions. Consider problem instance I: the first jobs have non-increasing sizes with the same job size prediction p. and the last job has a tiny job size but the correct job size prediction. We obtain: (1) predictions reveal informa- tion, (2) the first jobs are indistinguishable, and (3) the smallest job, although visible, contributes insignificantly to the total completion time. The benefit, however, that comes with predictions is that the indistinguishable jobs cannot differ too much from each other by size; they are constrained by the error n7. Since the smallest job cannot impact the total completion time much, we give any algorithm an advantage by finishing this job for free, and may ignore it to simplify the diseussion.
Any algorithm A will operate blindly against the first n jobs, so the adversary can force the algorithm to schedule these jobs in non-increasing order of job sizes. The optimum is running the jobs in non- decreasing order of job sizes. Then, the adversary considers the following optimization:
A(D (
1 (m- Ey.
p2x
which is a linear- fractional program with linear constraints, where the maximum occurs at a vertex of the feasible polyhedron. The relevant theory for this type of optimization problem can be found in Boyd and Vandenberghe (2004). The optimum is to set every job size to either one end of the extremes (17 or p/
1) Therefore, the optimization reduces to finding a B, 0 I B < 1, to maximize the ratio, where p = n. p.j S 38 and p = 11 j > Br. Let f(3) be the ratio after substituting this optimal solution structure. Taking the limit as n - oo and maximizing the function over 7+I- This gives us some hint on the adversarial
E [0, 1], we find the maximum achieved at 3 = 1 strategy. However, a straightforward adversary that assigns ,3t n jobs of size np (large jobs) and the remaining (1 - 5*) y jobs of size p/1) (small jobs) is not enough to yield the bound in Theorem 4.1 To see this, consider a two-phase algorithm B. In phase one, B processes p/v time for each job. During this phase, any small jobs processed will be completed, leaving large jobs. Phase two runs B(I) the rest of the jobs sequentially. A direct calculation shows lim Opt[T] < 17, for 17 > 1.6.
A more adaptive adversary works as follows. Let any algorithm A runs for t = (πр) - - time. A job is completed if and only if it has been processed for op time. These jobs are called large jobs. At time t", the adversary lets any job that has been processed for p/n to finish immediately (called intermediate jobs) and sets the rest of the jobs to have job size p/n) (small jobs). We show that when the prediction error is small, this adversary pushes the algorithm to complete all the large jobs before t" and to leave no intermediate jobs. This implies the lower bound of 17. When the error is large, the adversary pushes the algorithm to equally share the processor among the active jobs. This implies the lower bound of 2. When the error is moderate, however, the algorithm may mix SP/F and RR to fight against this adversary. In this case, the lower bound implied by this adversary is X(n).

---

Published as a conference paper at ICLR 2026
stpl- 1
Righe
aiqunme
10
175
3.08
1.5
3.00
1.55
225
270
3.06
Figure 3: Functions related smoothness bounds in Section Function f the piecewise lower bound in Theorem 4.1 is its linear first-order approximate
Figure 4: Function f is the lower bound in Theo- rem [.1] g. are components; a, I are bounds in Remark s is the upper bound in Theorem 5.4 h and are the bounds in Bampis et al. (2023) they should compare with f and
over (n 1+v3 3 in Remark 4.3 is the upper bound
Theorem
We outline the approach to derive the bound implied by the above adversary. Suppose algorithm
A knows the adversary's strategy and the value of 7) upfront. Effectively, A has to decide: (1) the number of large jobs to finish before time t", denoted by x n, S x S 1, (2) the number of small jobs to leave at t*, denoted by y 0 S y 1, and (3) the total time allocated to the unfinished small job group before t", denoted by e. We can show that these three parameters (z, y, e) represent all candidates for the optimal online schedule against this adversary. This claim follows from two observations about the optimal schedule. The first is that the number intermediate jobs is determined by (1 11-2- --))---- -y.,,, with total of la - (np) -2n time allocated to them, and it is optimal for A to equally share the processor among all the intermediate jobs. The second observation is that it is optimal for A bound 0 S e < p/n because the time allocated small jobs can be aggregated and used to yield more intermediate jobs, which favors A if e 2 p/n.. Then, it is optimal for A to concentrate e unit of time on one small job before t" Let be the adversarial instance. We can calculate A A(rane))) (I) and Optinmme) (T). Then, algorithm A considers the following optimization:
min (1)
(2)
a.y.C. Opt
s.t 1:7, max 0, n/xx + (1 x)
EN pr
S
T 0
where the constraint for y comes from that every intermediate job must have size at least p/n. Let 2n(n). 1(x, y, be the coefficient of the highest order term in A(z.v.e) (4) t Opt (4).
p
A(o)ne)) Showing some M is a lower bound for lim,- Opt reduces to h y. M) 2 0. Observe strictly convex in and y. We can show that h 0 indeed holds for the bounds stated in Theorem 4.1 Figure gives visualization of the above discussion.
We show that SPJF achieves competitive ratio of n72_ which proves Theorem 4.2 The proof follows the standard technique for analyzing SPJF used by |Purohit et al. (2018). Unfortunately, showing a better bound is non-trivial, although our lower bound analysis indicates that SPJF attains a competitive ratio 1) against the proposed adversary. Closing this gap is of future research interest.
PARALLEL IDENTICAL MACHINES TO MINIMIZE THE MAKESPAN
This section focuses on parallel identical machines scheduling to minimize the makespan. The clairvoyant case has been solved by polynomial approximation scheme (Hochbaum and Shmoys, 1987). where a (1 + e)-competitive algorithm is given with run time of ((n/e)*/<") The run time has then been improved to ((n/))(L)))) of one on consistency, which, as we will show, can be matched up to any precision. The non- clairvoyant case has been solved by Graham's 's list scheduling (Graham 1969,, which is (2 - ) competitive algorithm. List scheduling is optimal, given a lower bound (2 1) on the competitive ratio (Shmoys et al. 1995). Thus, a lower bound of (2 m on robustness exists, matched by list scheduling. So far, have not considered the predictions that are between perfect and worst-case.
by Leung 1989). There is a lower bound
7

---

Published as a conference paper at ICLR 2026
The first lower and upper bounds on algorithms with predictions given by Bampis et al. (023
They show a lower bound of 2-1/Ln² and an upper bound of +2)) if 17 2 or 2 otherwise. The lower bound follows from static adversary instance; the upper bound is obtained by Longest Predicted Job Size First based on Longest Job Size First (IJSF) (Graham 1969), which is 4/3-consistent and 2-robust. We will improve both bounds. In Theorem |5.
i.e., 2 +1//3 3
show a dynamic adversary based on the prediction error, which yields a better lower bound of m - 1/Ln²1, + (1p² 1)/[r²1}. In Theorem 5.4 we combine the (1 + -)apprroximation algorithm, i.e., the approximate offline optimum, and list scheduling to achieve a competitive ratio of roughly min 2]. It implies a better upper bound as 17² < 2(11² + 1)/3 if n² < 2. Moreover,
our algorithm achieves the optimal 1-consistency up to any precision while retaining the optimal 2-robustness. Figure 4
shows a visual comparison of these bounds.
Theorem 5.1. If AfArr is an algorithm minimize the makespan, sT() 2 max { [1+ L [
We give intuitions for the proof of Theorem 5.1 We want to construct problem instances where predictions reveal minimal but additional information. Observe that the makespan is heavily deter- mined by the allocation of large jobs: the competitive ratio improves from 2 1 to 3 - f with LJSF. Thus, our strategy, similar the previous section, is to reveal the true size of the smallest job while ensuring that the rest are indistinguishable via predictions. This ensures (1) (I) < (P(I) so predictions reveal information, and (2) we can analyze the marginal gain of the predictions. We consider the following setup: JI has the largest job size, 17", with a prediction of vy; J2,..... have the same job sizes close to 1 with predictions of Jn has a very small job size, e, with prediction of e. In this case, jobs JI,.... Jn are indistinguishable. Although the smallest job is visible, it contributes insignificantly to the makespan. Again, the algorithm benefits from that the indistinguishable jobs cannot differ too much by size; they are constrained by the error n,. Given that the smallest job will not impact the makespan much, we ignore it simplify the discussion.
Consider the simplest adversary strategy with 3 jobs and 2 machines. Job J1 has a size r7² with prediction 17, and jobs J22 and J3 have size with prediction n. These jobs are indistinguishable, so we can force any algorithm to allocate jobs J2 and J1 to machine M1 and Ja to M2. The resulting makespan is 1 + r7², while the optimum allocates J1 to M1 and J2, J3 to M2, attaining a makespan
2. We have established a lower bound of 1+n² n²
2 if 1j² < 2. When r/² 2 2, we set the sizes of J2 and Ju to 2 so the construction bounds the smoothness by 3. We can have a better adversary strategy
2'
as v) increases above 5 Consider 7 jobs and 3 machines: pi = 11² and Dł = 1 for 2 S j S 7, with PA = 17 for all j. We can force any algorithm to allocate J/, J2, J3 to Mi. J4, Js M2, and Jg. J7 to M3. achieving makespan of 122 2, while the optimum is 3. This yields a lower bound " n2+2 higher than 1 if n/ 2. Our proof of Theorem 5.1 generalizes this adversary strategy for any n)
2.
Observe that the lower bound on smoothness does not exceed 2. This is consistent with the 2- competitiveness of list scheduling, i.e., a a 2-competitive algorithm exists for any prediction error. The following bound is useful to represent the asymptotic behavior of smoothness.
Remark 5.2. (T) 2 max (1 + 1-'1-
(1²-1)² 2 - 2 1+ (1-11"44"
- E 2 2(n
We then give a consistent, smooth, and robust algorithm. Our algorithm has a competitive ratio of min(n² + c, 1 with a time polynomial in n for any given 0. The algorithm has near optimal consistency of 1 + smoothness of 172 +e for 172 < 2, and the optimal robustness of 2 1. Our analysis builds on the following result for clairvoyant scheduling.
m
Theorem 5.3 (Hochbaum and Shmoys ( 1987); : Leung (989)). There exists a (1 (ttp)--pppxiimmatoon algorithu with run time (nffe) (o/lo/))) for clairvoyant scheduling for any given 6 >> 0; it determines the allocation of jobs to machines upfront.
A straightforward application of this + + appprxximatio is to run the approximation algorithm as the job size predictions are actual job sizes. Call this algorithm SIMPLE. SIMPLE has consistency 1+e e and smoothness O11²), each job is under--over--ssimatee by at most factor of 1/. The algo- rithm, however, is not robust- has the robustness of ((m), the worst competitive ratio attainable by allocating all the jobs any machine. To see why SIMPLE is not robust, create = Km + m jobs for some large enough K; m - of them are small jobs with job size prediction and job size 8 for some small 8 and the rest Km are large jobs and have job size prediction 2e with job size
8

---

Published as a conference paper at ICLR 2026
1 for some small positive (c 2km) For any given SIMPLE must allocate each small job separate machine and all the large jobs on one machine- it is a (1 + apprrooximtaooon with respect to job size predictions. The makespan achieved by SIMPLE is Km while the optimum allocates the large jobs evenly and has a makespan at most K + 6. Thus, the robustness of SIMPLE is ((m).
To overcome the poor robustness of SIMPLE, we propose simple technique called list-adjusting: some machine M, finishes its last job determined by SIMPLE when some other waiting jobs are allocated other machines, we run any of them on M; instead of idling it. This technique ensures that the final schedule is replicable by list scheduling (thus the name list-adjusting), where list scheduling is (2 - 1,, competitiive for any job order. Note that aist-adjusting needs SIMPLE to have a static schedule to follow upfront, so knowing if job is the last on some machine is possible.
Theorem 5.4. For parallel identical machines to minimize the makespan, there exists min + e, 2 ccompetitive algorithm with run time polynomial in n. for any given e > O.
Figure plots the functions related to the smoothness bounds we have derived, including the lower bound (Theorem 5.1) and upper bound (Theorem [5.4). and compares them with the bounds derived by [Bampis et al. (2023). Functions and / take alternating domination in f. Function is (non-trivial) unified lower bound for f. which can be well-approximated by function for large 7. The optimal smoothness should lie between functions s and f. Therefore, gap exists between the upper and lower bounds for smoothness. Closing this gap for such fundamental scheduling problem may advance our knowledge about the smoothness of algorithms with predictions.
6 UNIFORMLY-RELATER MACHINES TO MINIMIZE THE MAKESPAN
This section focuses on uniformly-related machines. This problem has recently been studied under the algorithms with predictions setting; an O(min 17 log (r)mmm]mpttitiyy algorithm has been given by Zhao et al. (2024). The literature, however, missing a lower bound on smoothness. With our definition of smoothness, we show that a [log 17] smoothness lower bound exists; this bound is asymptotically tight, given that an Oloog smooth algorithm exists. Our key result is the following.
Theorem 6.1. If A is an algorithm to minimize the makespan, 8 A Z [log
Our adversary strategy has two key elements. The first is revealing additional but minimum informa- tion via predictions. We allow predictions to reveal the size of the smallest job while leaving the rest indistinguishable. The second is pushing the larger jobs to be finished later. Both elements follow the idea used in the previous cases. We show that this strategy implies a 52(log lower bound.
We create our adversarial problem instance for any given prediction error 1). Part of the design indistinguishable jobs, for which we follow family of instances developed by Cho and Sahni (180)) that has been shown effective in attacking non-clairvoyant scheduler (Shmoys et al.) 1995). Let [2 log n
Create groups of machines G, and groups of jobs T., for S Kis Every machine in G; has a speed of 2', and every job in T; has size 2', for 0 < < k, i.e., the machines in the same group are identical to each other, and the same for jobs. Every job in groups To...., T- has job size prediction of 17, and |G,| [T, 22k-2i-1, for 0 S sic < k. The k-th group is special, with one machine in G2 and one job in Tk. The speed of the machine in G3 is ò, and the size of the job in T' is å with job size prediction of 8, for a small 8 < min( Tog 7T 2. J. In this instance, we have n m. Index the jobs and machines such that p S pē S ... S Ph- Ph 8, $1 S s2 S S
8m Sm 5, - G [M, M2 ..... 1. and U T, = {J1, J.. ). The job size predictions are: Py 17, for S S n 1 and Pm 8. Table summarizes the problem instance.
There are a few properties of this problem in- stance: (1) the prediction error 77; (2) the in- stance belongs to I,; (3) the optimal makespan C = 1; (4) any schedule that completes a
mach grps.: Go
G1
G
G
job grps.:
To
Ti
T
Tk
8, / pf:
20
2
2h-1
job other than J,, on Mm must have a makespan
|G]] / [T]:
22h-1
22k-3
21
at least? 3 > flog Thus, Theorem 6.1 is triv- ial if the scheduler completes a job other than
py:
17
7
8
Table 1: The adversarial problem instance.
Jn on Mn. We assume Jj...., Jn-1 are com-
pleted on M,,.., m. Mn- for the following discussion so the scheduler correctly allocates J,.

---

Published as a conference paper at ICLR 2026
We introduce the notion of adversarial properties and show that the adversary force the sched- uler to finish larger jobs later. For any schedule, let (J) and ty( be the last starting time and the finishing time of job Jz. A job can be preempted and later restarted; t, ()) denotes the last starting time. Let m(j) be the machine that completes J.. Let j. be the highest index for the jobs in T;-
Lemma 6.2. Any scheduler can be forced to construct schedule with the adversarial properties:
S ... 1. (1) $t.(2))...
Sty(nn 10 1)
2. (1) + Pi 2t,)) <j<l<n
(m(
We show that, against the adversary problem instance, any schedule with the adversarial properties has makespan at least [log 7] through the following bounds. Lemma 6.3 shows that finishing any group of jobs costs at least one unit of time, Lemma bounds the time difference between finishing two groups of jobs. Putting these bounds together yields Theorem 6.1
Lemma 6.3. max ( (15( (.)) 2 1, S < k, under the adversarial properties. Lemma 6.4. ty ()! (
2 2, 4 k under the adversarial properties.
The bound in Theorem 6. is asymptotically tight, as an Ominn(og 17, log ccompetitiee algo- rithm exists (Zhao et al. 2024). With 2llog m) non-clairvoyant lower bound (Shmoys et al., 1995). the existing algorithm achieves asymptotically optimal consistency, smoothness, and robust- ness. This shows the possibility of attaining optimality in all three metrics.
7 DISCUSSION
Our definition of smoothness excludes the problem instances with predictions that reveal no addi- tional information. An alternative way to define smoothness would be to include these instances, i.e (1) suppetuingI. choose our definition because 1) fully separates the problem instances considered by the two met- rics, 2) the smoothness lower bound has the interpretation that "no algorithm can achieve better than 8 (7) even if the predictions are revealing additional information", and 3) the smoothness bounds stronger. All the derived bounds (Theorems 4.1 4.2 5.1 5.4 and 6. I still hold for ('A(T)). be- cause the problem instances considered in our definition are a subset of those in 8'A (n). It remains open if the proposed smoothness definition makes difference in the upper bounds, i... if there exists an algorithm A to some problem where (n) < s
Ope(T) While this also separates smoothness and robustness,
A())
We highlight that proposed notion of smoothness applies to other online problems. Different online problems and prediction settings require different interpretations of predicate R(1) in the definition. Take the one-way trading problem
example (Elenter et al., 20244 Benomar and Perchet 2025). Following the notations in Elenter et al. 22024). one candidate definition of R(T) is P-P-- max(p² - 1, M PE), where a the input sequence of exchange rates, P& the maximum rate in o. P the maximum-rate prediction, Ip- Po the prediction error, and M an upper bound on the rates known upfront. The intuition is that if R(I) holds for some problem instance I, p can take any value in [1, MM. given P. which effectively gives no additional information, as we know Pa e [1, M) upfront. This predicate R(T) allows one to partition the problem instances, thus leading to concrete definitions of consistency, smoothness, and robustness following the setup in our work.
8 CONCLUSIONS
Smoothness bounds are derived for some non-clairvoyant scheduling with predictions under our refined smoothness metric, which forces additional information from predictions. In the competitive analysis, we see that predictions constrain the adversary, forcing it to have a much more involved adversarial strategy. Lower bounds exist in smoothness the informational advantage of predictions cannot be unbounded, but gaps exist between the lower and upper bounds for virtually all problems considered. It will be interesting to see if any algorithm can achieve (exactly) optimal consistency, robustness, and smoothness. A positive answer will uncover the full potential of algorithms with predictions, A negative answer may reveal the ultimate trade-offss in this model.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their feedback and suggestions, which have improved this work. Professor Albert Zomaya and Dr. Tianming Zhao would like to acknowledge the support of the Australian Research Council Research Hub for Future Digital Manufacturing (JH230100013), Tianming expresses his gratitude to his family. He is grateful to his wife, Min Li, and his son, Michael Renqian Zhao, whose love and support have been a constant source of motivation and inspiration. He also warmly acknowledges the forthcoming new addition to his family.
REFERENCES
R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 4569):1563-1581, 1966. doi: 10.1002/j.1538-7300 1966.1001799.xx
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Alexander Wei and Fred Zhang. Optimal robustness-consiitens trade-offs for online algorithms. In Proceedings of the 34th International Conference Neural Informa- fion Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, and Fanny Pas- cual. Scheduling with untrusted predictions. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joins Conference on Artificial Intelligence, IJCAI-22, pages 4581-
4587. International Joint Conferences Artificial Intelligence Organization, 2022. doi: 00.24963/jcai.2222/338 URLhttts://doii /ttp://0o...0011.22/6/////// Track.
2022 636 Main
Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. -ln-Clairvoyant Makespan Minimization Scheduling with Predictions. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informatics (L.PPcss) pages 9: 1-1: Dagstuhl, Ger- many, 2023, Schloss Dagstuhl - weibnizz-Zentrun für Informatik. ISBN 978-3-95977-289-1 doi: 11.42200LLIIcsSSSAAAACCC document 100 4230 LIP ics. ISAAC. 2023.9
URL https::////.......... /tr///drpps.//// dagst dteesuuhh..deeetiiiiiss
Tianming Zhao, Wei Li, and Albert Y. Zomaya. Uniform machine scheduling with predictions. Proceedings of the International Conference on Automated Planning and Scheduling. 32(1):413- 422, Jun. 2022. URL https: / //ojs aaai, wwtp/iigge....o.oeeeeeeeo.eeeeee wttp://nww...g//I.asss.......... wttp:p//cs.//aacceeeee//pp 19827
R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In P.L. Hammer, E.L. Johnson, and B.H. Korte, editors, Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287-326. Elsevier, 1979, doi: www.:/accccccccaaaaaaaaaaa...... 7/www. htwp://cceecccaaecccccoooeeeeeee
URL http::
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings the Thirty-First Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA '20, page 1859-1877, USA, 2020. Society for Industrial and Applied Mathematics.
Tianming Zhao, Wei Li, and Albert Y. Zomaya. Searning-Augmentee Scheduling IEEE Trans- actiony on Computers, 73(11):2548-2662 November 2024. ISSN 1557-9956. doi: 10.1 109/ TCC.002..4418856 URL htt.httts///dd www.:eeeeeeeeeeeeeeeeeeee http://pwwwurrrc..o.o..rooooo//e 1109/TC. 2024. 3441856
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain pro- cessing time. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of
11

---

Published as a conference paper at ICLR 2026
Computing, STOC 2021, page 1070-1080, New York, NY. USA, 2021. Association for Com- puting Machinery. ISBN 9781450380539.
doi: 10.11457244633553351003.... URL hetps: 1/ 10.110../44443220 3451023
Yossi Azar, Eldad Peretz, and Noam Touitou. Distortion-Oblivious Algorithms for Schedul- ing on Multiple Machines. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz Inter- national Proceedings in Informatics (LIPIcs), pages 16:1-16:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl Leiiniiz-Zentrum für Informatik. ISBN 978-3-959777-558-. doi: 10.4230/ LIPPcs.ISAAC.2022... URL htttts://dropp.tt. 10. 28.4220/LIPICCS ISAAC. 2022.18 16
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions, page 662.662. Cam- bridge University Press, 2021.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65 (7):33-35, June 2022. ISSN 0001-0782. doi: 10.1145/3528087. URL [tl.https:///do .tr.oooo.orr/o// .org/
10.1145/3528087
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 9296-3305. PMLR, 10-15 Jul 2018.
Jakub Chiedowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zoina Robust learning- augmented caching: An experimental study. In Marina Meila and Tong Zhang, editors, Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1920-1930. PMLR, 18-24 Jul 2021.
Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung- -han An. Improved Saaming-auugment algorithms for the multi-option ski rental problem via best-possible competitive analysis. In An- dreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 31539-31555 PMLR, 23 Jul 2023.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online match- ing problems with machine learned advice. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Asso- ciates Inc ISBN 9781713829546.
Sami Davies, Benjamin Moseley, Sergei Vissilvi and Yuyan Wang. Predictive flows for faster ford-fulkerson. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pages 7231-7248 PMLR, 23-29 Jul 2023.
Alexander Lindermayr, Nicole Megow, and Martin Rapp. Speed-oblivious online scheduling: Knowing (Precise) speeds is necessary. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 21312-21334, PMLR, 23-29 Jul 2023.
Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https:// algori wwgorithmswwitheee. hhw.tttmss--ii--eeeetttiiooooos wwt.on.....tt........ 1o/] 2022a. Accessed: 2024-01-24.
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant schedul- ing with predictions. In Proceedings of the 33rd ACM Symposium on Parallelism in Algo-
rithms and Architectures, SPAA '21, page 285-294, New York, NY, USA, 2021. Association
for Computing Machinery. ISBN 45038800. doi: 10.114573499964.4661999 URL
12

---

Published as a conference paper at ICLR 2026
Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant schedul- ing. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '22, page 357-368, New York, NY, USA. 2022b. Association for Computing Machin- ery. ISBN 9781 0188445031446 doi: 10.1 015553440014.353383777 URL https:tppp//oot org/10.
1145/34901 48. 3538579
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vas- silvitskii. Algorithms with prediction portfolios. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Infor- mation Processing Systems, volume 35, pages 20273-20286. Curran Associates, Inc., 2022. URL http:://proceddnns..erriis cc.pppppp.cpppppp...p.eeeep fitees/pppeeee/22///////// Eile/ FLL1719221//350000331166666666-3 Confrrrr pdff
Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6523-6532. PMLR, 18-24 Jul 2021.
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Discrete-smoothnesss in online algorithms with predictions. A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 41932 41955. Curran Associates, Inc., 2023.
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 4 International Conference on Machine Learn- ing, volume 235 of Proceedings of Machine Learning Research, pages 3506-3538. PMLR, 21-27 Jul 2024. URL
httpppeess//23//eeennmraaaa/a/ html
Stephen Boyd and Lieven Vandenberghe. Convex optimization Cambridge university press, 2004.
Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM. 34(1):144-162, January 1987. ISSN 0004-
5411. doi: 10. 10.1145/7531.755 URL/LLtsss//bb.orr//D....
7535
Joseph Y-T. Leung. Bin packing with restricted piece sizes. Information Processing Let- ters, 1155)14 1989. ISSN 0020-0190. doi: http:://ooioog///000000000000000
90223-8.
URL http:///ww..cceeeeeeeeeeceeeeees
0020019089502238
R. L. Graham. Bounds multiprocessing timing anomalies. SIAM Journal on Applied Mathemat- ics, 17(2):416-429, 1969. doi: 10. 10.1137/01100
David B. Shmoys, Joel Wein, and David P. Williamson. Scheduling parallel machines on-line.
SIAM Journal on Computing, 24(6:1313-1331 1995. doi: 10.13775009755999244887. URL
https: http://.o..orr/....11////0033333
Yookun Cho and Sartaj Sahni. Bounds for list schedules on uniform processors, SIAM Journal on Computing, 91):9111033, 1980. doi: 10.1137/0209007. URL https:://do..og///
1137/0209007
Alex Elenter, Spyros Angelopoulos, Christoph Dür, and Yanni Lefki. Overcoming brittleness in pareto-optimal Baaming-auggentin algorithms. In Proceedings of the 38th International Confer- on Neural Information Processing Systems, NIPS '24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385.
Ziyad Benomar and Vianney Perchet. On tradeoff's in learning-augmente algorithms. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th In- ternational Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 802 810. PMLR, 03-05 May 2025. URL https: //proceedings..o .ww.e.g...........mm.o.... wwwpspesssseeeeeee wttppp/////////eoaaraaaaaaa////a html
13

---

Published as a conference paper at ICLR 2026
A PROOFS FOR SECTION
Proof for Example 3.7 easy verify for Ze, (I)) 1. Observe that Z, Zz
I, N = and Z, UZ, = I Ie. It suffices to show that PP(T) is the boundary for ()()) to separate I, and Z. under v/( > 1. Consider any problem instance with - v 2 / P())
and 17(1) > 1. Create a constant vector of predictions pe (Piin m))ssnn where Pmin
minissen p (I). Observe that npp", pT)
This means Er.
Consider any problem instance I with ( < < P(T) and nT() > 1. Without loss of generality, let pi and p1 be the minimum and maximum job sizes. For any constant predictions vector p (p)isisn with some constant p, it holds that Pi P
Pi
P(I), which means one of or Pi n(I). This holds for all constant vectors.
P
p
Pi
is at least /P([). Therefore, npp,p" (T)) P())
Thus, predicate R(I) is not true. This means E I..
B PROOFS FOR SECTION
This section proves the following theorems.
Theorem B.1 (Theorem 4.1.. If A is an algorithm for single machine to minimize total com- pletion time, SA(T) 2 1) for 17 S rf, SA(1) 2 ((1) for ni" 1] S v3, and s 2 for 7 1 v3. where 81 is the positive root of x 4r X 2n 10 - +0
(1) 1.835), and
p24447+88++
Theorem B.2 (Theorem 4.2p. For single machine minimize the total completion time, there exists a compeliiive algorithm.
Table
presents the notations used in the analysis.
Symbol
Meaning / Definition
Number of jobs.
J,
Job j. j n.
P
True job size of job Jj-
Pj
Job size prediction for Jj.
P
Maximum job size ratio P= (max, p3) (min, p2).
C
Completion time of job Jj-
Prediction error for job Jy: ΠΙ = /p)
Total prediction error max, f/--
A
Deterministic online algorithm under analysis.
Opt
Offline optimum schedule. A problem instance.
I
((T)
Total prediction error of T. Maximum job size ratio of L.
P(I)
A(I), Opt(()
Objective value of A and Opt on instance I.
sa(1)
Smoothness of as function of 77-
n?*
Positive root of 4x Intermediate lounr-bound function defined in Thcorem 4.1
0; numerically 1/" 1.835.
X(n)
8"
Fraction "large" jobs in the adversary construction; 3 1/(n + 1). Cut-off time (n") used by the adversary.
1"
N.
Schedule parameters: finished-large fraction, leftover-small fraction, and extra time spent one small job before t*.
h(x,
The expression governing the leading term of A(I) Opt(I) in the analysis.
Table 2: Notations used in the analysis.
14

---

Published as a conference paper at ICLR 2026
PROOF OUTLINE
We outline the proof first. Fix any T,. We reveal the actual size of the smallest job while ensuring that the rest are indistinguishable via predictions. Consider the following problem instance I: jobs have non-increasing sizes Pi 2 P2 2 2 Ph, where Pj E I//n, mp) Pj = p. J S ni, for some large positive p. and tiny job Jn+1 with Pi+1 = Pn+1 = < min 7 m Then, we have:
(1) MT()) < /P(T) so predictions reveal information, (2) jobs JI,...,JJ Jn are indistinguishable via predictions, and (3) the smallest job, although visible, contributes insignificantly to the total completion time. Given that the smallest job does not impact the total completion time and the
competitive ratio much, we give any algorithm an advantage by finishing this job for free and may ignore it to simplify the discussion.
Any algorithm A will operate blindly against the indistinguishable jobs JI.... , so the adversary
can force the algorithm to schedule the jobs in non-increasing order of job sizes. The optimum is running the jobs in non-decreasing order of job sizes. Thus, we have A(T) = Σラ= (n
1 1) P)
and (A)(A) = Σラ= j Pj. Then, the adversary considers the following optimization:
A(I) Opt(1) = Ej (n-
max mww
Th ビー=
which is a Ainear-fraction program with linear constraints, where the maximum occurs at a vertex (boundary) of the feasible polyhedron. Therefore, the optimization reduces to finding a B, 2.05 B < 1, to maximize the ratio, where p3_ = 7 p.j S .ān and p = p/ > Bn. Let ((3) be the ratio after substituting this optimal solution structure. Taking the limit as n oc, we have:
lim f(B) = 12(23 - B²) + (1- 32 + (1- 82)
Maximizing the right-hand side over 3 E [0, IJ, we find the maximum achieved at 8 = oFF However, a straightforward adversary that assigns f jobs of size up (large jobs) and the remaining (1 -B jobs of size p/1 (small jobs) is not enough to yield the bound. To see this, consider a two-phase algorithm B. In phase one, B processes p/n time for each job sequentially. During this phase, any small jobs processed will be completed, leaving large jobs. Phase two runs the rest of the jobs sequentially. A direct calculation shows (I) 1)2 ((2n) + 4n + 1)n n7 + 2nj² 1)
and OTT(T)= m)(2n+n+1) We have limn->oo Opt(1)
B(I) 1 1 42 strictly less than rj for "
2(
r > 1.6.
The adversary works as follows. Let any algorithm A runs for t" = (np) 8 time. A job is completed (immediately) and only if it has been processed for np time. These jobs are called large jobs. At time t", the adversary sets pj = x,((²) + if job Jj has been processed for 2z xz5(²) 2 p/n time with very small positive & (called intermediate jobs), or pj p/n if a (1") < p/n (small jobs). We show that when the prediction error is small, i.e., 17 S n7 ( 1.835), this adversary pushes the algorithm to complete all the large jobs before 1" and to have no intermediate jobs. This implies the lower bound of 17. On the other hand, the strategy pushes the algorithm to equally share the processor among the active jobs when the error is large, i.e., > 1 + v3 (x 2.732). This implies the lower bound of 2, matched by RR. When the error is moderate (i.e., 17" < 1) S 1 1 v3),, however, the algorithm may mix SPJF and RR to fight against this adversary if it knows 77. In this case, the lower bound implied by this strategy is X(7). somewhere between 1)' and 2.
We outline the approach to derive the bound implied by the above adversary. Suppose algorithm A knows the adversary's 'ss strategy and the value of 77 upfront. Effectively, A has to decide: (1) x n, O S x & 1, the number of large jobs to finish before time 1", (2) y n, 0 S y S 1, the number of small jobs to leave t², and (3) e, the total time allocated the unfinished small job group before t*. We can show that these three parameters (I, y, e) represent all candidates for the optimal online schedule against this adversary. This claim follows from two observations about the optimal schedule. The first is that the number of intermediate jobs is determined by (1-z (1---y) 12----)nn .n, with total of t' (πр) rn time allocated them, and is optimal for A to equally share the processor among all the intermediate jobs, i.c., every intermediate job has size ['-(pp) (1-2-2) The second
observation is that it is optimal for A to bound 0 < < p/1 because the time allocated to small
15

---

Published as a conference paper at ICLR 2026
jobs can be aggregated and used to yield more intermediate jobs, which favors A e 2 p/n. Then, is optimal for A to concentrate e unit of time on one small job before t*. Let I be the adversarial
instance. We have: A(z.y.)) (I) mpm + np(1 z) + pn²) n² + mpx + Py ey) -n
and (pt(a..)e =
2n pu(2 y) + _m|=2² + (3 - x1 + - w))) n2² + m2 + 1 Py
1
2e(1 + - v)) n2 2e. Then, algorithm A considers the following optimization:
A A(x.v.e(
min a.g.
(pt(a.y.e) (f)
1 1+ max 0, n²x + (1 x)
27
e1
P
s.t. S S
S
V
S
S
e <
77 pm
17 1+11"
n
where the bound for y comes from that every intermediate job must have a size of least p/n n/n.. Let 2n(a). -(r, y, t) be the coefficient of n² (i.c., the highest order term) in (1) (x.v.e) (1);
p
we have: 11x y. 1) = y² (nt + 1 + + 1) + (-rfSta - 1ftx + 1121 2xp 21) + (11210 + 1 22 2n x 2ny2). 2, Showing some bound M is the minimum for lim Opt( (T) reduces to showing (ar, y, M) 2 O. Observe that h is strictly convex in and y. Therefore, with any fixed I, the minimum of occurs at either the boundaries of y or at ÿ = =( -======(++2+2)
Ala.v..:())
Similarly, with any fixed y, the minimum of h occurs at either the boundaries of a or 3 pyy ny-nt+tp+2 Given these candidates for the minimum, we can show that h(x, y. n) 2 0 for 17 S n²" h(z, v, X(n)) 2 0 for 17" ") S 1 + v3, and h(r, y. 2) 2 2 for vj > 1 + v3, which completes the proof of the Theorem.
20++1((e-1)
2(++1)
PROOF OF THEOREM 4.1
We introduce the adversarial strategy first.
Adversarial strategy: Fix any 1) > Pick a large enough p and n. The adversary presents
the following problem instance I: jobs have non-increasing sizes pt 2 p2 > 2 ph where
PJ E [p/n, npl.P; = p, VI I j I n, and a tiny job Jn+1 with PT+1 = Pa+1 = = < min g p P }- It lets any algorithm A processes jobs for t* = (Tp) -3'n time, where 3r = 1/(1 + 1). A job is completed (immediately) if and only if has been processed for up time. These jobs are called large jobs. At time t", the adversary sets Pj x (t") + E if job Jj has been processed for 23 (t)(t) 2 p/n time with a very small positive + 0 (called intermediate jobs), or P5 = p/u if x (1") < p/n (small jobs). The very small positive and are set so that (e+ =)n is less than & times any small positive constant; then, the contributions of and to the competitive ratio can be controlled to any arbitrary precision. Therefore, we treat them as 0 in the analysis without affecting the results. The number of jobs n will be set large and properly enough so that n is (at least approximately) an integer. This adversarial strategy satisfies the requirements for smoothness analysis.
m++1
7
Lemma B.3. << n() < P(())
Proof. Observe that max, P 2 p/n while min, p3 = p/12². Therefore, P(T) 2 p/u 122 > The lemma holds with 1) > 1 by the choice of 17.
p/g p/T
Consider any scheduler A. We give two advantages: (1) after time t", A schedules the jobs optimally, i.e., it knows the remaining job sizes at time 1" so it can run the jobs via shortest remaining job size first, and (2) after A decides the parameters (x., y, e), sequentially runs the an large jobs first in the t* period. Therefore, the following analysis operates
lower bound of A()).
Suppose algorithm A knows the adversary's strategy and the value of 1 upfront. Effectively, A has to decide: (1) m, 0 < x < 1, the number of large jobs to finish before time t", (2) y n. 0 < y < 1, the number of small jobs to leave at t², and (3) e, the total time allocated to the unfinished small job group before t". Since we treat
Scheduler A:
E = O, the scheduler finishes the tiny job for free and all the intermediate jobs at t* From t" onward, the scheduler runs the remaining small jobs via the shortest remaining job size first. Lemma B.4 shows that these three parameters (ær, y, e)
16

---

Published as a conference paper at ICLR 2026
represent all candidates for the optimal online schedule against this adversary. We will later refine the ranges for these three parameters.
Lemma B.4 (Canomical representation), Fix > 1 and let be the adversarial instance described above. For any online deterministic algorithm A, there exists an algorithm with the same smaller competitive ratio, where any schedule produced by which is determined by three parameters:
y,yee satisfying 0
x 0 0 S y S 1, 10..eeee S
where (1) xn large jobs are already completed at time t², (2) yn small jobs have received units of processing in total; that e is concentrated on one of them, and (3) the remaining (1 I -- y)m
intermediate jobs have each received exactly (1- (1-x- yym
(-(mp))ane units of processing by t*.
Thus, the triple (z. y, e) enumerates all candidates for an optimal schedule against the adversary.
This claim follows from two observations (Lemmas B.5 and B.6 about the optimal schedule. The first that the number of intermediate jobs determined by M (1 I y)n, with a total of Tar 1x 1-- (mp) -27 (27
e time allocated to them, and it is optimal for A to equally share the processor among all the intermediate jobs, i.e., every intermediate job has size Ts. The second observation M
that is optimal for A to bound 0 S e < p/n because the time allocated to small jobs can be aggregated and used yield more intermediate jobs, which favors A e 2 p/n. Then, it is optimal for A to concentrate e unit of time on one small job before t*.
Lemma B.5 (Equal-share property for intermediate jobs). Let A be any deterministic online algo- rithm and be the schedule it generates up to time t" against the adversary. Denote by I(o) the problem instance the adversary finalizes after observing a. Assume a is described by (x, y, e) of Lemma B.4 Then there exists another algorithm A' that coincides with A except that, during [0, t"), it shares the processor uniformly among the M intermediate jobs, giving each exactly Tax /M units of processing. Let o' be the resulting schedule (up to time t* and I [o'' the corresponding instance. We have:
A(T(a)) (T(O')))
(pt))(o)) Sptt
and therefore:
(T((o')) Opt(T(a'))
A(T(O))
S Opt (T)))
Hence, without loss of generality, we may restrict attention to algorithms whose schedules equal-share the processor among intermediate jobs by time t².
Proof. Let Wi...., WM be the amounts of processing given to the M intermediate jobs by time t* in o. Ei=1 w; TM. Without loss of generality, 8j < p/n) be the processing each of the S = yn small jobs has received; thus Σÿ 8, = e. After observing a at time t", the adversary finalizes the true job sizes and the remaining work is:
sort W1 S.. WM. Let $1,..., 85, <
(p/n - (o/n-si),.... si)..., (p/n 88)
S items
1. The algorithm's cost does not depend the individual wi.
Observe that the contribution of the intermediate jobs is t" M to the total completion time, which does not depend on the vector (wi,..., WM). After the intermediate jobs are gone, the instance consists solely of the S small jobs whose remaining sizes are (p/n- - si),..., (p/1) - ss); these quantities are independent of the w;. Therefore the cost of A that comes from the small jobs depends on ($1..... ss) but again not on (wi....,
... War). Combining the parts,
A(((a)) Charge + t + F(......,
where Chage is the cost of large jobs completed by 1x and F is a function of the small-job resid- ual vector only. Hence A(((o)) depends on M and the multiset {sy}. but not on the vector (Wi,... W.). Therefore, for any other schedule o' with the same (xc, y, e) (hence the same M and {sy)), have:
A(T(O)) A'(T(o'))
17

---

Published as a conference paper at ICLR 2026
2. Equalizing w; increases the offline optimum.
The offline optimum runs the jobs in non-decreasing order. Under the adversary's 's sizes that order is:
p/m....... ./n,. Wi..... WM TP...... TP
small jobs
M intermediaae jobs
L large jobs
where L 2m. Let d(w) ش== (M jj 1) wy.. Write:
Opt(T(o)) = Csmalll + Clarge + 2S5 + ((w))
where Csnall S(S+1) Gurge M,S, L, TMr but independent of how the total TM is distributed among the w;, We bound ((w) by Chebyshev sum inequality for oppositely ordered sequences:
(2S TM ) + up L(L-1) and P. S.M, all depending on 2 n)
((w) = - (M
M
Σ (M j+ j=1
M
w
M
TM
M
2
1=1
The maximum is achieved if w; Di= M w TM/M, V achieved by A'. Therefore,
M + Tm 2 Opt(T(o))
Opt(I(o')) Csmall + Clange + SSS. +
Putting parts and 2 together proves the claim.
Lemma B.6 (Total processor allocation small jobs). Lei A be any deterministic online algorithm that equal-share processing for intermediate jobs and be the schedule generates up to time t against the adversary. Denote by [(a) the problem instance finalized after observing a. Assume described by the triple (z, y, e) of Lemma B.4 with e 2 p/n. Write integer and < c' p/n. Then there exists another algorithm A' that coincides with A except that, during (0,t"), it allocates e' time on one of the small jobs and 0 time on the other small jobs and sets yn- small jobs, i.e., increases intermediate jobs. Effectively, the characteristic triple for the schedule generated by A' is (I, -z/n,e") e'). Let of be the resulting schedule (up to time (*) and I (oo' the corresponding instance. We have:
p/n e', where is
A(I(o)) 2 (((o'')),
((p((G)){(p(((T'))))
and therefore:
A'(((o))
A(T(o))
(p(()(o')
Opt (T())
Hence, without loss of generality, may restrict attention algorithms whose schedules allocate e < p/n time to small jobs and to just one of them by time t*.
Proof. Let Wi...., WM be the amounts of processing given the M (1- y)n intermediate jobs by time t" a, so EM w; = Tas- Let $1...., S5. (0 < s, < </n) be the processing each of the S yn small jobs has received; thus Σ Σド= 8j Without loss of generality, sort wi .... < and < ... Ss.. After observing at time 1", the adversary finalizes the true job sizes and the remaining work is:
(p/n $1). (p/n sg)
S items
Let L = on and Tv 1--
We can write:
LiL 11
S +
A(l(a)) = vp
(
+
Σ
8j
2
intermediate
j=1
large
small
18

---

Published as a conference paper at ICLR 2026
and
P S(S + 11
P SSM +
TM
M +1
P (S++TM)L + (mp)
+1
Opt(1(o))
2
M 2
2
small
intermediate
large
For A', the number of large jobs remain I, = the number of small jobs becomes S' = S y'n = yn - 2, and M' = M + (1 I y)m + 2, and Ty = T'r + = After observing o' at time t", the adversary finalizes the true job sizes and the remaining work is:
p/n.... p/n. (p/n e¹).
9 items
We write:
L(L + 1)
PS +1)
Al(((')) = 7p
E' +S' +
2 ESS
large
small
and
Opt(I(o')) p (S' + 1)
P S'M'
Ty M' MM' +1)
ELs + L + (np)
L(L+ 1)
M'
2
2
small
intermediate
large
We have:
A(((O) - A'((0'))
PSS +1)
PS + 1) + e'S
= - M') (8 - "S')t"t"
Σ
j83
17 2
1)
(2S - - 1)2
S Ejsj
" 2
j=1
8
L(s + + 1)) + (S 0(($==)) +1
-Ess jsj
11
j=1
max y sy 20.
20 and
(a(((())-Opp(Lle)
12 + - S'(S" + +1) + 2(S S'M') + 7 Thr + 1) (MM' + 1)]
2n
+ + 8') Tw L
p2 (2S +
p2 (= + M -S)
TM + 2 p
11
pz (2 (2+ 2M +
=TM
p2
(M + +2+1)
2m
2
2n
2 M 7
Tm)
P P M < TMr
0
(every intermediate job has size at least
rj n
Proof for Lemma B.4
It follows from Lemmas and
B.6
19

---

Published as a conference paper at ICLR 2026
We now refine the ranges for 2, y, e. Before t* (7 the scheduler A can complete at most
8"n large jobs, so x S 3". There is an upper bound of 1- 3 on y. since yn 2 (1- 3" )m + 1, the total processing of jobs prior to t* is at most (n- ((1 3 )n f 1)) ()))-(1p))))))))))))) (mp) + (8 - 1) (np) + <
(n = t*. This contradicts with that scheduler
has processed t" amount of time on jobs.
Finally, by the setting of adversary, we have Tae M 2 + r" ("-(mpla-e x² 147 + en Thus, we formulate the feasible range for the triple:
P + y y n² + (1 (1-x)-
(1-x-1)m V)n
pn
s 1+1
max n²xx + (1 - x) 1+
S pm
7 7
H c -
Let A be the online algorithm that minimizes the competitive ratio against the adversary. By Lemma B.44 the schedule can be determined by three parameters F, e. We can write A(1) and (P)(T) under any given choice of (x, y, e). denoted by A(x.,.e) ()),)))()) and (pt(n.n.e) Let = zn,
yn, M (1 x v)m, mp, s 7. and m (c- (C'-(xp)en-e en)) We write:
(I-x yjn
A(x.n.e( (T)
[[I 1)
S(S +1) eS
M
+
intermediate
large
small
(Ir) ( (en
t" (1 x y)n + (ym) + p (yn)(ym +1)
np
e (ym)
7
2
intermodiate
large
small
np
2
xm 2
+ 8 up (1 x y)
yppnn +
p
y
2
+
ym
2
- eyn
intermediate
large
small
1
1
= 1 mpx² + +3 - x) +
pbj 2
n² + (,1100
+ 2
py - ez) .1
21)
211
and
Opt(n.y.e) (I)
S(S 11)
+ +SM + m M(M +1)
+&S mM) 1 +1 L(L+1) 1)
2
2
small
intermediate
large
(ym)(yn + 1)
(yn) ((1 -x x -x--1-1 n) + m ((1 r - 4)m) - x - y)n + 1)
2
2
intermediate
+ (s (ym) + m ((1 - x - y)ni) (an) + (xn)(xn +
2
large
g y n + yn + y(1 - x n) 22 + (np(3* - -x)n e)
(1 - x - 4) +
2
2
(gyn + 1p(33 - x)n - e) xπ + mp 2²112 + xnn
+
2
1
1
1
(2 - v) 2 mmla (88 - (1 + x - U)1 n² + nn
py
e(1 y))n
2m
2n
2
We consider the following optimization:
min A(a.n.e((T) (T) 2.9.0 Opt (p(
(3)
20

---

Published as a conference paper at ICLR 2026
s.t.O S x 1+
max 0, 7f + (1
x)
+
-
c <
P
n
+
We will show the following bound, which will prove Theorem 4.1 Lemma B.7. For Optimization 3 we have:
(1)
7
lim 1L-00
X(1),
"f 1j S 1+ v3
(pt(a (T)
2,
n>1+ v3
for any feasible (.). where 77 is the positive root of xt 4r - 4 = 0 (1) ~ 1.835), and
X(7)) 2n n² +-- / (1+ + +9/2
44 48
Our proof structure is as follows. Observe that terms A(z,y.e and (a. (7) are quadratic in n and the coefficients of n² are positive for any feasible (zt, v,y)). e). The adversary can set suffi- ciently large n so lim Opt(r.p.,)(1) and denominator. Write the coefficient of n² in A(H,y.e) (1) - tettppppttpg (pt
A( equals the ratio of the coefficients of n² in the numerator
(1 1
1 (/ +.3 3ppppp11 - 2) +
1 py²² t
1 py(2 2 y) + 2 nmlm=² l2² + -8*- x)(1 v)
1
21
21
[y² (np + + y-n (-1²tx
rpt + 1 2np - 21)
2n(11 +
(n + - -2t 27/²x + 2n²)]
(substituting 3 = 1/(11 + 1))
h(x,y. v.
27(11 +
where h(2, v.t y² (nt + + (-1pto 27 + n/²t 2nyt 2t) + (112tx x
n12 x222 277xx r 2n²)) ). Therefore, showing
Acanne))) 40000 (p. (I)
lim
2t
for some is equivalent to showing
h(2, y, 0
Notice that the expression depends on x and but not e, which is intuitive as only affects a small portion of processor allocation. Observe that h is quadratic in x and y, if the other variables are fixed as constants. Therefore, with any fixed v, the minimum of h occurs at either the boundaries
of y ÿ *(n"² 2"0===="""20
Similarly, with any fixed y, the minimum of h occurs at either the boundaries of x ā gtw-nttty-2 To see this, write h(z,v,t) x² (17 + + 2(++1) (-nity + n²'t - ty - 2n7²) + (y²tty - - 2n² + ntyy 2nty + ny² +ty² -ty - -g²). Given these candidates for the minimum, we can show Lemma B.7 discussing three cases.
2(1+1)(++1)
2ty-+yy
Lemma B.8. For Optimization we have:
lim (1) (1)
7, 17 1
1-000
Opt
for any feasible (I, e),,, where T7" is the positive root of x² - 4r - 4 = (1)" ~ 1.835).
Proof. We show that the claim holds for < x S + < y S 7- E < g, which relaxes the range for y. Thus, will hold for a more restricted region. Write:
11
h(,, n) 3² (1 + 1)² y 7 (11x + 1 1² + 2m 2) + 12 (n²2 + np² 1) + x² 22 + 2)
We show that h(2, y, n) 2 where the equality holds when (z, y) = (++ , Notice that
- - y - 0. 1 implies that the processing must be all allocated to the
21

---

Published as a conference paper at ICLR 2026
large jobs by time t", there will be no intermediate jobs and 0 time allocated to small jobs by time th. Given any 2, we have h(1, y, 7) 2 min(h(r, O, 7). h(z, n+1 n), h(x, 9. n)). Given any y, we
have 11z;, ys m) 2 minfh(0, v. 77,, h( I V. h m))
Case 1 (y 0). We have:
h(2, 0, 17) n/² (n'2 x na² 17 -2 = r²² ((7) - 1)x² + (17² -2)x + 2 - n)
-2r
Case 1.1 (y 0, x = 0). We have:
h(0,0,n) = (2 -2 >0
for S 11 (1)* 2 1.835).
Case 1.2 (y 0, x ) We have:
h( 17 + 1 0,n) n7²
1
1)( ) ( -2) 1
) +2 -n) 1) = 0
17 7
2-1² Case 1.3 (y 0, ã 2[n+1)
We have:
h( 2 2-11 1/2
112
2 2-11 + 2
00 .0.7)
17²
(1 1)( 1)(((1
)2 + (17 2)
+ -1)
2(17 + 1)
2(17) + 1)
1/ (1/² 4n - 4)
2 0
4 (17 +
if 17 S '7"", which implies 17 4n 4 < O. Putting Cases 1.1, 1.2, and 1.3 together, we have:
1
h(2, 0, n) 2 min(h(0,0, n), h( 17
0, ((.
Case 2 (y ,4T). We have:
h(1, n 1 7) =
"
17 (m 1)2- 1
7+1 17 ( 122 n² + 2m + +2)
17
+ 12 (122 x + np²2
1 x² 2x +2)
= (1) + 1) ++1 220
where equality holds when (z. v) = |+ m+1
Case (y- = - = " 22 2 +2n+2) 7(1 2111"2+0²² x 2 x x- 2 +2n+
We have:
1(1+1)(++])
2(0+1)=
M(x, G. (") (112x 1 + n2x - 12 + 21 + +2) 2 + 1)²
2(n + 1)?
n (1fxx 1 + 12xx 17² + 2m +2)
17 (17 x + 17 1/² + 2n+2) +2)
2(1 + 1)
+ 1 (1²xx + np? - + x.²
2r + 2)
7 (n² 4n - 4)
1
82 2 0
17 +
where equality holds when (x.v) (, +
Putting Cases 1, 2, and 3, together, we have:
(x,,v.)) 2 min(hle 0), Mxx
M), 20
n7
22

---

Published as a conference paper at ICLR 2026
Before we show the case for 17* < 1711+ v3, need few bounds for A(1).
Lemma B.9.
" S Mn)) 2
for 17" < 17 I 1 V3, where n² is the positive root of x 4x = 0 (1)" F 1.835) and
X(1) = 2n +1 499
4'444488044
Proof. We first show that X(1) increasing in [n]" + v3). Differentiate À with respect to rj and factorize:
2 (1) 2n - 2) (17 + 2n + 2) N())
((1) dn
/1 + 1 (1/² + 4nf + 87 + 4)² 21 + nj² + 91/² + 167 + 8
where:
(1)) = 17" +1² + 5nj² + /7/22/ + 37 + 10,y + 25 + 247 + 8 87 + 4
The sign of 4 2n X(1) is determined by -11²² - 21j 2) = (x v3 1)((1 v3) - x). Therefore,
d
((1) n¹ < n 1+ v3 dn
and, thus, A(1) is increasing in [n", 1 Then, to show the claim it suffices to show that X(7) if 17 = '7" and X(n) = 2 if 1 1+ v3.
Case 1 (A(n) 17 if 17 = 17"). Let 17"' satisfy (11*)* 4nn" +
Substitute 17 = -7" and use
(n²)* = 417 + 4. We have:
2(n")*² + (n1)² + )()") 167 +8 =2(4n +4) + (17")3 + 9(1")) + 167" +8 8 = -ni" + 1)(n" + +4)2
Therefore:
A(n²) 2n (17 + 11" + (17" + 1)(r) + 4))
(n" + 11)"" + 4(1" + 1)( + +2)
1j"
4(1)" + 1)(11" +2)
Case 2 (A(1)= 2 if 1 v3. We have 77² = =2n + 2. The denominator of À becomes
n7² + 4n7 + 8n + 4 = (2n + 2)² 4n² + 81 + 4 = 8(1 + 1)?.
Next, compute the radicand in the numerator: 2n + n7 + 917" + 167 + 8 2(2n + 2)² +2) + 167 +
+ 812²
16n 8 (2n)² + 2n) + 9 + 161 - 8
-19/² + 34m
181" + (2m + 2) + 34n + 16 18(n 1)
We have:
A(1) 2n1 + 3(7 + 1) 2(n 1))
2n(11 + + 3(1 + 1)m)
n/2
1/2
=
8(7 1)2
8(1 + 1)2
7
1/22
Lemma B.10.
X(1) S 7
for 17" < 1 v3, where 11' is the positive root of x² 4r = 0 (n) ~ 1.835) and
X(1) 2n 1o(""+n-o + / (1+1)(22** 408 +16+45))
17 444 48044
23

---

Published as a conference paper at ICLR 2026
Proof. To show
2n +1 v () 1/ 9r2² 16n + +8)
17t + 4nj² + 817 +4
It suffices to show
2 - + 8) - (1) + 41/ + 8n + 4) - -21 + +1)
+ 4 + 1) +1² + 9n + 167 + 8) - (17 + 2n + 6n + 4)
+ (1) 4n - 4) (1² + 41²² + 8m + 4) 0
which is trivial as r/" <n <n 1 11144 0) Lemma B.11. For Optimization 3 have:
lim A 2 X(1), n¹ <n51+v3
(ptiz.g.e)
for any feasible (e.,,e), where of is the positive root of at 4r - 4 = 0 (1) x 1.835), and 2n 1² +n +2 +16
Proof. We show that the claim holds for 0 < x S 147. 0 7 S e < f, which relaxes the range for y. Thus, will hold for a more restricted region. Recall that h(z, y, t) x² (17 + + +
(-1"tty + 17't - tyty - 2n/) + (1²ty - 172t + 21/² + nty² 2njy + nH² + 2ty y²). We show that h(z, y, A(n)) Z where the equality holds when (x,y) (0, X
(,, Given any H, we have (2; 1) 2 min(h(2, 0, t). h(r, :) h(x, (x. (). Given any we have
h(z, y. t) 2 mh, y. t), h( ++ 9.t)
Case (y- = 0). We have:
h(2, 0.t)
x² (172 + 1/²) + 2))) (-1 2n²2)
= =12 + 1)x² + (np - 2)x + (2 - 1))
Using Lemma Therefore,
B.9 we have A(n) 2 2 2 2 2 and 17" < <n,1" S A(n) = nd(1) > (17)²
ha, (,n))) - 17n + l)x² + (n\(1) 2)x + (2 X(n))) >0
Case 2 (y n+1). We have:
h(1, n + 1" .) = -11² + 277 + 17) x² + (-2n7² 2n) + 2n²² 2nt + 3n 2t
1)
Case 2.1 (y 91
1 O). We have:
100 17 A(1)) 21₁² 2nA(1) 31 2X(r) 2 2n² -2n1² + 33 2n 1) 0
where A(7) 5 7) is by Lemma B.10
If y म we have ã nty nty-
1/ " m m1 +2
Therefore, we are left with
2(++1)
2(++1)
m+1
one case consider under y TT
Case 2.2 (y- 1+ T. = 7+ ). We have:
h( 7 + 1' 17 + 1 1) = (17² + 2n² + +n) (,tz))
17
)2 (-2n² -2n) + 2nj 2nt + 3m 2t (2
24

---

Published as a conference paper at ICLR 2026
= 27(17 t)
Therefore,
1 7
h( 17 + 1' ((n)) = - 27)) 0
for 1/" <.
Putting Cases 2.1 and 2.2 together, we have:
h(z, u A(1)) min(h(0, न M())),))))).))))). h( 1 w 7fI X(n)), , 20 0
Case 3 (y/ = - =(1"0+0pp x x ,t = X(1)). We have:
2(1
h(,,8,1) 1 (17% + 11² - 17² + 21 + 2)
(' + 1)2
2(11 + [) + 1)
t (112x 2p25 1/2 21 +2)
17 (17 x + n22 - n7 + 2n + 2)
2(1 + +)( 1)
+ 1/ (1²xx + np² - + x²² - 2x +2
Case 3.1 (y = -- = 1(1"2t1)²= +2
t= X(n), x = 0). We have:
2(n+1)(++1)
h(0.
((-r)+20t2) (m 1)² - 1(-o2+20+2)
2(n+1)((++1)
177 (-1² + 2n 2) + 77² (-n) + 2)
(-1)
((++1)(++1)
(-n)² - 4n²² - 8m 4) 1² + (4n + + + 871² + 817
(1 + (1+
The equality holds because A(7) is the positive solution to equation (-1₁² - 417 - 81 - 4) x² +
(4n}² + 4n7² + St1² + 811² = 0. This can be verified via the quadratic formula:
-(4n1 + 4n7²) v (413 4n22)² - 4 (-1p² 41p2 8n - 4) (81p3 + 8172)
2(- 41² 8n 4)
(41/² + 4n7)) + / 16n2 (1) + 1) (21 + 173 + 9112 167+8)
2 (11² + 4x1 + 8n
2n (1² + +1 v + 12 + 173 9722 + 167 + 8)
A(1))
1 + 4172 + 87 +4
Case 3.2 (y)
1 = A(11) (+1) We have:
+[++1)(++1
113 I+I
1 + 1/2 I+I
1 x + 21 +2)
1 7 17,
(,,1,,11) 1) =
)2(1) + 112
2(1 + 1))
(1i² u+R
1 + 11² 7+ - 1/2 + 24 +2
-17 "n(11" u-ा +1² nt1 -1² +7+22 +2 +2)
2(1 + 1)
n (1p n-4
1 + 7( /11 )² -1 + ( (p+)) 12 2 - +
(1) 1) (272t + 2n2 + 2nl + + + t)
(1 + 1) 11)
Therefore,
h 1 M. v, (.n)) = (n-\ X 2n
+ +2 (1+1)
+ + -(n)) 0
25

---

Published as a conference paper at ICLR 2026
for X(n) S 77 by Lemma B.10
We then show that under y = V. x
2
1 7t1+ so this case does not need to be handled.
of 2(1+1)(++1)
Case 3.3 (y - D
t = X(n), x = .).
We first derive the expression for म as a function of r) and t.
y4 +
1(++1)
2(1+1) [(nt + t1ū + 14-2-111 1y1]
(nt 1) (111((+t 22 1j +20++2) 2 1/
2
2[++1)(++1)
Solving for vt gives:
- 2(2
3
(1 +
However,
m+1 (2 172) + 1jjt +
1
(n [) - 1/
11
21 (1)-))
(1 + 1) (1/p2 4t - 4)
Observe that 17 A(1) 2 0 and
(22(()))2 - 4X(1) - 42 (X(1)) 4X(r) - -420
where the first inequality is due to Lemma B.10 and the second due to A(n) 2 77" (Lemma B.10 Therefore,
n+1
The case does exist has already been taken into account in Case 3.2.
Putting Case 3.1 and 3.2 together, we have:
Ma, 0, A(n)) 2 min 8, A(n)), M()) A(n))) 2 0
Lemma B.12. For Optimization 3 have:
lim A(c.g.e (1)
2 1> 1
n-00 (pt (T)
for any feasible (I, N,,y,e).
Proof. We show that the claim holds for 0 S x S 1 < < 44.0 S < L. which relaxes the range for y. Thus, it will hold for more restricted region. Recall that h(x, y.t) I² (n² + + + x (-n'ty + n - n2ty- - 2nn)) + (r²ty n 2nj² + +nyy 2nty + my² +t² 2ty + )²). We show that h(x, y, 2) 0 where the equality holds when (z, y) (0,0). Given any x, we have h1x y. t) 2 min(h(a, O, t), 11( ...)), ...,t),fee h(x, G. t).. Given any y. we have h( y. 2
min (h0, y, t), h( -ir 8) (65, y, t)).
Case 1 (y 0). We have:
h(x,0, 0,t) 112(1 + 1)x² + (nt - 2)x (2 t))
26

---

Published as a conference paper at ICLR 2026
Therefore,
- nf(()) 1)x² - 1))) 20
Case 2 (y/ = ) We have:
h(x,
17
2) -17 2n²² 1) x² + (-2n² 2n) + 2nI² 1l
11 7
Case 2.1 (y 1 = 0). We have:
h(0,
17 2) = 2n1² - 17-47 -
+
for 1) > 1 + v3 If
we have 5
1 7 we have one case left under y _ 7+r*
Case 2.2 (y
n q+1s x
We have:
7+
h1
1 1 2) 2n(1 - 2) 2 0
for 1) 1 v3. Putting Cases 2.1 and 2.2 together, we have:
h(1, mtI 2) 2 min min( -=I: 2), M 7 . 2), M o4T 2)} 2 0
Case 3 (y = --= (0" 3(m+1)
(17²00 + +1/ 1/² + 21/ + 2)
M(,, 0.
(² + 1)2
3(1 + 1)
(1fxx + 17 1/2 + 2m + +2)
.1) (1722 + n²2 2
+ 2m +2
3(n + 1)
+ 2 (12x + qn² + x² - -xx 22
For this case to exist, we need 5 2 0. This implies:
(17xx x + 17 x 7/2 + 2m + 2)
1 27 - 2
20=x>
( (1)+))
17 (1 + 1)
Therefore, the range of a: becomes
22-22-2 7 7+11
Case 3.1 (y - (2" 2
11221-2
3(7+1)
(((+1)
h( 2 27,2)
7-(++1)
(n7² + 1 ))
22-2112 - 1/2 2n +2)
[
)² 1)²
3(1 + 1)
(173 + 2) 22-
112 2m +2)
(n+ 1]
17 (17² + 17²) )22 2n-2 1/2 + 21 + +2
3(1 - 1)
(1
+ 1? (?2 222222222
+ n 122 22 )22
11 + gg 2-2n-222
2 2 2 +2)
[(++1)
()+
((++1]
(
(n² - 2m - 2) (2my* -1² 2n - 2)
2? (1) + 1)
27

---

Published as a conference paper at ICLR 2026
With 17 1 + v3, we have 17² 2n + 2 and
21²² 1/² 21y 2 > (2 + 2) -1p² -1f-2n 2)
2n
2 = =1² 2 > 0
f) 1) 1 + v3. Therefore, have:
( 16 22 2n- 2) 2
Case 3.2 (y -ÿ= x- 0-
3(m-1) 1)
1 7
h( 7 (.
(11² + ,p) n+I 112 + +1)1+11 +2)
)² 1)2
3(17 + 1)
(17² + 7²²) 741 111² + 21 +2
17 (17) + +1²²) n11 - 172 + 2n +
3(17 1)
+ 17 (12 1+4 + n
1
- + ( -2 2,, + +2)
(17 2) (6n) + 5n + 2)
>0
(n + 1)
for 17 > 1 + V3.
We then show that under y = U. x
7+1 so this case does not exist.
+2
Case 3.3 (y =
t 2, x .))
3(1-1)
We first derive the expression for ã as a function of v and t.
ní #
+
2(++1)
(n+1) -33
However,
1 +
1 + (1 + 1) - 3)
1
17 n
f
7
(1 1) (1p 3)
The case does exist.
Putting Case 3.1 and 3.2 together, we have:
h(x, (.2) 2 min 22 2.. 1/ -0,)) 20
(f
Remark 1.13. Bound in Lemma B.12 is tight as 2-competitive algorithm (i.e., Round-Robin) exists matching the lower bound.
Proof for Lemma B.7 It follows from Lemmas B.8 B.
and B.12
Proof for Theorem 4./ It follows from Lemmas B.4 and B.7
FIRST ORDER APPROXIMATION FOR BOUND A(7)
Remark 1. We have A(7) 2 0.187 + 1.5 for 17" T) < 1+ v3, so the piecewise smoothness
bound Theorem 4.1 yields (n))) 2 0.18n + 1.5 over (1) 1 V3).
Proof.
X(n) 2 0.18 1.5
28

---

Published as a conference paper at ICLR 2026
21 +1+ +y
97/² + 167 + 8)
2 0.1887 1.5
4 167 8) (0.181) 1.5)(1) + 417² 8n + 4) -2n(11² n)
2//
4n + +8)
(0.181) + 1
+ 5.447// + +12.2 + 6.0)²
+ 8r)" 12n + 39.827 / + 97.28t/ + 26.56n/ - 12.72n - - 6.0
+ P(n) 0
where:
P(n) 0.03244) 0.54n) - 1.7892.7* + 9.881617/ 10.53767 13.6064r)
+ 84.9696n) 27.03367) 195.0784n - 152.64n 36
We show P(n)= 2 0 for all r E (n", 1 v3J. where 77" is the positive root of x 4z 4 = 0.
Since P polynomial, it is continuous and differentiable over [n] 1 + v3). On the compact interval (7", 1+] its global minimum occurs at either the boundary or at a point where d P(r) = dyj
We compute:
d P(n) = -0.324m - 4.861 14.31367 + 69.117227
63.225667 + 68.0321
dn
333.87844) 81.1008r) 390.116877 152.64
Numerically solving dn P(n) in [n) 1 v3] yields one real roots:
R 2.475
We compute (to high precision):
P(n') = 25.154. P(m) = 952.345, P(1 v3) x 305.734
All three values are strictly positive. The minimum of P on [1]", 1 + v3) must occur at one of {n" m, ( 1 + v3). Since P is positive at each of these points, follows that:
P(n) 2 0 for 1) E [,",1+ v3)
ON SMOOTHNESS METRIC
We demonstrate how refined smoothness metric captures valuable information that the classical definition misses. Focus on the regime 17 < ny,, for which we proved the lower bound ()))) 1/, with equality attained at (x, e) 1+T+ - 0) against the adversarial instance.
Under the classical smoothness model-wher all predictions allowed to be identical (p) p for every j) and hence carry no additional information-thh example tells us that any sequential ordering of the jobs might achieve the bound. Any algorithm that completes the jobs (randomly) sequentially will experience the first 7+ ones revealed as large and the rest as small. That gives us no guidance to the optimal ordering. In contrast, our new smoothness model includes a vanishingly small tiny job, foreing an adversarial instance where finishing that job soon does matter. In this setting, the example singles out the policy that respects the job size predictions, i.e., the algorithm should process the tiny job (with the smallest job size prediction) immediately, thus recommending scheduling policy that leverages job size predictions rather than leaving us with an arbitrary choice. Therefore, our refined metric turns a vacuous "any order works" statement into meaningful pointer toward the Shortest Predicted Job size First (SPJF) scheduling.
PROOF OF THEOREM 4.2
Proof for Theorem 4.2 We show that Shortest Predicted Job size First (SPJF), i.c., running the jobs sequentially from the smallest job size prediction to the largest, is co-competiiive.
29

---

Published as a conference paper at ICLR 2026
Fix any problem instance I with prediction error 7/ Assume without loss of generality that pi < $ P;. Define d( to be the amount of processing job Jr has received by the completion of job Jj for any pair of jobs (i. Then, we have:
" A(I)
Σnj pj + j=1
E
(
Isies5n
Observe that d(i.,) + d(j.)) 1) = p. if Pi < Py and that d(i. j) + d(j,t) 1 P3 if 2 Pj. for any
i < j. Notice that p}- S mp, S mp, S npp; if 2 Pg.
We have:
R
n DJ
A(T) S pj
Σ
Σ
Σ
Σ
P +
Σ
(03
(1-
==1
S
j=1
iSisisn P.2ps
Pi<Pj
P:2Py
x Opi((T) Σ
(r'pt - pt) S +1)
Σ
a 12 .
ISicjSn PiZPs
I<icjsa P:2P/
C PROOFS FOR SECTION 5
Notations. Running algorithm A against problem instance / produces a schedule, a which specifies which machine processes which job given any time. The completion time of J, in schedule a is denoted by CJ. The makespan of schedule a is C = maxisssn Cy. The
cost incurred by A is denoted by A(I) = ohall) Let (1) denote the optimal schedule, (1) mina(s) Coll), where (I) denotes any valid schedule for instance 7. We use i.e., Ca'l
OI)(I)= C to denote the cost of the optimal schedule.
Proof Theorem 5.7 We partition the range for 7/² (n²² 2 1) into disjoint intervals and specify the adversary strategy for each interval. The partition is as follows: 17² E {1} U (1, (2, 31 ( U ...U (k- k k] U (k. k + 1 + U ... where k: 2 2 is an integer. We consider two generic cases.
Case (17 E (k- - - k). We create n = k(k - 1) + 2 jobs and k machines: pi = 12 and p3 = 1, j n 1, with p3 = n for 1 S S n 1- 1, and pk = Pn = for some small positive < é < 1. This problem instance belongs to I,, as vP machines, one can force any algorithm to allocate job J1 no sooner than time k: 1. This is because the algorithm cannot distinguish jobs in set S = {J1,..... .... Jn-1),
P VV
1 17. By re-indexing the jobs and
Ph.
the adversary can set the first n - jobs (from set S) that have been processed by the scheduler for at least one unit of time to be size-1 jobs. Thus, the earliest time J1 can start is no sooner than R(k-1) = k - 1. Therefore, the makespan achieved by the algorithm must be at least k- 1 1 The optimal schedule is to allocate Jn to M₁ and jobs J2, Ja-1 to the rest of the machines, each running exactly i of them. The optimal makespan is at most k + c. We have shown the smoothness s(A) 2 k-1+n for any > 0,
k
ktt
which gives s(A) 2 1+
1--1 KA 1 + T where the equality is due to n7² E (k- T k] and A is
an integer. It also holds that s(A) > + - 1+
- k
- 2 [T
Case 2 21² E k 16.k+1-2 DD. We create n = k(k 1) + 2 jobs and k machines: pi = 172 and - _2 E. 2 < S n n- 1, with pj = v for S j S n 1, and p" = P.. = e for some small positive 0 0<c< < 1. The following holds via similar arguments used for case 1. The problem instance belongs to Ig. Re-indcxing the jobs and the machines, one can force any algorithm to allocate job Ji no sooner than k=1 Thus, the makespan achieved by the algorithm must be at least x n The optimal makespan is at most 172 + e. Therefore, s(A) > 2 F
T where the equality
is due to 2 E (k, k + 1 } and & is an integer. It also holds that s(A) 2 2 1
1
E
1 1
30

---

Published as a conference paper at ICLR 2026
Proof for Theorem 5.4 Fix > O. Run SIMPLE (with e/2), treating job size predictions as job sizes with list-adjusting. We show that this List- adsjusijg SIMPLE (L-SIMPLE) satisfies the claim.
Let os, LS, OOPT be the schedules produced by SIMPLE (e/2), L-SIMPLE (e/2), and the optimum. Let Cmax (o) denote the makespan of schedule a and Cmaxe (o) that if the job sizes are replaced by the predictions, i.c., Cmax(o) = max;e|m] (m)) EjeN, [0) Pj: Cmux (o) = e ΣjEN.10] Pj. where [m]] = {l..... m) and No [i] represents the jobs assigned to M, in schedule σ. We have:
1 Cmax S mmax S (1 (1+66 +//2) Činax
7
I (1 + e/2) ( S (1 + e/2) 17 C
where Önaxx min, (o) and Cimax Cmax (OOP)) The first and last inequalities are due to that every job size differs by. at most, a multiplicative factor of 1j in different accountings. The second inequality is by Theorem 5.3 and the third is by the optimality of Cmaxx If 12² < 2, we have (msx((Lss) S Cmax((s) < (1²² +E- Cimax. where the first inequality is due to that list-adjusting does not increase the makespan. Schedule dLS is replicable via list scheduling with the job order of non-decreasing start time in oLS. Thus, Cmax (OLS) S (2 ) C due to the competitive ratio of list scheduling. Finally, list-adjusting takes constant time per operation, so the run time of L-SIMPLE'S is dominated by SIMPLE, which is polynomial in n for fixed 6.
D PROOFS FOR SECTION 6
Proof for Lemma 6.2 The adversary's edge is that jobs J1,..., Jn-1 are indistinguishable from the scheduler's s point of view. The adversary maintains a set of jobs J(t); initially, J(0) Jn J1 The adversary monitors (t( per machine M, at any time t, where 2z(6) is how long M; has been non-preemptively running job. The adversary wakes up at time & when 8, x. (t) = minj,eJ(1)) Pj for some machine M,; it sets the index of that job to be n - [[t)]] (so the job immediately finishes) and removes the job from (t). If the monitoring condition holds for more than one machine, the adversary sets the index for the job running on the smallest indexed machine first and then moves to the second smallest and so on until s; (t) < minJ, EJ(() P3 for all M,.
This adversary strategy works since the scheduler cannot distinguish jobs in ((t at any time t, even if it somehow knows the job sizes but does not know which size links to which job. The scheduler can learn lower bounds of job sizes as they are processed, but every job in J(() has a size no less than these lower bounds, leaving every bijection between (()) and (t))) == [pj]J, E [()) possible. The predictions also do not reveal whether a prediction is an over- or under-estimation, even if the scheduler has L(t). This is because the job size is revealed only when completed. The scheduler initially knows that some predictions are overestimations of the job sizes but does not know which until the last job with a size less than 17 finishes to realize that all jobs in J(t) have predictions no less than their job sizes in the future.
Property one in the claim holds immediately following the adversary strategy. We show 4, (,()) + Pi 2 (j) for any j < I < n via proof by contradiction. Let l, (a(() + smict)
Pj If l, < (f),,, at time tg. the job Ji running on machine Mm must be completed, as Sm(1) Em(r) (tx) = Sm()) (tx tz)) = p3 2 minJ,eJ(t.) Py. Then, it holds (1) = tz < tt( contradicting j < and
property one.
Proof Lemma 6.3 If any job Jj E Ti is completed on a machine from G; or slower, we have ti!xx O) t t. ()) 2 2 1 and the claim holds. It suffices show the claim if every job J E T; is completed on a machine from G1+1 or faster. Processing all jobs from T; on all machines in G+41 or faster must take more than one unit of time:
E,,en, PJ
max (ty() t,0i) J,
EMEU G. St
2 [T]
22k-i-1
Σi=+1 2 22k-2111 1
1 3t -Gil
31

---

Published as a conference paper at ICLR 2026
All jobs from T, completed machines from Gi+1 faster. By Lemma 6.3 it takes at least one unit of time for all machines in G5+1 or faster to process all jobs from Т. Thus, there must exist one machine, named M, E U G1, that processes at least one unit of time for jobs in T; by the pigeonhole principle. Thus, there exist jobs J, and Ji such that J1.J1 E Tú m(j) ml) r and ty( (t) 2 1. Running Ji takes at most unit of time: (y) (I)
Proof for Lemma 6.4
Case 1.
pi
I
2' 2
We also have ty( (1) by the first adversarial property.
&r
Therefore:
t ( ()() 2 ty( - ty ( 2 t (1) - ty(
2 21- - (4-0
2
Case 2. There exists a job J; E T; completed on a machine from G, or slower. By the second adversarial property, we have (o(i) Pjiuar/ m L ( Therefore:
(1 - 1:: 2 (ا( L (0-1))
Pj
pj Pjpma
= =t(()) - t, (1-11 +
2
2 2
mm(j)
8m(j)
Proof of Theorem 6.1 If C is the makespan achieved by algorithm A, we have:
C
(J(mima 2 ty (((()
(1,()=M)) t (x()x2) ... (I) -1((
k-1
k 1
(Lemma 6.4
Cit max
+ (5
2
2
By Lemma 6.3
we have (ibaax)
and:
k ++1
2 log m] +
CA
max
[log nl
2
32


Reviews:
[{"review_id": "DgH4SRMNJo", "reviewer": "Reviewer_PzFT", "summary": "The paper considers non-clairvoyant scheduling with job size predictions for two different objective functions, total completion time minimization on a single machine and makespan minimization on identical and uniformly-related machines. In non-clairvoyant scheduling, the actual job sizes are unknown and only revealed once a job is completed. In the setting with predictions, we have a-priori access to predictions on the job sizes. Such learning-augmented algorithm are studied with respect to their consistency (the competitive ratio for correct predictions), their robustness (the competitive ratio for arbitrarily bad predictions) and their smoothness (an guarantee depending on a prediction error).\n\nIn this paper, the authors propose an alternative definition of smoothness, which only requires error-dependent guarantees for predictions that \"reveal additional information\". The author study this notion for the error $\\eta$, which is the maximum ratio over all jobs between a predicted job size and an actual job size. For minimising the total completion time on a single machine, the authors prove an upper bound of $\\eta^2$ and a lower bound of $\\eta$. For minimising the makespan on identical machines, the authors show a lower bound of $2-\\mathcal{O}(\\eta^{-2})$ and an upper bound of $min(\\eta^2,2)$. For minimising the makespan on uniformly related machines, they show a lower bound of $\\lceil\\log \\eta \\rceil$", "questions": "* Could you elaborate on the advantages of your smoothness definition, taking the first weakness above into account?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper gives more fine-grained error-dependent lower bounds for multiple non-clairvoyant scheduling problems. These lower bounds are non-trivial. In my opinion, error-dependent lower bounds are not sufficiently studied in the area of learning-augmented algorithms. Hence, I think that the given lower bounds are a significant contribution.", "weaknesses": "* I don't completely get the idea behind the partition of instances in the proposed smoothness definition. Smoothness bounds according to the new definition exclude predictions that \"reveal no additional information\". However, if the predictions reveal no additional information, then lower bounds for the original problem without predictions should always apply. Hence, even using the original definitions, such predictions should always lead to the algorithms guarantee ending up in the robustness case, the same as in the new definition. \n* The paper is missing a discussion of related work on flow time scheduling with predictions, e.g., \"Distortion-Oblivious Algorithms for Scheduling on Multiple Machines\" and \"Flow time scheduling with uncertain processing time\" by Azar, Leonardi and Touitou, and \"Distortion-Oblivious Algorithms for Scheduling on Multiple Machines\" by Azar, Peretz and Touitou. These works consider a more general problem, which contains total completion time minimization. Their distortion error is related to the multiplicative error that is considered in this paper. In particular, the upper bounds presented in these works should imply (weaker) upper bounds for the error measure used in this paper.\n* The algorithmic results of Theorem 4.2 and Theorem 5.4 are not actually using the proposed new definition of smoothness. Instead, Theorem 4.2 is just an error-dependent bound and Theorem 5.4 is the minimum between an error-dependent bound and a robustness bound. Hence, both theorems just follow the original notions of consistency, robustness and smoothness. The proposed alternative notion of smoothness seems to only be used to give more fine-grained lower bounds. While these lower bounds are nice results, I think that algorithmic results are necessary to make a good case for establishing the proposed alternative notion of smoothness.\n* The algorithmic results given in this paper are not very technically involved. I think the paper would benefit from more clearly stating that the main results are more fine-grained error-dependent lower bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5bd3X3uXRp", "reviewer": "Reviewer_3VjR", "summary": "The paper considers 3 scheduling problems. Jobs are given, but their length is revealed only at their completion. This is called the non-clairvoyant model. The 3 scheduling problems are\n\n1. Single machine. The goal is to minimize the sum of completion times.\n2. Identical parallel machines. The goal is to minimize the maximum completion time.\n3. Related parallel machines. Same objective. But machines have different speeds. Execution time is job length divided by machine speed.\n\nThis model is augmented with predictions on the job length. The error between the prediction and the actual job length is measured by $\\eta$, the maximum over all jobs j, of the maximum over the ratios $p_j/p^\\star_j$ and $p^\\star_j/p_j$, where $p_j$ is the predicted and $p^\\star_j$ the actual length. Note that if the error is 1, the optimal solution could be computed, at least in exponential time for the parallel machine cases.\n\nThe performance of a schedule is measured by the competitive ratio, which compares its objective value with the optimal solution, one could compute if the actual processing times were known. \n\nThis paper is part of an active research area on learning augmented algorithms. There an important question is how to design algorithms with a competitive ratio degrading smoothly with the error.\n\nThe paper distinguishes 3 kind of instances, where an instance is the pair $\\langle p, p^*\\rangle$.\n\n- $I_c$ is the set of instance with no error, $\\eta(I)=1$.\n- $I_r$ is the set of instance with error, for which a constant prediction $p'$ exists, that is $p'_j$ is independent of $j$, and with the same error, that is $\\eta(p,p^\\star)=\\eta(p',p^\\star)$.\n- $I_s$ are all other instances.\n\nThe competitive ratio within each of these instance classes is called \n\n- consistency\n- robustness\n- smoothness \n\nThe smoothness ratio is a function of eta, and the paper provides bounds for it. For the single machine problem: when eta is between 1 and 1.835, the smoothness is at least eta. When it is between 1.835 and $1+\\sqrt3$, it is at least some specific function $\\lambda(\\eta)$. And above $1+\\sqrt3$ it is at least 2. This lower bound is continuous. It is also shown that in all cases the smoothness of the _Shortest Processing Job First_ algorithm is at most $\\eta^2$. Its analysis relies on previous work. There is a long discussion on how the worst case instances look like.\n\nThere are also lower and upper bounds given for the identical and the uniformly identical parallel machine scheduling problem. It improves over a work from 2023. For the identical parallel machine problem, there is an algorithm called SIMPLE from the 80's, which is 1+epsilon consistent and eta^2 robust, but not smooth. A modification is proposed where once a machine finishes all jobs assigned to it, steels pending jobs from other machines.\n\nFor the uniform parallel machine problem, an upper bound was know in 2024, and the paper provides an essentially matching lower bound.", "questions": "Page 4 line 198, I found definition of $I_c$ confusing and propose $I_c=\\\\{I|\\eta(T)=1\\\\}$.\n\nI found the definition of $I_c, I_r, I_s$ not well explained. I would say that R(I) is the set of instances, for which there is a constant vector $q$ such that $\\eta(p,q)=\\eta(p,p^\\star)$. In other words for a fixed prediction error, the set of possible actual job length vectors $p^\\star$ include a constant one. Which means that the prediction error does not allow to partially order jobs according to their length, or even partition them according to the approximate length. These informations would be necessary to design a good schedule. Also I need some discussion on how this smoothness is related to the usual studied notion of the competitive ratio degrading smoothly with the prediction error.\n\nTheorem 4.1 is hard to parse, because $\\eta^*$ is defined at the end of the sentence.\n\nI cannot parse Figure 3 on a black and white printout.\n\nPage 8 line 386. For large error eta, the lower bound is 2, but the upper bound is 2-1/m. Hence something is not quite right.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Overall I think that this is a great paper. It is novel to distinguish instances where the prediction can actually tell something about the instance, in addition to a distinction by the prediction error. Then the results are good, sometimes tight. The results are not technically involved, but it does not always need to be the case in a good paper. The studied problems are among the most important online problems.  It leaves open problems, and hence will drive the community in an interesting direction.\n\nPrediction error was mostly studied with respect to absolute difference. Considering the ratios for the error is in my opinion the better approach.", "weaknesses": "I had to read the definition of R(I) several times before understanding its deep meaning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xhzHh2rwTs", "reviewer": "Reviewer_88uW", "summary": "This paper studies the non-clairvoyant scheduling problem in an online setting under the algorithms with predictions framework.  In addition to the standard notions of consistency and robustness, the authors revisit the notion of smoothness, which captures the performance of a learning-augmented algorithm when predictions are in the middle ground — not perfectly accurate but also not completely adversarial (i.e., there is a bounded prediction error).  This problem has been studied before, but the authors propose a different (superior) metric to measure prediction error, and upper / lower bounds on algorithm performance in three scenarios using this error metric.", "questions": "The refined notion of smoothness requires this definition of instances on which \\eta is small enough to provide information (reasonable predictions, Definition 3.1).  Can you speak on whether this notion of smoothness can extend to other online problems?  I know there are some problems such as one-way trading that exhibit a brittleness [1] — even a prediction with a very small prediction error can be completely uninformative in some cases.  Would this pose a challenge for the proposed partitioning?\n\nAm I understanding correctly that the constant vector $\\mathbf{p}$ mentioned around line 193 is a vector where any arbitrary element is the same value (e.g., p[0] = p[1] = p[2] = ….)?\n\nCan you speak to the utility of smoothness bounds in practice?  They initially strike me as a primarily theoretical exercise since a prediction model’s error is not generally known apriori.  This question doesn’t detract from the paper’s contribution, but I wonder if there is some secondary benefit from considering smoothness (e.g., even if the bounds themselves are not informative in practice, perhaps the algorithms designed with smoothness in mind are better at dealing with prediction errors in practice?)\n\n[1] On Tradeoffs in Learning-Augmented Algorithms, Ziyad Benomar, Vianney Perchet, arXiv:2501.12770", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed method to measure prediction error (multiplicatively rather than as the $L_1$ difference) is natural and makes sense for the problem.\n\nSmoothness bounds are known to be somewhat difficult to obtain in the literature on learning-augmented algorithms (in the sense that many papers omit it completely and focus on the sometimes easier to analyze consistency and robustness metrics).  This paper provides a useful definition of smoothness (as a partitioning of the universe of inputs) that could help to model some notion of smoothness in other problems.\n\nThe paper studies several settings: single machine scheduling, parallel machines scheduling, and uniform machines scheduling, and provides or completes a set of upper and lower bounds for each setting.", "weaknesses": "Figure 2 is quite hard to read in its current form due to small text.\n\nThe upper bounds and lower bounds are not all tight in the sense that the proposed algorithms do not attain the theoretically best possible smoothness — this is a relatively mild weakness since attaining optimality in this sense seems quite challenging in the literature on related problems.\n\nTypically at an ICLR-type of conference I would expect to see some small numerical experiments in addition to the theory.  This might also allow for some comparison between the proposed algorithms and the algorithms that rely on a different prediction error metric in the literature.\n\nIt may be worth clarifying somewhere early on that $\\eta \\geq 1$ in your multiplicative model, because from the abstract a reader may get the impression that your upper bound is somehow below your lower bound (i.e., if $\\eta$ was allowed to be $< 1$, $\\eta^2 < \\eta$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UDAMy4QPRA", "reviewer": "Reviewer_m6da", "summary": "The present paper studies non-clairvoyant scheduling scheduling with predictions. In this online scheduling problem, we are given job that need to be scheduled on a single or multiple machines over time. A non-clairvoyant algorithm only learns about a job's processing time once it is completed. In particular, the paper studies this problem for minimizing the average completion time on a single machine, and minimizing the makespan on parallel identical and uniformly related machines. \n\nIn the classic online setting, these problems are well understood. The paper considers them in a learning-augmented setting, where initially a prediction on each jobs processing time is given. The quality of the prediction is measures by the maximum relative deviation factor $\\eta$ of the predictions to the actual processing times. The authors propose a new idea to classify, for a fixed error value, all instances into those where the prediction error is correct, helpful, and not helpfu. Their key idea is that if their exists a prediction that achieves for the instance the fixed prediction error, then it is still useless if all predicted job lengths are the same. By that, they remove instances from the set of instance on which they want to achieve smooth guarantees, and thereby can show better bounds than previous work.\n\nThey then apply this new definition to the three aforementioned problem variants, and prove error-dependent performance guarantees depending on $\\eta$.", "questions": "As far as I know, the type of multiplicative prediction error has been introduced in a paper by Azar, Leonardi, and Touitou (STOC 2021). Perhaps you update these references.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a new way to establish smoothness bounds for learning-augmented algorithms, and showcases it in non-clairvoyant scheduling, a well-studied and established class of problems in the area.\n- The bounds are highly non-trivial and optimized. They improve over previous work.\n- They prove lower bounds that show that previous results are best-possible\n- The paper considers three different problems, which have all been studied before, and thereby nicely continues the story of learning-augmented scheduling.\n\nI think that the paper is a nice contribution to the field of learning-augmented algorithms. It has a new conceptual idea and executes it across different settings, which showcases it applicability. It also gives a good overview over literature. I think it is a good fit for ICLR.", "weaknesses": "- One can argue that the results are somewhat incremental, but I think this is rather a minor weakness.\n- I would prefer a slightly less technical main part. For a revised version, I would recommend to simplify or upper bound complicated expressions like in Theorem 4.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)