Competitive Fair Scheduling with Predictions
Authors: Tianming Zhao
Chunqiu xia
Xiaomin Chang
Chunhao Li
Wei Li
Albert Zomaya
Venue: ICLR 2025 Poster (2025)
Keywords: Learning-augmented Algorithms
Scheduling
Competitive analysis
Fairness
Predictions
Primary area: optimization
TL;DR: We consider online non-clairvoyant scheduling to minimize the max-stretch under the learning-augmented framework and design competitive algorithms under various settings.

Abstract: Beyond the worst-case analysis of algorithms, the learning-augmented framework considers that an algorithm can leverage possibly imperfect predictions about the unknown variables to have guarantees tied to the prediction quality. We consider online non-clairvoyant scheduling to minimize the max-stretch under this framework, where the scheduler can access job size predictions. We present a family of algorithms: Relaxed-Greedy (RG) with an $O(\eta^3 \cdot \sqrt{P})$ competitive ratio, where $\eta$ denotes the prediction error for job sizes and $P$ the maximum job size ratio; Adaptive Relaxed-Greedy with an $O(\lambda^{0.5} \cdot \eta^{2.5} \cdot \sqrt{P})$ competitive ratio, where $\lambda$ denotes the error for the minimum job size; Predictive Relaxed-Greedy with an $O(\lambda^{0.5} \cdot \varphi^{0.5} \cdot \eta \cdot \max \\\{ \eta, \varphi \\\} \cdot \sqrt{P})$ competitive ratio, where $\varphi$ denotes the error for the maximum job size. We also present *${RG}^x$*, an algorithm that represents a trade-off between consistency and smoothness, with an $O(\eta^{2+2x} \cdot P^{1-x})$ competitive ratio. We introduce a general method using resource augmentation to bound robustness, resulting in *RR*-augmented *RG*, with a $(1 + \epsilon)$-speed $O(\min \\\{ \eta^3 \sqrt{P}, \frac{n}{\epsilon} \\\})$ competitive ratio. Finally, we conduct simulations on synthetic and real-world datasets to evaluate the practical performance of these algorithms.

Published as a conference paper at ICLR 2025
COMPETITIVE FAIR BAIRSCHERR SCHEDULING WITH PREDICTIONS
Tianming Zhao
Chunqiu Xia
Xiaomin Chang
School of Computer Science The University of Sydney
School of Computer Science The University of Sydney
School of Computer Science
The University of Sydney
Chunhao Li
Wei Li
Albert Y. Zomaya
School of Computer Science
School of Computer Science The University of Sydney
School of Computer Science
The University of Sydney
The University of Sydney
ABSTRACT
Beyond the worst-case analysis of algorithms, the learning-augmented framework considers that an algorithm can leverage possibly imperfect predictions about the unknown variables have guarantees tied the prediction quality. We consider online non-clairvoyant scheduling to minimize the max-stretch under this frame- work, where the scheduler can access job size predictions. We present family of algorithms: Staxxed-Greddy (RG) with an OTp vP) competitive ratio, where !) denotes the prediction error for job sizes and P the maximum job size ratio; Adaptive Relaxed-Greedy with an ((x9.5 .7,2.5 2,. vP) competitive ratio, where À with an ( -p..... 11 max up VP) competitive ratio, where denotes the error for the maximum job size. We also present RG algorithm that represents trade- off between consistency and smoothness, with an 0 pl-") competitive ratio. We introduce general method using resource augmentation to bound robust- ness, resulting in RR-augmented RG, with (1 c)-speed O (172 V " competitive ratio. Finally, we conduct simulations on synthetic and real-world datasets evaluate the practical performance of these algorithms.
denotes the error for the minimum job size; Predictive Relaxed-Greed
INTRODUCTION
In classic online scheduling. algorithms are designed to have worst-case guarantees under incomplete information. However, this conservative approach often results in suboptimal performance, especially compared to where full information is available. Given the rapid advancements in Machine Learning (ML) predictive models, the need for worst-case guarantees under incomplete information may be too pessimistic. Beyond worst-case analysis, recent researchers have explored learning-augnen augmented al- gorithms leverage predictions to improve siciision-making With ML models providing predictions of unknown variables, these algorithms are robust and have an improved performance.
Scheduling jobs that arrive over time (preemption allowed) is fundamental challenge in computing resource management, particularly when minimizing the maximum stretch. The stretch of a job Jj is defined the ratio of its response time job size, given by C, C--ry where Cj denotes the completion
P
time, ry release time, and p job size (or processing time). The maximum stretch, termed max-stretch, measures fairuess of the resource allocation: max-stretch of A implies that each job receives least x --speed machine. In contrast, other metries like total completion time ( Cj) and total response time (EC, T3) emphasize efficiency and will unfairly delay large jobs, even those released early. Studying max-stretch scheduling offers general insight into fair resource allocation.
Previous work has considered offline max-stretch scheduling and online clairvoyant scheduling: both assume precisely known job sizes (Bender et al. 1998 2002, Benoit et al. 2021). However, assuming perfect knowledge is overly optimistic in practice. Job sizes can be estimated using ML models (Amiri and Mohammad- Khanli 2017) but inherently subject to error. This raises key question: how can we make fair scheduling decisions with imperfect information? ? Our objective is leameneeaugmmeteed algorithms with performance guarantees tied to the prediction quality and robust

---

Published as a conference paper at ICLR 2025
against poor predictions. To our knowledge, this paper is the first to explore learning- augmented algorithms for fair scheduling. We define several terms before presenting our contributions.
Prediction errors. We consider several types of predictions: job size predictions per job at the job's arrival, an upfront prediction for the minimum job size, and an upfront prediction for the maximum job size. Prediction errors are defined the multiplicative difference between predicted and actual job sizes. Let y) denote the prediction error, defined as 7 where Pj is the job size prediction for Jj (Zhao et al., 2022 Azar et al., 2021). We define
maxisıS4 f/ = maxi5şjn max py p
Ei # J.
as the ratio of the largest and smallest job sizes: P Pmas
where Pinax and Pimin represent the maximum and minimum job sizes. For the predicted minimum job size, the error is denoted by
Pinga
Pintn" Pintn J. where Pinin is the predicted minimum job size. The error for the predicted maximum job size is ip max Liaax Pinxx
max Paiia Pain
Pimax
), where Pmax is the predicted maximum job size.
Pinax
Competitive framework, consistency, smoothness, and robustness. An online algorithm will be compared against an offline optimal algorithm A" that knows all jobs' release times and sizes in advance. We say A has a competitive ratio or is e-competitive, if (A) I c SSSAA (T) for any problem instance I, where (T) and 5 (T) denote the max- max-stretch achieved by A and A", respectively. Consistency measures the algorithm performance under perfect predictions; smoothness under any prediction; robustness under worst-case predictions. Formally, an algorithm is said to have consistency T (or be r-consistent) if it is r-competitive when 7) = 1; smoothness p (or be p-smooth) it is p-competitive where p a function of n7; and robustness (or be v-robust) if it is u-competitive for any where v is independent of 7). The relationship between smoothness and robustness can be expressed robustness lim smoothness.
Resource augmentation. An algorithm A is (1 c)-speed c-competitive if 5 S c. Sf (T) for any problem instance J, where (7) and S (T) denote the max-stretch achieved by and A", respectively, and the subscripts denote the speed of the processor used by the corresponding algorithm and A is an offline optimal algorithm.
CONTRIBUTIONS
1. Improved fairness in scheduling: We present an exact offline algorithm with runtime of O(n" l)) where n is the number of jobs. We develop family of Srexxed-Greddy (RG) algorithms under various prediction settings, achieving an O(vP) competitive ratio matching the best-known clairvoyant result under perfect predictions. These algorithms require different types of predictions, including job size and minimun/maximum job size predictions, with varying guarantees depending the quality and availability of the predictions. These algorithms leverage ML predictions for job sizes to optimize fairness in resource allocation. They extend the algo- rithmic idea proposed by Bender et al. (2002), but with predictions, they longer require prior knowledge of exact or extreme job sizes, making them applicable to a broader range of scenarios.
We explore the trade-off between consistency and smooth- ness by introducing RG with competitive ratio of 0(72+2r pl-*). This algorithm is parame- terized, allowing users to adjust the guarantees a function of the prediction error 7), based on the confidence in the prediction quality.
trade-off:
Enhanced robustness via resource augmentation: To address the robustness limitations O(n- P) in the RG family, we propose RG round-robin- -ugme-ed version of RG, which achieves optimal robustness of (n) with a (1 + e) -spped and a competitive ratio of O (min & /P, a }). We demonstrate how asymptotically optimal robustness can be achieved via resource augmentation when the classic technique of preferential round robin fails (Purohit et al. 2018).
4. Extensive experimental validation:
We conduct experiments on synthetic and world datasets to evaluate the performance of these algorithms. The experimental results validate our theoret- ical analysis and demonstrate that RG consistently outperforms other algorithms in practical scenarios, showing its robustness and effectiveness.
2

---

Published as a conference paper at ICLR 2025
The family of the RG algorithms is somewhat reminiscent of the proposed by [Bnnder et al. (202). The existing algorithms work in clairvoyant scheduling. They assume the minimum job size is 1 and a known maximum job size. The assumption is unrealistic, particularly when the extreme job sizes vary from time to time. Our algorithms extend the existing work to non-clairvoyant scheduling and overcome these limitations via predictions. The proposed algorithms allow variable minimum job size and do not require the exact maximum job size.
algorithm
2 PRELIMINARIES
Problem definition. Consider job system with a single unit-speed machine and n independent jobs. The jobs arrive at the machine for processing over time. We use Jj denote the j-th arrived job (tie break arbitrarily). Job Jj has a release time тÿ and a job size p). i.e., it takes (in total) pz time to complete processing job Jj. Jobs are preemptive, which means they can be preempted during their processing. A preempted job can resume processing later. Let Cj denote the completion time for job Jz. The stretch Sj for job Jj is the ratio of the response time and job size, i.e., Sj C_- Our objective is to minimize the maximum stretch, known as max-stretch:
Pj
max-stretch = maxisi S3- = maxigisn
Cj-rs
Related work. We review recent advances in competitive online scheduling with predictions. For single-maching static scheduling to minimize total completion time, an ((min (1 27), 1-x })- competitive algorithm exists (Purohit et al.] 2018). where 7) is the additive error defined as 17 Ej=1 Ipy P, and À is a user-defined parameter. Follow-up works analyze robustness robustress-comsistennyy trade-off's Wei and Zhang 2020) and extend the results to dynamic scheduling and parallel machines
n
log log 2022). For unrelated machine scheduling to minimize makespan, deterministic log log m log m} >competttieee algorithm is developed (Li and Xian 2021), building on (Lattanzi et al. 2020). Here, the predictions are for machine loads, 7) is the multplicattive error of the predictions, and m is the number of machines. For single-machine machine scheduling to minimize weighted algorithm is developed (Azar et al., 2021), where j is the multiplicative error for job size predictions and D is the maximum density ratio. For parallel identical machine scheduling. an O(min (uP, μ log μ + ş log n m compettiieeee algorithm is developed to minimize the mean response time, along with an O²n²) -comp-icotee non- migrative algorithm for minimizing mean stretch (Azar et al. 2022). Our problem is special case of minimizing maximum weighted response time, but prior works under the Garming-augmeent framework focus on min-sum objective, while our work focuses on min-max. Results on prediction error metrics (Im et al. 202T). ) multiple predictions (Dinitz et al. 2022), machine speed predictions (Balkanski et al. 2023 and stochastic scheduling (Merlis et al. 2023) are also available.
(Bampis al.
O(min
response time, an O(min((r log(uP), ورر
(
OFFLINE, ONLINE CLAIRVOYANT, ONLINE NON-CLAIRVOYANT SCHEDULING
We start with offline scheduling. We show an optimal algorithm with (
2 log n) run time. We review the lower bound and competitive algorithms for online clairvoyant scheduling. We consider online non-clairvoyant scheduling and show a 2(n) competitive lower bound with an Oomm-oomeeee
algorithm. Proofs for Section 3.1 and 3.3 are in Appendix and B
3.1 OFFLINE SCHEDULING
We have already known that an approximation exists for offline scheduling.
Theorem 3.1 (Bender et al. 1998).. There exists an algorithm that finds a preemptive offline schedule with max-stretch most + ttmes the optimum time polynomial in n and {. for any fixed
The (1 + apprroxximtionnn algorithm is based a bisection search over the value of the optimal max max-stretch, using Earliest Deadline First (EDF) to check the feasibility of each candidate value. While the algorithm is polynomial in terms of the number of jobs and the precision parameter it is not purely polynomial in the input size n. This is because, traditionally, finding the exact minimum max-stretch was considered to involve infinite search space, thus requiring a predefined precision
3

---

Published as a conference paper at ICLR 2025
to discretize the search space. [Bender et al. (2002) propose that the search for the maximum stretch can be reduced to a finite set candidates, but they do not formalize this result. Recent work (Benoit exact polynomial-time greedy algorithm for the case where all jobs are released at time O. This algorithm follows the smallest job size first policy but does not apply to the general case with arbitrary release times. To close this gap, first technical contribution is formal proof of an exact, polynomial-tin )
et al.] 202I)) provides
offline scheduling algorithm for arbitrary release times. The insight is identifying an On >size list of candidates that contains the optimal max- max-stretch. We establish the following result, with the proof provided in Appendix A
Theorem 3.2 (Optimal Offline Scheduling). There exists an algorithm that finds an offline schedule with optimal max-stretch in time polynomial in n. It admits an O logn) implementation.
3.2 ONLINE CLAIRVOYANT SCHEDULING
We consider online clairvoyant scheduling, where we know a job at its release time. We also know the exact job size p when job Jj is released. This problem has been studied by Bender et al. (1998) 2002]. We summarize the key results, including the lower bound and competitive algorithms.
Theorem 3.3
(Bender et al.
(1998). No 2 -competitive deterministic clairvoyant algorithm exists.
Theorem 3,4
Bender et al. 2002 ) There exist Ploopeccceeeii clairvoyant algorithms.
3.3 ONLINE NON-CLAIRVOYANT SCHEDULING
We consider online coa-clairvoyant scheduling, where we know a job its release time but not the job size Pj at job J,'s release. The job size is revealed only after the job is completed. We give the lower bound on the competitive ratio for any deterministic algorithm. The key construction of the adversary is to force the algorithm to allocate no more than a 1 share of processing at some point for the smallest-sized job, resulting in a stretch of for that job. Subsequently. the rest of the jobs are assigned geometrically increasing sizes, ensuring that the optimum max- stretch is approximately 1. Theorem 3.5 Non-ccairvoyyant Lower Bound). No c-competitive deterministic algorithm exists with < n. for online non-clairvoyant max-stretch scheduling, even if all jobs are released time 0.
We show Round Robin (RR) scheduling where every job in the system shares an equal amount of processing power of the machine at any arbitrarily fine time, i.e., with & jobs in the system, each gets units of the processing done every time unit until any job completes or any job arrives), an n-competitive online non-clairvoyant scheduling algorithm.
Theorem 3.6 (o-Compeee RR). AR is n-competitive for online non-clairvoyant scheduling.
We show that any non-lazy algorithm is O(n c)coopttiievee. Here, non-lazy means that the algorithm does not idle the machine unnecessarily when there are active jobs. This result will be used to establish the robustness of learning- aanmentd algorithms in the following sections.
Theorem 3.7 (Worst-case Competitive Ratio). Any non-lazy algorithm is (n - 1)- P 1 1-competitive.
ONLINE SCHEDULING WITH PREDICTIONS
We consider the integration of predictions. Rather than knowing the exact job size, have size prediction Pj for job Jy. Initially. we assume that the extreme predictions are known beforehand; specifically, the algorithm knows the smallest prediction Pmii (i.e., prediction Pmnax (maxisjsn Pj) at time O. We present the Solaxed-Greede algorithm, which achieves an O17² vP) competitive ratio, where is the prediction error for job sizes. Next, we show how to remove this assumption by updating the extreme predictions observed online and using predictions of the extreme job sizes. We introduce the Adaptive telaxed-Greede algorithm, which uses the prediction of the minimum job size and dynamically updates the maximum job size prediction, achieving an ( 1,2.5 /P) competitive ratio, where is the prediction error for the minimum job size. Finally, we present the Predictive Relaxed-Greed O 6 n max (p) vP) competitive ratio, where o is the prediction error for the maximum job size. We begin by outlining the algorithmic ideas, with proofs for Section 4.2 4.3 and 4.4 provided in Appendix and
Pý) and the largest
algorithm, which uses
predictions of both extreme job sizes. achieving
4

---

Published as a conference paper at ICLR 2025
4.1 ALGORITHM OVERVIEW
The key algorithmic idea is the reduction to the case with two job sizes. Recall that the stretch is defined as C.-rr, If there are only two job sizes one short and the other long the jobs of the 52
same type should he executed in a First-In-FirstOOn (FIFO) manner. A short job should be executed before long job if the long job is released at the same time as, or later than, the short job. It can be shown that greedily scheduling the jobs, i.c., always running the job with the minimal stretch, results in a constant competitive ratio when there are only two job sizes (as shown in Bender et al. (2002) and Lemma C.6). Clearly, the problem becomes easier when there are only two job sizes. Our strategy to reduce the general problem to this two-job-size case via predictions.
We classify jobs into two categories: job Jj is considered short if its job size prediction Pj S s/Pmin Panax where 14 is a constant, and long otherwise. We show in Appendix that the optimal choice for μ v3, though for now, we can ignore this constant. We then approximate the stretch for با=ي and for long jobs by C these are defined to be relaxed stretch. This short jobs by VPrwin Piaax construction follows the idea in Bender et al. (2002), but requires both Pmin and Pmax to account for that the minimal job size is not necessarily 1, which is assumed in Bender et al. (2002). This approach overestimates the size of a short job J by PPmin "Pmax I v TT²²- -Piin Pinax 1) VP- Pmin S n v vP- ppj resulting in an overestimation by at most a factor of n/v P. Similarly,, it overestimates the size
Pmaa
of long job Jj (p) Prmin PPmax) by Pmax "/Pmin" 'Pmax''
Puus
I <n. -/P.v
Puun
meaning the overestimation is at most a factor of vP Overall, the relaxed stretch overestimates job sizes by at most /P. With these approximations, the stretch a a J, is bounded by ((r'PP) times the relaxed stretch, resulting in competitive ratio loss of O()²vP) (Lemma C.8 However, the advantage of this approximation is that reduces the scheduling problem the easier two-job- size case. In Appendix H we show that using the square root of Pmin Pmmax provides the optimal dependency on P in the competitive ratio, though it is possible to adjust the power to P'min P for any x S 1. yielding different power dependencies on P in the competitive ratio.
Using predictions to classify jobs as short or long, we greedily schedule the jobs by running the job with the minimal relaxed stretch any time. This heuristic minimizes the relaxed stretch to within constant factor (v3). Finally, we observe that the optimal relaxed stretch is bounded by y) times the optimal max-stretch (Lemma C.7 The max-stretch bound from Relaxed-Greedt is O(r2 of the optimal relaxed stretch, which is itself bounded by 0(7²v/) of the optimal max-stretch.
4.2 DELAXED-GREEIT
One of the assumptions for previous algorithms is that the minimum job size is known to be 1 and that the maximum job size is also known upfront. We relax these assumptions by setting a threshold as the geometric mean of the predicted minimum and maximum job sizes, which serves as the boundary for classifying jobs as small or large. Our analysis shows that such methods allow the performance to tie to the prediction errors for these quantities.
Definition 4.1 (a-3 Relaxed-SStetchh) Define 0-3 relaxed-stretch (j., for job Jj at time ( given and 3: S) = I-ri if J is active at time and Pj S a; (t),,s(t) = (-ry if J, is active at time and P. >> a. We drop the prefix a-3 when the context is clear.
Definition 4.2 (a-9 Short and Long Jobs). Given parameters a and 8, a job Jj is said to be short if P, < a; a job Jj is said to be long otherwise.
We present VP) -Poompoptttiiiiee algorithm Relaxed-Greede (RG). Through the execution and B = Pinax- It holds
of RG, parameters a and B are set to be constants: a /Pmin Proax
v3
Pmmin Pinax Pmax B. Note that the constant v3 in serves to yield optimal constant in
the competitive ratio. Any constant can replace it and still maintain RG's O(T²VP) competitive ratio as long as a < 3 (see Appendix for a discussion). Algorithm RG maintains the invariant of running the active job with the largest relaxed-stretch. This means that at any time i, RG looks at all
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: Relaxed- Greedy
Data :job size prediction Py upon job release and the extreme predictions Puin Pmax
Result schedule with max-stretch O(1)² times the optimum max-stretch
VPmin Pinox ,3 Pmax
v3
Function relaxedStreter (j.0) // computes job J relaxed at time
if Jj completed before then
L t + C, // set variable to be the completion time of J,
t-r p) Σ a else t-r
return
Relaxed-Greedy maintains the active job (released but not completed job) set U; initially, set U + 0. Event Function NobRelease () // Jj is released
insert Jj into U; on the machine U 0.
Event Function JobComplete () // J3 has been processed for p unit at time L remove Jj from U.
11
if there at least one job in U then let J, be the job in U with the largest relaxed-streteie J. + arg max relaxedStretch( t). with tie breaking by the smaller job index.
12
run J. on the machine.
14
else
15
idle the machine.
16
Event Function JobSwitchi // there exists Ja EU such that relaxedStretch(r, t) relaxedStretch(e:t) t), where Je is the currently running job let J, be the job U with the largest relaxed-stretch: Je arg urgmax relaxedStretch(z, with breaking by the smaller job index.
18
preempt Je.
19
run J. on the machine.
the active jobs and processes the one with the largest relaxed-stretee until the job is completed or until there another active job later with larger relaxed-stretch. Note that RG does need the knowledge of the prediction error The pseudo-code of RG is given in Algorithm [
Theorem 4.3 (The ( Competitive Ratio). Relaxed-Greedy. is v3 V VP-competitive
for online scheduling with predictions.
We show that RG is (nn co)coepttii with the worst-case predictions. Theorem 4.4 (Robustness RG). RG 1)- 1-competitive with arbitrarity bad predictions, and this bound is tight.
Remark 4.5. Relaxed-Greede is v3 VP-consistent,, v SaaiesetttttttnasSssssseee PP-smothh, and (n - 1) P + 1- robust. It represents consistency of O(VP) matching (asymptotically) the best-known clairvoyant competitive ratio but comes with the worst robustness among non-lazy algorithms.
Algorithm RG can be implemented with constant run-time for online gpcision-making Observe that any later-released short (long) job has smaller relaxed-streteh than any early-released active short (long) job. Thus, the short (long) jobs are processed in First-In-First-Oi (FIFO) manner, allowing us to maintain two queues, one for short and one for long jobs. Determining the job with the largest relaxed-stretch requires simply comparing the relaxed-stretci We give RG's 's performance for its run-time and space complexity and preemptions.
the jobs at the front of the queues.
Proposition 4.6 (Complexity RG). Relaxed-Green Greedy admits an implementation with O(1) run- time to make any online decision and ((n) space.
Proposition 4.7 (Preemptions of RG). Relaxed-Greede generates a schedule with at most n 1 preemptions. Thus, the amortized number of preemptions per job is at most 1.
4.3 ADAPTIVE RELAXED-GREED
We remove the assumption of knowing the extreme predictions beforehand and extend RG to Adaptive Relaxed-Greedy (ARG). We show that the absence of extreme predictions does not

---

Published as a conference paper at ICLR 2025
significantly alter the competitive ratio. We show that ARG achieves an 0(10.5177255 .12.5......PP))) competitive ratio, where À denotes the prediction error for the minimum job size. Instead of knowing the exact minimum job size prediction, Algorithm ARG can access black-box ML model that predicts the minimum job size of all jobs, denoted by Pinin This predicted minimum job size Pinin comes with a Meanwhile, Algorithm ARG learns Pmax along job release.
prediction error À max Pinta
Pain
Pinin
Pinin
key technical challenge in ARG is classifying jobs when a is continuously updated over time. Dynamically changing the classification of jobs might work, but the proof for its competitive ratio is difficult to establish (we did not find proof). Our solution overcomes this issue by ensuring that once a job is classified at its arrival time, based oryy it remains unchanged in that classification. For example, if job Jj is classified as r-long, it remains a long job, regardless of future updates of a. This enables the competitive analysis for ARG. One innovation of ARG is the of heterogeneous predictions, i.c., predictions for different types of quantities, in Saarnnng-uugmeet analysis reveals that these different predictions impact the algorithm's performance differently.
algorithms. Our
We introduce subscript / to denote the value of variable at time L. Thus, Pmax at time (denoted by Pmaxxt) represents the maximum job size prediction seen so far, i.e., Pmax. max,, St Pj- Parameters a and |3 are functions in Pmin and Pmax and thus are time-varying They are updated with
updates of Pmax in JobRelease. Formally, ARG sets an /Pain Pmaxx and Br max max (Pmax, at), va where Og and 3e denote the values of a and B time 1. We record Or; and Br, for every job Jj. These values are used compute the adaptive relaxed-strete stretch of Jj. defined as follows.
Definition 4.8 (a-8 Adaptive Relaxed-Stretch), Define a-8 adaptive relaxed-stretch St,, for job A-ry Jj at time given and 3: S3,a,9 f-ri if J is active at time t and pj S ar, (),, Br, if Jj is active at time t and Pj ary, We drop the prefix a-3 when the context is clear.
ary
Definition 4.9 (a-B r-short and r-long Jobs). Given parameters a and B, a job J, is said to be r-short if p S Ory; aryaajof job Jj is said to be r-long otherwise.
The prefix r for r-short or r-long means that the classification depends on the values a and 3 at r'y for job J.. is thus possible that a r-short job released later has larger job size prediction than r-long job released earlier. Other than that, ARG maintains the (same) invariant of running the active job with the largest adaptive relaxed-stretch. The pseudo-code of ARG is given in Appendix E
Theorem 4.10 (The O()0.5 .72.5 vP) Competitive Ratio). Adaptive Relaxed-Greedy is v3.
0.5 2,2.5 /Pocompetieivee for online scheduling with predictions.
Remark 4.11. Adaptive
v3- VP-consistent, - n P--soooth and
(n- 1) + 1-robust. This robustness result is tight.
The ARG's performance remains the same as RG with respect to run-time and space complexity and preemptions. Since the parameters a and B are non-decreasing, still holds that any later-released short (long) job has a smaller adaptive relaxed-stretch than any carly-released active short (long) job, allowing ARG to have the same implementation of two FIFO job queues as RG does.
Proposition 4.12 (Complexity of ARG). Adaptive Belaxed-Greens admits implementation with (1) run-time to make any online decision and O(n) space.
Proposition 4.13 (Preemptions of ARG). Adaptive Relaxed- Greedy generates a schedule with at most n 1 preemptions. Thus, the amortized number of preemptions per job is at most 1.
The competitive result in this section does not hold if the algorithm is instead given the predicted maximum job size and has to estimate the minimum job size prediction online. There seems to be an asymmetric importance for the knowledge about extreme job sizes. Having some knowledge of the mínimum job size at the start may be a requirement.
4.4 PREDICTIVE RELAXED-GREEI
If the prediction error(s) for extreme job sizes are believed be lower than 17. the algorithm can use an additional prediction about the maximum job size. We extend RG to Predictive Relaxed-Greedi (PRG), which needs access to predictions of both the minimum job size, denoted by pmmnn and
the maximum job size, denoted by Pinax of all jobs, with prediction errors À = max Pmm Puin
Puin P
7

---

Published as a conference paper at ICLR 2025
}- PRG sets static and / independent of time: Vimi Plnns and
and 40 max {
Pinax Prixx
Pinax"
Pinaxe
Faax where f is a symbolic constant f max (v3,
Piiin
+ + } for any small fixed 0.
Pince
This ensures a < 3. Algorithm PRG maintains the same invariant of running the active job with the largest relaxed-stretch determined by the above a and 3.
Theorem 4.14 (The O(20.5 -0..S -n max( (0} vP) Competitive Ratio), Predictive Relaxed- Greedy is max A. p Au.5 .pu.s.. 17- max p) VP-competitive.
With reasonable predictions where Punin S Pmnxx and S 17, PRG is v3. 1 . competitive. With extremely bad predictions (i.e., Piuin > Pimax). however, the competitive ratio depends on the prediction values and becomes (V Pinin +c). ,0.b... ....o.nmmffffofmm maxaax(; (p) vP. This can Pinxx
00.5 ...5..... -7 P-
be avoided by switching to ARG when Pmnnn > 3 Pimxx Combining of ARG and PRG guarantees the competitive ratio of v/3 X y0u. vn max (p) vP or v33 X 1/2.5 vP.
Remark 4.15. Predictive Relaxed Relaxed-Greedy is max 3. u1- VP-consistent, max L. u1 A .0... max(7) (7, pp -s-moothh, and (n 1)- 10-P4 1-robust. This robustness result is tight. The algorithm admits an implementation with ((1) run-time to make any online decision and ((n) space and generates a schedule with at most preemptions.
5
TRADE-OFFS
We study the trade-off off between consistency and smoothness for RG by altering the parameters (a and (8) in the definition of relaxed-stretch. The idea directly applies ARG and PRG, so this paper does not discuss them. We introduce hyper-parameter x (0 S S 1) Denote RG 2 to be Relaxed
Greedy parametrized by z, where RG sets Plii. and 3 Pmax and runs the same process v3
as RG. This constructs family of algorithms and RG is one member RG We show that RG interpolates between the First Come First Serve (denoted by FIFO) algorithm and RG, where FIFO is -compppitiieevveee and RG is O17²² v cooocttttii See Appendix Gor proofs for this section and Appendix H for the construction process of RG
Theorem 5.1 (The 011 pl->) Competitive Ratio). RG (0 S S 2 is /3 2222 pl-s.
competitive for online scheduling with predictions.
we set x with a = Pmax, 3 = Pmax, we have a singular point where RG decays to FIFO, as every job would be classified as a short job. We drop the constant v3 here as this term in relaxed-
stretch does not improve the performance RG Algorithm RG with a = Pmaxs 3 = Pmax Or FIFO, achieves O(P) competitive ratio.
Theorem 5.2 (The O(P) Competitive Ratio), RG or FIFO, is P-competitive.
Setting x 1 gives the best consistency (O(vP)) but the worst smoothness (0(1²)). In contrast, 3
Pınax, Pmax gives the worst consistency (O(P)) but the optimal smoothness as a function on v) (O(1)), for which the prediction quality does not affect the performance at all. If we exclude the singular point RG i.e., 0 < S the power of P from 1 to and increases that of 17 from 2 to 3 (a visualization of the trade-offs is in Appendix []). Practitioners can choose the srper-parameter z based on the confidence of the prediction quality: high-quality predictions deserve high æ; low-quality predictions a low
setting O with
2. increasing syper-parameter decreases
BOUNDING ROBUSTNESS VIA RESOURCE AUGMENTATION
We introduce a general method for bounding robustness. The goal is to address the weak robustness (O(n P)) of the soamingg-ugmmeteer algorithms,, i.e., they cannot deal with the worst predictions. We first show that the recent technique of Preferential Round Robin (PRR) (Purohit et al.) 2018). which allocates partial processing power to multiple algorithms, fails to address this issue with the mtx-stretch metric. This shows the necessity of resource augmentation (Kalyanasundaram
8

---

Published as a conference paper at ICLR 2025
and Pruhs 2000). We produce family of RR-augmented algorithms with asymptotically optimal robustness and near-optimal consistency. Algorithm RG one member of the family, is (1 (speed O(min (n) . vP. competitive.. Proofs are in Appendix
We first review the PRR method. Suppose we have two algorithms, A and B, with competitive ratios Ca and en. Combining the two algorithms by giving (0 1) proportion of processing power to A and 1 - x processing power to B constructs a competitive ratio of min [2, I-z metrics (e.g., total completion time) under static scheduling (all jobs are released at time 0). This method, however, requires critical assumption that each algorithm, when given processing power less than 1, has a competitive ratio scaled by the allocated speed. This assumption, unfortunately, fails to hold in general and, in particular, not for the max-stretch scheduling.
_c_ } for some
Theorem 6.1 (Motivation for Resource Augmentation). Any algorithm is at best 1-e n + 1- competitive, if given a (1 speee machine, for any
1.
With a slower machine, any algorithm is Q(n) competiive, matching the non-clairvoyant lower bound. This means (slower) speed takes away the advantages of clairvoyance, echoing similar phenomenon as previously observed by KKayaanaundaaan and Pruhs (2000). As a result, the assumption for PRR does not hold. Theorem 6..1 also suggests that RR has asymptotically optimal competitive ratio (O(z)) with slower machine. This leads to the design of RR-augmented algorithms with resource augmentation. The idea augment base algorithm (e.g., RG) with higher-speed machine, using the additional speed to run RR concurrently at unit speed.
Definition 6.2 (Monotonicity (Purohit et al., 2018)). A non-clairvoyant scheduling algorithm is called monotonic if given two instances with identical inputs and actual job sizes (pi.... Ph) and .......'''' such that pj S p" for all j. the objective function value found by the algorithm for the first instance is no higher than that for the second.
Lemma 6.3. All algorithms mentioned in this paper (RG, ARG, PRG, RG", and RR) are monotonic.
Theorem 6.4 (RR-augmented Algorithms). Given a monotonic algorithm with competitive ratio CA. one can obtain (1 + e--eed min(cA. ccompetitive ( (RR-augmented) algorithm.
Remark 6.5. RR-augmented RG (denoted by RG*) is (1 + e)-speed min /33 min n/² vP. - competitive. Similarly, we produce ARG + ((1 ()-seed min 33 X .7/2., .P, )-competitivv) PRG (1-ee--ppeed min |h: -4 00. .00.5 m n-max(n, .P.. ) >-oopetittive) and PRG** ((1 + e)-speed min (33 17 2222 pl-x, a ccompetitive). While preserving their consistency, these algorithms achieve asymptotically optimal robustness, strictly optimal with 2-speed augmentation.
EXPERIMENTS
We evaluate Greedy- with-Rounding (GWR) (Bender et 2002). RR, RG, ARG, and RG on synthetic and real-world datasets (Google 2019), (Alibabal 2023), and Azure (Cortez et al. 2017) in minimizing max-stretch, variance of stretch, and mean response time. Stretch variance measures fairness by comparing jobs to each other; the mean response time measures total efficiency. This section presents the results for the max-stretch minimization. The rest of the results and discussions
are in Appendix K L M
and N Code is available on GitHub (Anonymous) 2024p.
We measure the performance ratio, which is the ratio between the max-stretch obtained by an algorithm and the optimum. Algorithm 2 is used to compute the optimal max-stretch. We set RG to be (1 + 0s3)-speed RR-augmented RG, it runs RG at unit speed and RR at speed 0.3. The job sizes are generated following exponential distributions. With the maximum job size ratio P. we set P, max log X- AA where X is a random variable with X ~ U(0, 1) and A scaling factor to ensure p < P. Given 17 and p). set pý + p}- exp(YY with Y log n, log n). We generate 50 independent instances for every problem set defined by n, P. 17, and the range of release times.
Figures to are the results for synthetic datasets. Figures T and 2 present the performance ratio under different n and P with perfect predictions. RG and ARG outperform GWR and RR in most scenarios. RG+, with a slight 0.3 speed augmentation, consistently achieves the best performance. Figure presents the results under an increasing 7). While the performance ratio of RG, ARG, and RG+ increases with 17. RG is robust prediction error with bounded performance ratio.

---

Published as a conference paper at ICLR 2025
400
800
000m
100
96
Perta
Pertemanne
Figure Performance
increasing jobs.
represents
Figure 2: Performance ratios increasing P. sizes
the distribution of the performance ratios. The number of jobs is 1000
drawn from interval [1, Pl. where P is set to (RICI), 2 (RIC2). (R2C3).
(RICI), 2000 (RIC2) 3000 (RIC3), 4500 (R2C1), 6000 (R2C2),
(RIC3).
(R2C2),
10000 (R2C3), relensed uniformly [0, 5000] with sizes in [1, 10].
jobs fixed at 4500. Jobs are released in time (o, 5000 uniformly random prediction error set
Prediction error 1 (i.e, py = P.).
Ratoo
Performance Ratio
AGG
2.25
128
Prodiction Error
Figure Performance ratios with un increusing prediction emor y. The prediction increases from to 512. The number of jobs fixed 4500. Johs are released in time [0, 5000] uniformly at random, The joh are drawn [1: 10].
Prediction Error
Figure 4: Performance ratios with an increasing prediction error (1 6) on real-world trace-log data from Google Cloud.
Performance Ratio
150--90
250.
R01
150
100
Prediction Error
Prediction
Figure Performance ratios increasing prodiction
Figure 6: Performance an increasing prediction error (1 6) real world trace data from Alibaba Cloud.
6) on world trace log data from Azure Cloud.
Figure 4 to presents the results on real-world trace-log data under different y). RG and ARG have strong performance under perfect predictions. With limited job size information, the performance ratio of ARG increases the fastest with increasing 7). RG's performance ratio falls between ARG and GWR under imperfect predictions. Overall, RG achieves the best performance at all times.
8 CONCLUSION
Under classic scheduling settings, propose exact polynomial-time offline algorithm, establish a non-clairvoyant competitive lower bound of 2(n), and present a matching (oomectmtee algorithm. We develop family of algorithms for online scheduling to minimize max-stretch with different types of predictions. These algorithms offer various guarantees and leverage predictions from multiple sources. They achieve a consistency of O(vP) matching the best-known clairvoyant result but exhibit relatively weak robustness of O(n P). P). We demonstrate how consistency- smoothness trade-off can be achieved with parameterized algorithm. Furthermore, we show how resource augmentation can overcome the poor robustness guarantee, resulting in asymptotically optimal robustness. Through experiments, we demonstrate the practicality of these algorithms. We anticipate that many of the techniques we employ are applicable to other problems.
Many questions remain open for future work. We have not established whether the cubic dependency algorithms. Therefore, analyzing the lower bound on the dependency 17 remains a subject for future study. While we have shown that our construction of RG achieves the best possible trade-off for consistency and smoothness under this method, we have not demonstrated the Pareto-optimalie of the trade-off. Establishing this remains interesting direction for future work. Additionally, extending the approach to parallel identical machines seems be promising direction.
on is optimal for learning-augmenti
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We sincerely thank the anonymous reviewers for their valuable feedback and constructive suggestions, which have significantly improved this work. Professor Albert Zomaya and Dr Wei Li would like to acknowledge the support of the Australian Research Council Discovery Grant (DP200103494), Dr Wei Li acknowledges the support of the Australian Research Council (ARC) through the Discovery Early Career Researcher Award (DE210100263), Dr Tianming Zhao expresses his deepest gratitude to his family. In particular, Tianming is grateful to his wife, Min Li, and his newborn son, Michael Renqian Zhao, for their love, encouragement, and inspiration throughout this journey. Their support has been an invaluable source of motivation.
REFERENCES
Alibaba. Alibaba cluster data, GitHub repository.
Maryam Amiri and Leyli Goohammad-Khanll Survey on prediction models of applications for resources provisioning in cloud. J. Netw. Comput. Appl., 82(C):93-113, March 2017. ISSN 1084-8045. doi: 2.10066/.jnca.201..00
jnca
2017.01.00 016
Anonymous, Experiment code and datasets for competitive fair scheduling with predic- tions. https://anonymous.oooor Swtpppn.cceincc//iiSS.ooomoo 3388, 2024. [Online; accessed Date-of-Access,
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1070-1080, New York, NY, USA, 2021, Association for Computing Machinery. ISBN 978 978145038053,, doi: 10. 0111455/440635535510222
3406325. 345102445122
Yossi Azar, Eldad Peretz, and Noam Touitou. Distortion Oblivvius Algorithms for Scheduling on Mul- tiple Machines. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algo- rithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings Infor- matics (LIPles), pages 16:1-16:18 18, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibbiz-ZZetrrum für Informatik. ISBN 97--9998--399 77788-3995977-2555 258-7
doi: 4230:///.11...3321111. ISAAC. 2022. drops. ie http:///cccccccccceeeeceooe
16. URL/ttps:://
Kenneth R. Baker. Introduction to sequencing and scheduling. Wiley, 1974.
Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions. In Jaroslaw Byrka and Andreas Wiese, editors, Approximation and Online Algorithms, pages 74-89, Cham, 2023. Springer Nature Switzerland. ISBN 978-3-031-49881-
Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, and Fanny Paseual. Scheduling with untrusted predictions. In Lud De Raedt, editor, Proceedings of the Thirty- -Frst International Joint Conference on Artificial Intelligence, IJCAI-22, pages 1581-4 International Joint Conferences Artificial Intelligence Organization, 7 2022. doi: 10. 20224963/icai.2222/6666 wtt.:ogggg.......... 20l.2496331223 ccai..iiiiaa../// 2022/636 Main Track.
URL htt.ts:://ooi..oooooooo .org//o...rooooooooooooo 10/011011
Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and stretch metries for scheduling continuous job streams. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '98, page 270-279, USA, 1998. Society for Industrial and Applied Mathematics. ISBN 0898714109.
Michael A. Bender, S. Muthukrishnan, and Rajmohan Rajaraman. Improved algorithms for stretch scheduling. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA '02, page 762-771, USA, 2002. Society for Industrial and Applied Mathematics. ISBN 089871513X.
Anne Benoit, Redouane Elghazi, and Yves Robert. Max-stretch minimization on edge-cloud platform. In 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 766-775, 2021. doi: 10.1 10.1099919949996622211
20211999992922210990 000866.

---

Published as a conference paper at ICLR 2025
Eli Cortez, Anand Bonde, Alexandre Muzio, Mark Russinovich, Marcus Fontoura, and Ricardo Bianchini. Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. In Proceedings of the 26th Symposium Operating Systems Principles, pages 153-167, 2017.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algo- rithms with prediction portfolios. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 40273-20286 Curran Associates, Inc., 2022.
Google. Google Cluster Workload Traces 2019, 2019. |ttp::::: google/ resources: oattaaattt/oooleeeooooeeeeeeeeee 2023-08-20.
Accessed:
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and
Architectures, SPAA '21, page 285-294. New York, NY, USA, 2021. Association for Computing Machinery. ISBN 45034008
doi: 10.1145/3409964.44617777 URL /ww.//di.i... org/
10 00.1145/3409988 344444466777
Bala Kalyanasundaran and Kirk Pruhs. Speed is as powerful clairvoyance. J. ACM, 47(4): 617 617-643, jul 2000. ISSN 0004-5411. doi: 10.1145/377476.347777.. URL hRtpp:t::///oi. 10 10.1145/347476.32
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Thirty-Firsl Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA '20, page 1859-1877, USA, 2020. Society for Industrial and Applied Mathematics.
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 28-24J0 Jul 2021. URL httppe///ppceeeiingg........eeee
.html
Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. On preemption and learning in stochastic scheduling. In Proceediiggs of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 21-27 Jul 2023. URL bettps:/pproceedi.g mlr. wttp://mw.s////22/aaa222222..... pdf
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Bengio, H. Wallach, 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 boouustness-oossistee online algorithms. In Proceedings of the 34th International Conference on Neural Informa- fion Processing Systems, NOPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
trade-offs for learning augmented
Tianming Zhao, Wei Li, and Albert Y. Zomaya. Real-time scheduling with predictions. In 2022 IEEE Real-Time Systems Symposium (RTSS), pages 331-343, 2022, doi: 10. 10/ 2022.00036.
12

---

Published as a conference paper at ICLR 2025
TABLE OF NOTATIONS
See Table for the table of notations used the analysis.
S
Mcaning
the number of jobs job with index release time J job size of Jj job size prediction for Jj completion time of Jj time instant completion time of Jj in the schedule constructed by algorithm A problem instance (in proofs for Section this refers problem input)
J
Pj
C
f
CA
i
a
schedule constructed
some problem instance
prediction error for J,: 7 max PI P1 P
total prediction error: 1) max Sn fB maxis/5. max p By
1)
Pinin Pmax
mininum/maximmm job size: Pinin = mim Sišn Pj and Pinax = max Sis maximum ratio of any two job sizes: Pinas Piim
P
S
stretch of job Jy: S, Cymra
S/
stretch of job Jy the schedule constructed by algorithm S optimal max-stretch for some problem instance T max stretch achieved by algorithm for some problem instance an ordering of jobs
cr-r, 22
S*
SA
π
Prniny Pmax Piins Punnx
mininum/maximum joh size prediction: Pmin min Syn Pj and Pinax = maxisisn
predicted minimum/maximum job size of all jobs
X
prediction error associated with Pim. max Panin
Pinin }
Piin
Pigia
prediction enror associated with Pinax: &p max
Pianx Piana
a-9 relaxed-streee stretch of job Jj at time t, abbreviated as St)
Sy..,
a-9 relaxed-stretch of job J, at its completion, abbreviated as S, when and (3 are clear maximum a-8 relaxed stretch of all jobs: Sa.3 maxisisn Sj.a.s, abbreviated S optimal max-relaxed-strete for some problem instance
Sa,e
S*
SA
max-relaxed-stretchh achieved hy algorithm A for some problem instance T deadline for job J, achieve the optimal max-relaxed-stue
d,
(L())
predecessors of J, (in terms of d,) at time L: (t) = (Jz d. < d,, J, active at time 1} followers of J, (in terms of d,y at time t: (t) = { d.. > d,, J., active at time t} completion time of J, in the schedule constructed by EDF with deadlines d,
(t
CEDF
SOPT
maxx-eeaxed-streee of the optimal schedule for the max-stretch problem the earliest time after which job delays/2-delays J, maximum job size prediction seen by time Pmax. max,, Pi u-3 adaptive pelaxed-stretch of job Jj at time abbreviated as S) a-B adaptive relaxed stretch of job Jj at its completion, abbreviated as S,
T Panax.
s())
Sa.p
maximum a-3 adaptive relaxed stretch: S_. maXigisn Sy abbreviated as Š
S+
optimal www.aadai---lleee--iteeee
for some problem instance /
SA
max eex--aapptvv--elaxaee stteech-stretchh achieved by algorithm for some problem instance deadline for job J, achieve the optimal www.-aapiivv--elledd--tteeee
d;
(t)
predecessors of J, (in terms of d,) at time (t( (Jz de < d,, Js active time followers of J, (in terms of d,) at time t: (t(t) = (Jz d, > d,, Ja active at time f)
(t)
CEDF
completion of Jj in schedule constructed by EDF with deadlines d; max-addppive--rllaxee-trrcchh of the optimal schedule for the max-streich problem
SOPT
Table A table of notations.
13

---

Published as a conference paper at ICLR 2025
Algorithm 2: Offline Scheduling
Data :every job J with release time ry and job size pj Result:scheduuf with optimal max max- stretch T - S 2,j S n. + Pj. P 2 (0)
view set a sorted index-based list.
r, Jo, m8. 0,
while λ ---1
assign d + rJ S5 Pj for S order jobs by increasing dy; tic breaks by smaller pj first and tie breaks arbitrarily for the rest. schedule jobs with respect to this order by always running the active arrived job with the highest priority (the most front the order); let the resulting schedule be
mLs <- max- max-stretch ms < ms. then
10
11
Oo, ms. + m, if every job J, completes later than d, in then
r k
14
else
15
+++++1
16
return do
A MISSING PROOFS FOR SECTION 3.1
An exact minimum (optimal) max-stretch exists.
This a product of the following general result.
Theorem A.1 (Min nin--usrr-deinee-stttttte Fix any positive vector = Y2..,,.... "nn). There exists schedule, for every problem instance, which achieves minimum max-user-deffieed-sreee stretch, defined as Sp maxigiSn Sr where Sr, -
73
In the analysis of this section, of the jobs and always finds a feasible schedule if one exists.
the optimality of EDF: EDF minimizes the maximum lateness
The max-stretch is special case of the max-uuser-definee--ttethhh with r P2. We show a polynomial-time exact algorithm exists. Observe that we can construct an optimal schedule using the Earliest Deadline First (EDF) algorithm if we know the optimal max-stretch. S* the optimal max-stretch, we can assign deadline dj + S* pp to every job Jj and schedule jobs by EDF. This schedule has max-stretch S* by the optimality of EDF. Essentially. EDF uses the deadlines to determine a job ordering and schedules jobs according the job priority indicated by the ordering. We can construct the optimal schedule if we know the optimal job ordering, which bisection search can find on the following set. We let S = 13 1
i,j S n. +
r-- > U be the Pj
set of all intersections (x-axis) of lines y = ry + P3 x and a zero element. Every element x E S corresponds to an order of jobs via assigning d; f- TT + P3 and ordering jobs by increasing dy. One of these orders is the optimal job order. A bisection search on sorted S can efficiently find The pseudo-code of this algorithm is given in Algorithm
The proof for Theorem A.I uses the following observation. Observation A.2. If a schedule exists with max-user max-user-deffied--stee y for any y 2 æ. no schedule achieves max-user-deffime--steetc x, no schedule achieves max-user-defined-stree y for any œ.
there exists a schedule with
æ. Construct another schedule o', which is identical except for the job Js that is completed as the last job in a. Preempt Js in of before its completion and resume Js later so that the ussr-defined-streed for job Jj reaches exactly y.
Proof. Suppose schedule a achieves a max--ssr--deiieed-stee
y. Thus, o' achieves a -effe--ffiee--steee
Suppose no schedule achieves max meex-user-deen wuuer--efined-streeeee æ. Suppose, for proof by contradiction, that there exists schedule that achieves max-unerrdeffine--ssttccch y with y & Construct schedule
14

---

Published as a conference paper at ICLR 2025
o' following the same procedure above to produce o' with max-user-defined-stteeee This contradicts the idea that no schedule achieves moxx-use--dffned--ee z.
We introduce some definitions and notations. Given order of jobs ग , J/: J2:..., Jj.. Jj.) indicating job priority (the more front in the order, the higher the priority is), define the priority schedule with respect to to be the schedule constructed from always running the active arrived job with the highest priority and preempting the running low priority job if necessary; the priority schedule is denoted by (T((.).
For any z E S, define πtх]] to be the job order constructed by ordering jobs in increasing deadlines, where dj = rg + x Ty.. with tie-breaking by smaller 7/j first and further tie- tie-breaking by the smaller job index first (or any arbitrary order). View set S as sorted index-based list S (wo, 31, ,..,,... Zxx Note that æ5 by definition. We have (20, 21 [ar1, 22); --. 1 Fx), [Zn, 0o) forms a partition of non-negative numbers.
Define mapping that maps positive numbers orders of jobs. Order (z) is defined as follows. Set deadline d; r. + x "i for all S S. n. Order the jobs by increasing deadlines. If two jobs have the same deadline, the one with smaller weight (7₂) comes first. If two jobs have the same deadline and size, i.e., the same release times and job sizes, the one with smaller job index comes first (this tie-breaking criterion can be arbitrary). The resulting order (x).
Proof for Theorem A.7 We make two observations: (1) PS(T does not achieve a max-user- defined-stretch 0; (2) (S(x(z)) achieves a mux-user--effmee--steee at most x, for large x. To
and PS(T(z')) achieves max-user-defined-steee at most x'. By Observation A.2 there exists the largest index such that (S(xx(x))) does not achieve a max -aa--uer-dffine--stettee zz. We show that the optimal value for www.eeeeee-eed-steeeeeeeee
observation 2, let x' maxisy<n Py Ey+
min minisss*
exists in interval [zp. 121] where Tp+1 denotes max) ry + if = k. By definition of p.
minissen 75
PS( ([([ap++1)> achieves max- max-uuse--effneed-streee at most Tp+1. Let X be the nax-user-defined stretch achieved by schedule (T(TT=))) Clearly, X* > Zp.
We first show that (=(r()) is identical to each other for all x E (p+1), by showing that (xp)) (x) for any x Tp+1)- Suppose, for proof by contradiction, there exists y E (Ip, 1p+1) such that ve (xxp) a (y). Let be the smallest index such that (Ip)) # (yy) (the k-th elements of L (xx) and (SS)) ) are non-equal). For reference, we let (xx)) = Jq and (z)) = Jr- Clearly, Jg is in front of Jr in V (I,p), but Ji is in front of Jg in (y), by the choice of k. This means that Jg has a smaller deadline than Ji in V
(xp), ), but a larger deadline in M (y). by the definition v.
We have:
Mig + Ip 7/ T1 Zp nu and rg + + 74 + 7
This means that T/ 7 and rg < rı. However, we have:
Tg < y < Tp+1
Ip 7/ 7
This contradicts with Tp+1 being the smallest element (in S) greater than Tp or new element should be in S, by the definition of Ip+1- Thus, we must have (Txx)) = (y) for all y E (Ip, 2p+1). and PS(T(z]) is identical to each other for all (xp.
x" < Tp+1. no schedule achieves a max muu--use--eefiee--stee (m(m(=)) achieves the same max--user-defiied--sttthhh X for all Tp S X is the minimum (optimal) nax--user-define--sttteeee
at most x for any x < X', as
X In this case, If X* 2 Tpt1, no schedule achieves a most æ for any I Ip+1. as PS(T [x]] achieves the same max-user- defined-stretch. X* for all x E [Tp, 1p+1). In this case, PS p achieves the minimum (optimal) max-usser-effinedd-stttchh Tp-1-
For the rest of this section, we restrict our discussion to the max-stretch, i.e., let I' (pi, P5, P.,) in the max--user-defiieed-steeedd
and prove Theorem 3.2 We can find the optimal job order with set zi
(S-
{ Ti Ti
-p [1 $ < S n. p # PJ.
- 0} {0}). View set S as a sorted index-based
list S (No, 31, ..... F.x). We have (No. x1), [E 1, Fxk), [Ni,, oc) forms partition of non-negative
15

---

Published as a conference paper at ICLR 2025
numbers. The optimal stretch S must be within one of the intervals. Suppose S [xp, 2p+1 1). where we use tx+1 to represent oo for convention. Then, PS(T(pp)) achieves the optimal max max-stretch. Lemma A.3. There exists x E S such that PS(T())) achieves the optimal max-stretch.
Proof. This a product of Theorem
Let x² E S be the critical element with PS(x(2*)) achieving the optimal max-stretch. Observe the following property enabling the bisection search.
Lemma A.4. At lease one job Jj in PS(r(x)) completes later than r, p Every job J in (=]())) completes later than rj x Pīj. for &, x².
pfr P..
S,æ xx.
Proof. We first show that (2(]) contains at least one job J that completes later than ry + 2 p for z E S, Tp. Suppose otherwise for proof by contradiction. There exists & S, < Ip such that every job Jj completes no later than + 2 p in ( Then, we have the max-stretch of (S( [ē]) to be at most à < Tp. which contradicts the fact that the optimal max-stretch is at least Tp-- We then show that every job Jj (T(((( completes
later than Fj + + --, for S, > Tp. If a E S, x > Tp, then it holds that x 2 1p+1 > S Since there exists a schedule with S* max-stretch, where every job J completes no later than ry + S* Pj. schedule where every job J, completes no later than r, + x Pz exists for St. By optimality of EDF, (S(T(x)) (a > 2p) must ensure that every job Jj completes no later than its deadline, rj + x.P... P).-
Lemma A.5. Algorithm admits an Onn² log n) implementation.
Proof. Computing S takes (n²)) time, as there are O(n²) pairs jobs. For the same reason, S has O(n²) elements. Sorting S takes (n logn?) O(n log n) time. We sort all jobs by their release time before entering the bisection search, which takes O( log n) time. The bisection search loop experiences Olog n²) (log n) iterations. Consider any iteration. Computing the job priority takes (n) + (n log n) = On log n) time. Computing the priority schedule with the static job priority takes (n log This is achieved by maintaining a priority queue of active arrived jobs and processing events, including job release and job completion. There are Onz) events for job release and job completion. Every event takes (log n) to process with the priority queue. Apart from computing the priority schedule, the rest operations in the iteration take (nn) time. Therefore, an iteration of the bisection search takes O(n log n) O(nlog n) O(n) = O(n log n) time. The overall complexity is:
On log n) O(log n) On log n) On log n)
Theorem A.6 (Theorem 3.2 Restated), Algorithm 2 finds an offline schedule with optimal max-stree stretch in time polynomial in n. It admits an On² log n. implementation.
Proof for Theorem 3.2 Let the optimal stretch be S*. Let Zp E S such that PS( [Ix]) achieves max-stretch S by Lemma A.3 We show that one of the bisection search iterations visits the Tp and finds the optimal job order T [xxpp. First observe that the bisection search procedure terminates within a finite number of iterations. Let 44 denote the left and right ends the searching interval at the start of the i-th iteration of the search (initially, lo 0 and ro [S).. We show the invariant that, if 4 < < rt, either the i-th iteration finds Ip or 4,41 S < r++1- The i-th iteration finds Tp if 4+r; = p. We consider the other two cases: [ < p and ['etr: > p. Suppose I [ < p. With & < at least one job Jj in PS( (x)) completes later than ry + a pj in this iteration by Lemma A.4 Then, we have 4+1 = + S (by k. both integers) and p < ri Ti+1- Suppose + Tx P in this iteration by Lemma A.4 Then, we have 1++1 4 < p and < k 1++1- Observe that we have le 2 Te, where e is the total number of iterations, at the termination of the search. This means that one of the iterations must visit the 2n and finds the optimal job order л [[rp)). which shows the correctness the algorithm. Further, Lemma A.5 shows that the algorithm admits a polynomial-timg O(n² log n) implementation.
> p. With & > p, every job Jj completes no later than
16

---

Published as a conference paper at ICLR 2025
B MISSING PROOFS FOR SECTION 3.3
Theorem B.1 (Theorem 3.5 Restated). No c-competitive deterministic algorithm exists with < n for online non-clairvoyant max-stretch scheduling, even if all jobs are released at time 0.
Proof for Theorem 3.5 We use proof by contradiction. Suppose there exists c-competitive deter- ministic algorithm A with < n. Consider identical jobs all with job size to be released at time O. Run A against this set of jobs. Without loss of generality, let J1 be the job with the least amount of the processed size 4, We have S by the pigeonhole principle.
Construct the problem instance consisting (n 2 2) jobs to be released at time 0, with job sizes Pf 1 + e, p5 = 2
+ c), P3 = x/² sb P = 3/3 x² P = -h =6=-? Here, Pj = 1/2 2/2- for 2 3, and x/ is a large constant v/- max n=c and is small constant m - }. Observe that 1 Run A againstt this job set. Since the algorithm deterministic, job J1 will be completed after time 1. The max-stretch achieved by A on this instance is more than
1/
0 and thus > 0 by the definition of e/.
pi = 1/(, + c) i+n-- Consider
n
the schedule that runs J1, J2.,.., ..., Jn sequentially in the order of job index. The stretch for job J1 is S = 1. The stretch for job 1/ is S2 = 4/66 for j 3. The stretch for job Jj is:
e). Observe that job J, completes at time z
yir
2 2レンー
for all j 2 Observe that w- and e-1 2 / 1/ 1 - <) by the definition of e. Thus, the max-stretch achieved by this schedule is most I However, we have the ratio between the max-stretch achieved by A and the optimal schedule more than:
u
--1 Therefore, the minimum max-stretch for this job set is
n
1+e n2 I
1 n (1 c.
c
which contradicts the competitive ratio of A. Theorem B.2 (Theorem 3.6 Restated). RR is n-competitive for online non-clairvoyant scheduling.
Proof for Theorem 3.6 With RR, job J is processed by at least p amount during time Ty (when the job arrives) and r + pj. Therefore, Cj I ry + pt and Sy S n for every 1 I j n. We have max-stretch- = maxi<jst S; S n = n 1. Observe that the optimal schedule has max-stretch of at least 1. Therefore, RR n--compeittie.
We observe instantaneous fairness achieves global fairness under the non-clairvoyant setting. This processor-sharing policy is necessary for non-clairvoyant scheduling, i.e., any algorithm must adapt a certain degree of processor sharing be competitive. We define processor-sharing follows.
Definition B.3 (k processor-sharing). An algorithm is said to be processor-sharie for a problem instance 1, if it holds either (1) J, is completed before i, or (2) Jj has been processed for least t- unit, for any job J, and any time instant E [ry, oo), in the exccution A on I.
Intuitively, a & processor-sharing algorithm allocates at least unit of processing power to all active jobs. By definition, RR is n processor processor-sharing for every problem instance. We show the criticality of processor-sharing in obtaining competitiveness in online non-clairvoyant scheduling.
Theorem B.4 (Equivalence of Competitiveness and Processor-sharing). In online non-clairvoyant scheduling, deterministic algorithm c-competitive if is e S* processor-sharnng for any problem instance I with the minimum max-stretch S", Any c-competitive algorithm must be c processor- sharing for every problem instance
Remark B.5. Any k processor-ae processor-sharing algorithm (for every problem instance) is ka processor- sharing for any k; < k2. As a corollary of Theorem B B.4 any l processor-sharee algorithm (for every problem instance) is k-competitive.
17

---

Published as a conference paper at ICLR 2025
The proof for Theorem B.4 uses the following bound for the minimum max stretth Observation B.6. The minimum max-stretch is at most n for any problem instance with jobs.
Proof. The max-stretch obtained by RR on any problem instance is most n. Therefore, the minimum max max-stretch for problem instance 7 is at most n.
Proof for Theorem B.4
Fix problem instance. If an algorithm is S* processor-sharing for that instance, every job J completes before + c S" PP with S3 S c= c S" The max-stretch is at most times the optimum, so the algorithm is c-competitive. Below consider the reverse.
Let A be any c-competitive algorithm. Suppose, for proof by contradiction, that there exists a problem instance / with minimum max-stretch S*, such that there exists a aob Jj and time instant d'-r at time t'. Construct another en
I' E [ri, 20), where Jj has been processed for less than instance I', which contains the same job set as except for the job J, with p} - q. Run on I'. The schedule is the same as the one generated for / before and at time f'. Therefore, J, is completed n. The minimum max-stretch
after L' for I' The max-stretch achieved on I' is more than '-u for I' at most n by Observation B.6 Thus, algorithm A achieves a max-stretch on l' more than c times the optimum, which contradicts the competitive ratio.
Theorem B.7 (Theorem 3.7 Restated). Any non-lazy algorithm is (n (a--1), 1). P 1-competitive.
Proof for Theorem 3.7
Pick any job Jz. The algorithm is processing active jobs in time [ry. Cj]- (n Piuas +rain. (n 1) P+L 1 and max-stretch max1gs5n Sj s
We have Sj
Ci-ry
Pint
(n- 1). P 11
C MISSING PROOFS FOR SECTION 4.2
Define heuristic relaxed-stretch based parameters and B (a < (3)
Definition C.1 (a-3 Relaxed-Stretch). Define a-ß relaxed-stretch (),n, for job Jj at time I given and 3: (() i-1 if Jj is active at time and Pj Sja,(()) f if Jj is active at time and pj > a. use Sja,8 to denote the a-3 relaxed-stretch at the completion of job Jy: Sya,.3 G-rri if p3 a: SS Ci-T Pý > a. Fixing a problem instance of a
3
online scheduling with predictions and schedule, we use max-relaxed-sttrichh denoted by Sa,8. to represent the maximum a-3 relaxed stretch of all jobs: Sa,6 maxisjen SJ,.3 We drop the subscripts a and 33 from the notations when the context is clear for simplicity. We also drop the prefix a-3 when the context is clear.
Classify jobs into short and long jobs according their job size predictions, with given and (.. Definition C.2 (a-3 Short and Long Jobs). Given parameters and 3, a a.job J is said to be short if Pj S o: a job J, is said to be long otherwise.
Fix problem instance /. Run RG. Let SRG and S* denote the max-stretch achieved by RG and the optimal max-stretch of Let 5RG and S* denote the max-relaxed-ssretaa achieved by RG and the optimal max-relaxeed max-relaxed-streeel of I. The quantity S* exists due to Theorem A.1 regardless of values of a and B3. We study the relations between SRG SRG, S*, and S*. We begin with showing SRG 3 St. We consider how much RG differs from optimal execution by examining the maximum amount of processing units a job can be delayed compared with the optimal schedule. Define d, to be the deadline of completing job J, to achieve the max-relaxed-stretto i.e.,
d, = r + S. a for short job Jj and ă, r, + S* 3 for long job Jy. A schedule achieves the optimal max-relaxed-stredd if every job J completes no later than dy. We study how much any job Jj be delayed after d, in RG.
18

---

Published as a conference paper at ICLR 2025
Observe that EDF finds a feasible schedule meeting all deadlines if one exists. The schedule obeying EDF with deadlines d, achieves the optimal max-relaxed-stretee St, Define set (t) {J dz I J active at time f} and set F) (t) [J2lde > d,. Juz active at time t) to be the predecessors and followers (in terms of the deadlines) of J at time t.
Definition C.3 (Definition of Delay). Job Jj is said to be delayed by another job Js time 1, if the following four conditions are simultancously met: (I) J is not completed or not released at time t, (2) J& E (1). (3) (L) A 0, and (4) RG is processing Ju at time with max m, (,) (1) Sa)).
If of and CffG denote the completion time for J, in the (optimal) schedule constructed by EDF with S and the schedule by RG, it follows CP 2 CFDF + +San job delays J time dt. The following
two lemmas hold with any given a and (ax < ().
Lemma C.4 (No Job Delays a Long Job). A long job is never delayed. for any a and B (a < 3).
Proof. Fix any long job Jj and time t before the completion of Jz- Suppose, for proof by contradiction, that another job Jk E (t) delays Jj at time t. Job Jj must be a short job, since otherwise, we would have ry rk and (,) Sa(t). We also have di dz rk St
- rs + St - rk > Ty. Thus, J is active at time t. We have:
3,(0 < 5%))) 3
r
t- 1>
Kk Tk 3 rg.
a
B 3-6 a
Observe, by the definition of delay, that Jk E [1) implies rk + + .
> rj
St 33. It holds that:
(r, 5t B 3- St a) r3 a = + Sr 1 dj
3-a
Thus, no job delays J/ before time dy. In such a case, however, Jj completes no later than dj. which earlier than f, contradicting the definition of delay.
Lemma C.5 (Bound on the Delay for Short Job). A short job Jj completes no later than r - for any a and 3 (a= < B).
Proof. We claim that any short job J, can only be delayed before time dy. i.e., some job Js (t) delays J at some time t implies < dj. We show this via proof by contradiction. Fix short job Jj- Suppose another job J/ (t) delays J, at some time t 2 dy Job Jj must be active time t. Job Js must be a long job, since otherwise, we would have JR E (1) implying da > dj.. which means Th rj and (,) > (t). We have:
3,01) < Sa(() = 1-rg 1-
T3 B a
+ t<
3
B
With Js E (t), holds rk + S 33.33 1331 rj + S5' a. We have:
t rg. (r, + S a 5 - =r, -r 3 a
which contradicts Js delays job J, at time 12 22
Next, consider any short job Jy. Define 7, to be the earliest time after which no job delays Jj. i.e., for any time & after Ty and before the completion time of Jj. the processor always processes a job from (1) when (1) * 0, and Tj is the earliest time instant such that the condition holds (Tj is the last time Jj is delayed). Consider set (T,) Observe that every job J. PT5(T) is delayed by the job (call it J2) running at time instant Tj, since de < d, and dy < dg. It follows Py(TT) contains only short jobs, by Lemma C.4 Observe that, for any job J. (T;)), have Tj S dz,
19

---

Published as a conference paper at ICLR 2025
equivalently r. T - S a, as job Jz is delayed at Ty. We bound the total amount of delay on Jj by E.,tP)(TT)) P. Consider the optimal schedule constructed by EDF with St, We have two cases.
Case 1 (T₃ < ry). In the optimal schedule, all jobs in P5 (Ty))) are released no earlier than Tj S and later than Tj and completed later than Tj S* a. We have:
Σ
P SoJ+ 5t a a-
(T) ( 5 a)) = 2
(.))
Case (Ty 2 r.y). In the optimal schedule, all jobs in (Ty) (including job Jj) are released no earlier
than Tj S* and completed later than d, =r rj S We have:
Σ
P s - - St a) - = --.
J. (T,))
Thus, the completion time for a short job J, in RG most d, + Ph 53
Let Sj and S be the relaxed-stretch of Jj in the schedule constructed by EDF with S and RG.
Lemma C.6. For any given a and 3 (ax < 3), holds 5h6 S St for any long job J, and S < 3.5 for any short job J.-
Proof. Pick any job Jj. If Jj is long job, it follows by Lemma C.4 that:
CR
CEDF
dt = C5DF S S $ S-
Jnny job delays satime
If Jj is a short job, it follows by Lemma C.5
that:
SPG
RG
rj <
33 -r 3
a
Denote SaG and SRG to be the stretch and the relaxed-stretch of job J, in the execution of RG. The
following lemmas show the relation between S" with S* and S with SRG by using / Drax and B Pmax- Lemma C.7 requires a < 3 and Pj S for all S S to hold; Lemma C.8
/3
requires the specific values for and 3 to hold. They do not hold under any arbitrary and B.
Lemma C.7. S S , any given a < 3 and pj S for all S S
Proof. Denote SOPT to be the max-relaxed-stretch of the optimal schedule for the max-stretch problem (the schedule with max-stretch S*). It follows S < SOPT. Consider the optimal schedule with max-stretch S*. Let Cj and SOPT denote the completion time job Jj and the relaxed-stretch of Jj in this schedule. Pick any job Jz. follows Pj S a and SOPT = C7-r, < G7
Pj
G- < 7 S", if Jj is short job. It follows P, < B and SOPT G7
3 < Gi-ri
<
P5 n
Pj
G- S if J, is longjob, Combining these two cases gives S < SOPT S². 0
P
Lemma C.8. holds S.G < 13- .V vP. Sff
for any long job Jj and S < 7
Vp VP. for
v3
any short job Jj, with /Pmmn Prnax and Pmax-
v3
20

---

Published as a conference paper at ICLR 2025
Proof. Pick any job Jz. If job Jj is long job, it holds that Pj
>
Pmiin Panax
We have:
v/
CRG
rj
CRG
rj
B
<
SRG
B
< <Sfo 11 v3.
Panax
Pj
B
Pj
Pj
v
Vmmin Pmax
I SRG 17 v3.
Pmax
SRG
17 v3-
1 P-maaxx
v3 1/2
V
Pmin
P Pinin/1
If job J, is short job, have:
SRG
CRG rj
Pj 2
CRG
CRG
rj a
S ShG.
v n Puain 17 Pinax
< VP
Pmin
Pmii
v3. Pinia
v3
Piin The derivation uses the observation: Pmax 1) Pinaxe Pmnin
and Pmnn S 1] Pimin
4
Combining the above results completes the proof for Theorem
Theorem C.9 (Theorem 4.3
Restated). Relaxed Grexed is v3 n7² VP Cc-coptttie for online
scheduling with predictions.
Proof for Theorem
4.3
Consider the execution of RG. Pick any job Jj. If job Jj is long job, we
have, by Lemmas
C.8
C.6.
and
C.7 that:
SRG S v3 1/2 P. Sfc S v
1/2
VP.
S S v3 of S*
If job Jn is short job, we have, by Lemmas C.8
C.6
and
C.7
that:
sg < V3
.p. SRG
<
< <33-7 S
v3
Therefore, we have SRG = maxisisn S < / vp.S" RG is v ..p...VPPPar VP-competitive
We show that RG is O(n P)ccopttiee with the worst-case predictions.
Theorem C.10 (Theorem 4.4 Restated). RG is (n - 1) P + 1-competitive with arbitrarity bad predictions, and this bound tight.
Proof for Theorem 4.4 The non-lazy RG is (n 1) P 1-competitive by Theorem 3.7 To see the bound is tight, we show that, for any small 6 > 0, there exists a set of n jobs with the associated predictions such that the max-stretch obtained by RG is at least (n 1) P+ 1 times the optimum.
Construct jobs: pi = 1, = P1 p2 3 and
Fix any 0 < e < Let (n-1)
P = P.r, = (1 - (1- P.p, = for all j 2 2. For this instance, we have Pmin = 1 and Pmax = P1- The optimal schedule processes job J1, J2. ..., Jn in order and has max-stretch + p. Algorithm RG will classify job J1 as long job and the rest as short jobs. In the execution of RG.
J1 is processed in the intervals (ry + -
(t) < St()) for (ry - C CR9
for all 2 n. Thus, before CRG job J1 has been processed for most:
w) + (j 2) P
(1-w)+
= (1 w) +
<
At CRG jobs J2. ..., Jn are completed, leaving J1 to completed at time (n - 1) P 1. The max-stretch obtained by RG is (n 1). P P+ 1, which is (n 1). P times 1 + f. the optimum max-stretch.
We show RG's performance for its run-time and space complexity and preemptions.
Lemma C.11. A short job Jj remains have the largest relaxed-stretch among active jobs for all time 2 t' before its completion if it had the largest relaxed welaxed-stretch among active jobs at some time t.
21

---

Published as a conference paper at ICLR 2025
Proof. Suppose job J, has the largest relaxed-strette among active jobs at time t'. For any short job Ju active at time t', we have (t)) 2 (t')") = Tj I rk. Fix any time 2 t', Any short job Jr active at time (including those released after (') has rj S T3 and, thus, () 2 (t). For any long job Ju
released after (', we have tr Lr active at time t', we have
(1) 2 (1), as S rk and a < B. For any long job Jn r'
3
p.r 2 t B.r,- Prr.-a-r
S,(t) 2 St))). O
Theorem C.12 (Theorem 4.6 Restated). Relaxed- admits an implementation with O(1) run-time to make any online decision and (n)) space.
Proof for Theorem 4.6 Main two First-In-First-O (FIFO) queues: short queue and long queue. The short/long queue contains short/long jobs in order of release time. The algorithm always processes the job with the largest relaxed-strede at the front of the two queues and removes a job from the (front of the) queue when the job completed. We claim that one of the jobs the front of the queues has the overall largest relaxed-stretce
any time L. To see this, it holds that ry S Tk 1-1 t-rk
o
(,(t) (t) for any short jobs J. and that r, S 1 1- S) 2 St(t) for any long jobs Js. Therefore, Lines 17 and 22 Algorithm 1 each require O(1) time to run. The rest operations take O(1) time to run. Finally, since the algorithm maintains at most all jobs in memory and constant number of support variables, the space required is O(n).
Instead of running JobSwitch at every time i, the algorithm may compute a critical time e' such that t'-r =" if a long job J is currently being processed, where Jj and J3. are the short (if there a are any) and long jobs at the front of the queues. Update or re-compute this t' if Ju is completed, or a new short job is released when there is no short job prior to the job's release. The algorithm calls JobSwitch only at time t', which minimizes the number of function calls. This is supported by the observation that JobSwitch is executed only when long job is being processed by Lemma C.11
Theorem C.13 (Theorem 4.7 Restated). Relaxed-Greedy generates schedule with at most n. 1 preemptions. Thus, the amortized number of preemptions per job is at most 1.
Preemptions are triggered by JobSwitch, which is not triggered while a short job is being processed by Lemma long job may be preempted by short jobs; these short jobs, however, will not be preempted by Lemma C.IT Thus, the number of preemptions is bounded by the total number of short jobs. which is at most 1. No preemptions occur if all jobs have the same job size prediction. Therefore, the amortized number of preemptions (per job) is at most
Proof for Theorem 4.7
D DISCUSSION OF THE CONSTANT IN RELAXED-STRETCHE FOR SECTION 4.2
We show that replacing the constant v3 in a with any other constant maintains RG's competitive ratio, long as < B. The idea applies to the family of RG-based algorithms, including ARG, PRG, RG". and their RR-augmentations, For simplicity, we focus our discussion on RG.
Fix any constant μ (μ parameters and 8, we (re-)use the definitions, lemmas, and notations from Section 4.2
Panin
Set
Pamin Pmax and 3 Pmax in RG. It holds < B. With
Panax
We show
the following theorem.
Theorem D.1. Golaxed-Greedy is max(u, 3) . PP-competitive with Pmaxx and μ >
/Pmin Penax
B
1
Punin
for online scheduling with predictions.
Pmnax"
22

---

Published as a conference paper at ICLR 2025
Algorithm 3: Adaptive Gelaxed-Greedo
Data :job size prediction pj upon job release and a prediction minimum job size pmin
scheuue with max-stretch O( 1/ vP) times the optimum max-stretch
Pmin t- Punius Pmax & 11 +- -1,
for jop Function relaxedStretch (j,0) // computes adaptive
J) at if Jj is completed before then
L t + C C2
if Pj S Crry then return t-ri
else
1-15 Rr5
return
Event Function JobRelease job Jj is released at time Fj
10
U then run J3 on the machine.
11
insert Jy into U.
13
Pmax max(pmax: PO).
Pmnin Pmax 3 max(pmax: a). ary + a, Brg +
v3
14
The other functions (JobComplete, JobSwitch) remain the same as in Algorithm
Proof. Consider the execution of RG. Pick any job Jj. If job J, is long (pj > a Pamin Pinxx
we have:
shG
CRG
CRG
B
<
SRG
SRG
1
B
SRG
7) P
Pmaa
3
P2
Pj
Pmin Pmnx
< sff 17
1) Piaxx
p 17 VP. SfR S np² vP. S S
Pmnnn/1
where the second last inequality is by Lemma C.6 and the last inequality is by Lemma C.7 If Jj is a short job, we have:
RG Ts
RG
CRG
sho
Tj
SRG
Pmmin Pmax
P'ii
a
Piin
J Pmii
< SRG
vn Pmin 77 Pinax
7 VPP.
SRG
St S
3 P.V.VP..
17
μ P'in
p
P
where the second last inequality is by Lemma C.6 and the last inequality is by Lemma we have gRG maaxsjjs sho max u 11) 173 S*.
C.7
Therefore,
The implications of Theorem D.1 are as follows. Altering the constant v3 a preserves RG's On1² /P) competitive ratio, i.c., the choice does not affect the asymptotic performance guarantee. This opens the door to searching for the appropriate constant for specific applications via algorithm enginecring. In addition, choosing μ v3 yields the optimal constant in the competitive ratio, as v3. This justifies our choice of max 2 n1 2 v3 for all μ > 0 and the minimum is obtained v3 in the definition of a.
E MISSING PROOFS FOR SECTION 4.3
We introduce subscript t to denote the value variable at time t. Thus, Pmax at time (denoted by Pmax,)) represents the maximum job size prediction seen far, i.e., Pmaxxt max,, st Pj- Parameters a and 3 are functions in Pmii and Pmax and thus are time-varying. They are updated with
/a Pmaxx
updates of Pmax in JobRelease. Formally, ARG sets a
and 3r max at).
/3
23

---

Published as a conference paper at ICLR 2025
where ay and Bt denote the values of and B time t. We record dry and Br, for every job Jj- These values are used to compute the adaptive relaxed-strett stretch of J.. defined as follows.
Definition E.1 (a-3 Adaptive Selaxed-Stretchh) Define a-B adaptive relaxed-stretch Sha, (t) for job 4-1 Jj time given and B: Sj.a,s()) (-rj if Jy is active time i and pj S <Or, (t) P.; dr; if J3 is active at time and Pj > ary We use $3,a,5 to denote the a-3 adaptive relaxed-stretch at the completion of job Jj: Sj.,, = C,-ra if Pj S Orry; Sj.,, C,-r, if Pj > ary Fixing schedule, we use suuu-aulppiive-reaxxe---ttte
ary
3r;
denoted by Sa, to represent the maximum a-B adaptive relaxed-stretch of all jobs: Sa,g maxişián S,,..6. We drop the subscripts a and from the notations and the prefix a-3 when the context is clear for simplicity.
The classification of job Jj now depends on the relationship between Pa and oryy Definition E.2 (a-3 r-short and r-long Jobs). Given parameters a and B, a job Jj is said to be r-short if pj S Ory; j J, is said to be r-long otherwise.
Definition E.3 (Minimum max-aadaptiv--rlaxxdd--teeee
We use S to denote the minimum given any and 3. The existence of this quantity is due to Theorem We drop the subscripts a and 33 from the notations when the context is clear.
A.1
Define d; to be the deadline of completing job J, to achieve the minimum max- adaapiiv--relaxxd stretch, i.e., d, = rg + 5t .r, for r-short job J, and di = ry + -3, for r-long job Jj. schedule achieves the optimal muxx-adaptive-relaeee stretch if every job Jj completes no later than dy. Define set (1) - [J N d,,, J2 active at time I) and set (4) = {J > dj, Ja active at time 1} to be the predecessors and followers of J, at time t in terms of minimizing the max-adaptive-relaxxd stretch.
Definition E.4 (Definition of O-delay). Job Jj is said to @-delayed by another job Ju at time I, the following four conditions are simultaneously met: (1) J, is not completed not released at time
1. (2) Ju E F,(), (3) (t) + 0, and (4) ARG is processing Ja at time with max J, 1,)7(()) (t) < (t).
The symbol @ is only to distinguish d-deay from delay; it does not contain any other meaning. We first make the following observation.
Observation E.5. For any x S y. it holds (1) a₂ S Bz. (2) a₂ S ag. and (3) Ba S By. Lemma E.6 (No Job e-delays r-long Job). A r-long job is never @-delayed.
Proof. Fix a r-long job Jj. Consider, for the proof by contradiction, another job Ju E Ft(() O- delays Jj at some time t. Observe that ry < rke since otherwise, we would have dj ry + 5.. 3r, 2 Tk + S* Br 2 dg. Thus, J, is active at time l. Job J/ must be r-short, since otherwise,
1,(1) -r, Dro
t- Lrk (1). We have:
5,(1 < (c(t) + t t-
< t- = Br, > ar and t. > Th Br, - -ry. arr Sr Br, =d;
Br,
Or
Br, ar
where the last incquality is due to dr > d, rk + S ar, rj 5 Bry. Thus, no job Oedeayss
Jj before time dz. However, in this case, job Jj completes no later than d,, which is earlier than t, contradicting the definition of -ddelay.
Lemma E.7 (Bound on the Delay for a r-short Job). r-short job Ju completes no later than ry + 3- St -
Proof. We claim that any r-short job can only be @-delayed before d,, i.c., some job Jj E Ft()) delely J, at time implies dz. We show this via proof by contradiction. Fix r-short job Jj.
24

---

Published as a conference paper at ICLR 2025
Suppose another job Ju (t) O-delays J, some time t 2 dz. Job J3 must be active time t.
Observe that rj > The since otherwise, we would have d, = r + S* ar, S rk + S* ar & dg.
Job JR must be r-long, since otherwise, d2 Tk + S arz rT + St ar, = dj. Then, it follows
de > dj + 5t Bro > >Tj + St Or3 7 Brx > Oryy We have:
(t) > s,( = Th t-rj 7 t [j Br - rk Cr,
< rj + 5 ar, = =d,
3rc
ar,
Brz² Ory
where the last inequality is due to Te > dj + + 5 Bra > rj + 5 ary. It followss d, 1 dj. contradicting that J3 O-delays job J at time dy.
Next, consider any r-short job Jj. Let T, denote the earliest time after which no job Ø-delays Jj. Every job Jz E (T(),) is @-delayed at time Tj by the job J1 running time instant Tj. since de S dj < d.. Thus, every job J2 E PJ(TT) is r-short by Lemma E.6 It follows that, for any job JØ (Ty), dg 1 dy Fx St Or, S ry + S Or; Tw S ry and TO S dg + 12 St T St .r, 2 Tj - Ory We bound the total amount of delay on J, by Σ J..E Pr. Consider the optimal schedule (in minimizing adaptive-relaxed-stteehh constructed by EDF with St. We have two cases.
Case (T₃ < ry). In the optimal schedule, all jobs in PT(T)) are released earlier than Tj SS--ar and no later than Ty and completed no later than Tj + S ay S TT + St Crry where denotes max (2E)(tt)))))) Tw. We have:
Σ
ST ar, - S -t = -- ar,
()))(())
Case (T₃ 2 r,)). In the optimal schedule, all jobs in PT((T) (including job J,) are released no earlier
than Tj S* .Or; and completed later than d, =r 3 S Ory- We have:
P S dz - (T, 5 -r,, +- S ar, - - S2 ar;
(ry)
Thus, the completion time for r-short job J, in ARG is at most dy ELEEEI Pd 53 ary
Let CFDF and CARG be the completion time of J in the schedule constructed by EDF with S and ARG. Let Sj and STAG be the adaptive relaxed-stretch of Jj in these two schedules.
any Lemma E.8. It holds SARG < S* for any r-long job J, and SARG <3. St for any r-short job J,-
Proof. Pick any job Jj. If Jj is a r-long job, it follows by Lemma E.6 that:
CARG
CEDF
dt CEDF SARG $ S any job @-delays J, time
If Jj is a r-oort job by Lemma E.7
it follows that:
CARG rj
(r, + 3. St Ory,) - r3 = 3 S
SARG
Or;
Ory
Lemma E.9. St Sn.S" with 04
Vinin Proxx.
and Br = max max((pmxxxee (pmax,t, 01).
Proof. Let SOPT be the max--alaptiv--rlaxee--ttteee of the optimal schedule for the max-stretch problem. It follows S < SOPT, Consider the optimal schedule with the minimum mtx-stretch.
25

---

Published as a conference paper at ICLR 2025
Let Cÿ and STPT be the completion time of job J3 and the adaptive relaxed-stretch of Jj in this schedule. Pick any job Jz. If job Jy is r-short job, it follows Pj S Cry and SO Cj r S
ar
Gi-Ti S1 11'
Ci S 5n.5" jo Jj is a r-long job, it follows Pj S Sa, Pa- = Pmax.r, = Br,
Pj S n S Combining these two cases gives us and 5OPT G- < - S Gi
Mr
St S SOPT maxigisn S S Sr.
SOPT
Let SARG and SARG be the stretch and adaptive relaxed-streted of job J, in the execution of ARG.
Lemma E.10. It holds SARG < v3. 10.5 .1t.5 vP SARG for any r-long job Jj and SARG <
1g...go. 0.5
VP. SARG for any r-short job Jj. with oN /Pain Pmaaie and 3r = max 0r)-
V3
v3
Pinin Pmnaiiy
Proof. Pick any job J.. If job J is r-long, follows pj aa,
We have:
v3
SARG CARG rj
CARG_ r3
Brg
s sSARG..
Brg
< SARGG
17 v3.
Pmax,ry
11
pj
Br,
D2
Pj
/mmin Pmaxxry
1 SARG 17 V3.
Pmaxxr;
$ SARG
77 V3.
7. Pimax V
v vP. SARG
Pinin
Pminn
If job Jy is rsooort, we have:
SARG
CARG r3
C rj Crs
SARG.
Pmin
1) Pmaxx
10.5 1y
v P. .AAGG
Puin
Ory
Pmni
v3. Pmin
v3
The derivation uses the observation: Pmax, max,, St Pz S Pmax S n Pmaxx for any t 2 0.
Theorem E.11 (Theorem 4.10 Restated). Adaptive Relaxed-Greede is v3. 10.5 2.5 v P. competitive for online scheduling with predictions.
Proof for Theorem 4.10 job Jú is r-llong we have, by Lemmas E.
E.8 and
E.9 that:
5 SARG v3. 055 1 vP. SARG
v 005
1.5
VP. v3
0.5 12 v P. 5
job J, is r-short, we have, by Lemmas E. E.S and E.9 that:
SARG < 00. 1f 0.5
0.5 1 0.5
VP. SARG <
VP S- S
< 0.5 1 5.
S
v3
Therefore, we have SARG < /3. 13.10.3
10.3, , ,2.
VP. St ARG is 1, B.5..VP-coom comopeitiii
Algorithm ARG is (n - 1). P 1-robust. The robustness result is tight by the same construction used in Theorem 4.4 with Pimin 1, where ARG sets a vPi and B = Pı at time 0, remains these
parameters constants, and produces the same result as RG. v3
For proving the run-time and space complexity, as well as the number of preemptions, we first show an equivalent version of Lemma C.11 ARG.
Lemma E. 1.. r-short job J, remains to have the largest adaptive relaxed-stretch among active jobs for all time 2 t' before its completion if it had the largest adaptive relaxed-strette among active jobs at some time t'.
Proof. Suppose job J, has the largest adaptive relaxed-stretch among active jobs at time t'. For any r-ohort job Jn active time t', we have $5(1)) 2 Sa)) d'r,
d'-re rj S Tk-
Dry Ory Fix any time & 1.. Any r-ohort job Js active time (including those released after 1') has
26

---

Published as a conference paper at ICLR 2025
fy S Nh and ary arg thus, St(t) 2 (t)... For any r-long job J3 released after t', we have
t 2 f + (t) 2 Sk (t), as rj S rh and ary S Br, S Brx. For any r-long job Jr active at ary Brz
time t', we have:
t' -rr
Tk
Brx rj Cry Th Bra ar Th S, (t) t'
Or3
3rk
Brc ar,
Br Ory
Therefore, job J remains to have the largest adaptive relaxed-stretch among active jobs at time t.
Theorem E.13 (Theorem 4.12 Restated). Adaptive Relaxed-Greedy admits an implementation
with (1)) run-time make any online decision and (n) space.
Similar to the proof for Theorem 4.6 Main two In--ins-------- (FIFO) queues: short queue and long queue. The short queue contains r-short jobs in order of release time; the long queue contains r-long jobs in order of release time. The algorithm always processes the job with the largest adaptive selxeed-tteetch at the front of the two queues and removes job from the (front of the) queue when the job is completed. We show that one of the jobs at the front of the queues has the overall largest adaptive relaxed-stretch at any time t. To see this, holds that rj I Th
Proof Theorem 4.12
2-71
t-rk + S,(t) 2 (x) for any r-short jobs Jj. Jk and that Ork
Ty S FR Bry maintains at most all jobs in memory and a constant number of support variables, the space required is at most (n).
(-r 2
t-rk (t) 2 (t) for any r-long jobs Jj, Jk- Finally, as the algorithm
8rg
L
Theorem E.14 (Theorem 4.13 Restated), Adaptive Relaxed- Relaxed-Greedy generates a schedule with at most preemptions. Thus, the amortized number of preemptions per job is at most 1.
Preemptions are triggered only by JobSwitch. Observe that JobSwitch is not triggered while a r-short job is being processed by Lemma E.12 A r-long job may be preempted while being processed by r-short jobs; these r-short jobs. however, will not be preempted by Lemma
Proof for Theorem 4.13
E.12 Thus, the number preemptions bounded by the total number of r-short jobs, which is at most 1. Note that no preemptions occur if all jobs have the same job size prediction Pmax. As result, the amortized number of preemptions per job is at most n S1. 1.
F MISSING PROOFS FOR SECTION 4.4
We prove that PRG achieves an O 0.. 17 max(n, p) VP) competitive ratio. With static a and 8, we (re-)use the definitions, lemmas, and notations from Section 4.2 Theorem E1 (Theorem 4.14 Restated). Predictive Relaxed-Greedy is max [. 11) 10.5 00.55
max p} httppp/..//....o..e....... VP-competitive for online scheduling with predictions.
Proof for Theorem
4.14
Consider the execution of PRG. Pick any job Jy. job J, is long job,
have:
SPRG
C.RR
rg.
3
< SPRG. 1 Pj
3 < SPRG
Piax
SPRG 17
Pmaxx Pmii
17 -.
3
P3
V Pinxx
< SPRG n. u.
$. Pmnax
S 1r 0.5 00 n S (By Lemma C.6
V
Pinia/ X
job J, is a short job, we have:
CPRG_ - < SPRG A Pimin 'p Pinxx
SPRG
3 . 0... V (By Lemma C.6
Pinin
# Pini
P
We then bound St by St through SOrT Pick any job Jj. follows SOIT Cir < C C <
Ci-ry Sn jio J, is a short job. It follows SOPT 3
Ci-r,
< < C < p.
Ci < S.
Pinxx
Pj
27

---

Published as a conference paper at ICLR 2025
if job Jj is long job. Therefore, we have 8 < SSOPT= maxigisn SOPT I max ) S", and, thus, SPRG = maxisijn SPRG I max{ μ 2J 10.5 so.s n max (7, 8) S*
Algorithm PRG is (n - 1) P4 1-robust. The robustness result for PRG is tight by the same construction used in Theorem 4.4 with Pimin = 1 and Pinax = P1-
G MISSING PROOFS FOR SECTION
We show that RG is O112+20, p1-*) pl--p commpetivive
Theorem G.1 (Theorem 5.1 Restated), RG (0 S x x 2) is v3 1, pl-x pl-m-pmmpeiitive for online scheduling with predictions.
Proof for Theorem have:
5.1
Consider the execution of RG Pick any job Jj. If job Jj is a long job, we
SAG"
S SRGG'
B SAG"
7) V3.
Pmax
v3 17 p p
7 Pj
Pmin Pinax
< v3 1/ + S St S v3 2+22 p S (By Lemmas C.6 and C.7
If job J, is a short we have, by Lemmas C.6 and
C.7 that:
sfo" SSRG
Pinin S Sfa
a
Pmin Pimnx
1 pl-r
SSR S 2 pl p S
v3. Pinin
v3
Therefore, we have SRG' saxi SRG S V3. nf 242x pl-x.
Theorem G.2 (Theorem 5.2 Restated), RG (with a Pmax: Pmax.. or FIFO, P-competitive.
Proof for Theorem 5.2 We first show RG minimizes maxisjsn Cj - ry (max-flow). If w maxig/Sn C ry (existence of w is due to Theorem/A.I] set , 1idd=-y Ty tw for all j S and run EDF with dz. The resulting schedule, which is identical to the schedule generated by RG achieves the minimum max-flow. Let Jk be the job with the largest flow in the schedule that minimizes max-stretch (e.g.. O have:
maxisisn Cj r5). Consider the execution of RG Pick any job Jj.
SRG RGO
TT
maxisqán CRG rg
maxisg5a C rgg
C -
Tk
P
<
5t
P
Pj
P]
Pj
Pk
Pj
Therefore, we have SRG" maxigiin SRG' S* P.
H CONSTRUCTION OF THE TRADE-OFF ALGORITHM FOR SECTION 5
We introduce parameters 0 (a1, 02 by, b2, 14) and parametrize Piin P and 3 P Paii P in the definition of relaxed-stretch. This section shows the construction of RG", the trade-off between consistency and smoothness under this parametrization.
and C.6 to hold, we must ensure & < 8. For Lemma to hold, we must ensure Pj S for all S I We will enforee these two relations after derive the others desire. For now, we assume that these relations hold. Run RG with the parametrized a and 33. Pick any job Jj. If Jj long job, it holds that pj > a, and have:
For Lemmas
SRG
CRG -r, RG Tj
3
RG
3
SRG 17
P Puin Pmax P ag
b1
7
Pj
3
D
Dj
bz--2 42
12-02 02
b2-az
=SRG
p...
Pmax
ai-bi bb
< 17-
P
ai-bi
S < 4
1j²
a1-bi bi
S* (By Lemma C.6 C.6 and C.7
pmi
Pmin
pmin
28

---

Published as a conference paper at ICLR 2025
If J is a short job, have:
s/
RR
rj
CRG
rj
CRG rj a
Pmin P
a1
Pj
Piiin
Pinin
p Pmin
Pauin Pmixx St < 17
Pmin Pmixx
<
S
(By
Lemma C.6 and C.7
11
Pinin
f
Pinin
3
P
H|a1l
17
(Piin))
11
where the last inequality is due to Pinin S sllarl (Pinin) )ai as Pmin I (1 Pinin = n//oxl (Pini)) )
d1 2 and Pmin
Puiin )-a
) = n11011 (Piin)) )o (1 < 0.
Pinin
The constant term to appear in the competitive ratio is max A), which is at least v (the minimum achieved at = v3). Therefore, we choose = v3 for an optimal constant term. As we aim to relate the competitive ratio to P, the maximum ratio of any two job sizes, we enforce the power Pmax to equal that of Pmii (or Pimin) on the denominator. Thus, we set:
a1
a2
b1 + b2
To enforce a 3,
21 Pmin
81
ppin by
Pmmn yau bj 1, we set:
v3
v3
Panax
2 b1
To enforce P, & 3 for all S S n, or Pmax we set:
S br plaxx Pmin
Prunk
Pinax b1
S 1,
Pintn
b 0
With these constraints, the results (i.e., Lemmas) used in this section can hold.
We have (with a1 + 02 = bj + by and 2 bı):
SRC < //3... 1/2 172 pi
St = 122 (mmax yas bb S S v3. ( Pimxx yar-bs S
1
Pmin
Punia
Pinia
= / 17 2 - 201
poi-b S*
for Jj being a long job. We have (with 02 = a1):
sac < /3 v3.7"" 111al
P 1-01
Pinn
for J, being short job.
Observe that FIFO is P-competitive by Theorem 5.2 We set the power of P and that of Pwas (which Pania
will relate to P) to at most 1, as FIFO will otherwise dominate our algorithm. enforce:
@1 b 1 a 11 <1
and
a 0 0
Fix any 0 < ai 1, decreasing b increases both the power and P in term v3 1,222a -2h Pa- bb S" We choose by = (and therefore by = 1) for the optimal (minimal) competitive ratio.
With 0 = (01, a1, 0, /3), we have:
SIG < / 24201 ped S*
for Jj being long job, and:
SRG S 33. 1 1/
Pmax 1-a; 5* < /3. 13..2t00
1) --Pmax )1 5* v3.,² pp--0 S* Pini
p
29

---

Published as a conference paper at ICLR 2025
for J being short job. Therefore, we have SRG maxisián Sh I 2/3 pmax((r,1=ai)
S For the competitive ratio, RG with 01
dominates that with an 2 + for any
2
0 A 2- Therefore, we restrict:
1
0 01 1
The competitive ratio of RG (with 0 (a1, a1, v3) and a S i) / 22- p1-01 Replacing 0 by x (0 S x S $), we construct RG with Pimm P
and Pmax-
v3
I
VISUALIZATION OF CONSISTENCY-SMOOTHNNNN TRADE-OFFS
The trade-off between consistency and smoothness is visualized in Figure
Figure between consistency and smoothness. gruphs
sager-parameter æ-axis) changes competitive
ratio as function of n (left curve (st of (=)) and P (right curve (n, P. p2 ")), i... the projection plane = (0 S }
represents the competitive ratio as function of and
J MISSING PROOFS FOR SECTION 6
Theorem J.1 (Theorem 6. Restated), Any algorithm is at best 1 n 1-competitive, if given
(L - e)-sped machine, for any 0 < <.<l.
Proof for Theorem 6.1
Construct jobs: Př = 1, = for all 1 < S n. Clearly, the optimal
schedule with unit-speed machine has max-stretch of 1. Run any algorithm with a (1 speed machine. Let the last completed job be J/. Clearly, have C₁ 2 n and l' I 1. Therefore, the stxest achieved is at least S Cu-re I (n 1), which is I-E n times the optimum.
We prove Lemma 6.3 which claims the monotonicity of the algorithms mentioned in this paper. We first show that the RG-based algorithms (RG, ARG, PRG, RG") are monotonic. Our proof shows that (1) any RG- RG-based algorithm has time-varying priority execution for all problem inputs, and (2) any algorithm with time-varying priority execution for all problem inputs is monotonic. We define time-varying priority execution follows.
Definition J.2 (Time-varying Priority Execution). Let A be algorithm and I problem input. We say A has a time-varying priority execution for there exist partitioning time 0 = to S S < ... < tp and mapping F from time partitions to total orderings of jobs (i.e., F(t,, fu+1) an order of all jobs) such that A always processes the active job that has the highest priority indicated by F(tz, 1141) (jobs the front of F(t,, bx41) have higher priorities) during (t.r ta+1) for all 0 < x < P, where (p+1 represents cc.
Here, a problem input differs from a problem instance. A problem input reveals the job size prediction to algorithm when job is released, i.e., problem input includes release times and job size predictions. A problem instance is all the data (release times, job sizes, and job size predictions). Thus, job create different problem instances by attaching different job size predictions. A
30

---

Published as a conference paper at ICLR 2025
time-varying priority execution processes jobs in ttiee-varyingg order that depends solely on the problem input, not the job sizes. This is key to proving monotonicity. Lemma J.3. Any RG-based algorithm has time-varying priority execution for all problem inputs.
Proof. Consider any RG-based algorithm A and any problem input 1. Suppose / include n jobs (J1,...; Jn) where job size prediction for Jj is Pj and release time is T.. Let Vj = a if Pj S a and y/ 33 if pj a for all S I n in the case of static and 3. In the case of time-varying and 3 (for ARG), let 1/j = Ory if P/ I City and yjj Pr, if pj > Ory, The relaxed-stretch (or adaptive-relaxed-stee
in ARG) for Jj at the time t can be uniformly written I-r, for 3i based algorithm. Let = to S t S t2 < ... S tp be the sorted elements in set y. + yj: wi-M 2 0) U (0). where every element corresponds to the solution to equation f- - with variable for some j. Recall that the algorithm runs the active job J, with the largest (-r) at any time t (with tie-brea by smaller job index first). Thus, to conclude time-varying priority execution, we only need to show that the relative priority between jobs (in terms of (-1x) ) for the entire job set remains the same in every interval (tz, f2+1). Suppose, for proof by contradiction, that there are two jobs Ja and Jn with E'-Te- 4' and -"-ra
any - | 1 J
иiー
M/
yj
Vaa
with L' < t" and f,, t" E (12,4x+1 for some T. Then, we have:
< Ya Tb yb Ta <1" < 12+1
1x l'
Ya yb
which contradicts the construction of the time partitioning 0 = to S L1 S/2 S...... Stp.
Lemma J.4. Any algorithm with time-varying priority execution for all problem inputs is monotonic.
Proof. Consider any algorithm A with time-varying priority execution for all problem inputs, any two instances with identical input and actual job sizes (pi...,, P?,) and (pi'.....p" such that pj S pj for all j. Let (22) and ((2) be the max-stretch obtained by A on these two instances, and we denote the schedules by 01 and σ2. To show 5()) < 5(2), we show c.") S <c.²) for all 1 15 S n, where ct and ((2) denote the completion time for job Jj in the two schedules. Let pý (t) and p3 (t) denote the remaining job size of job Jj at time L in the two schedules, i.e., pz minus the total amount
of processing allocated to job Jj up to time L. To show c(I < cfP) we show that algorithm A maintains (2)(()) S p (1) for all S j < n.
O. Let 0 to l1 S ... S. (p be the time partition (for algorithm A running against 7) with a mapping F such that A always processes the active job that has the highest priority indicated by F(tz,tz+1)
We show pj (1) S Pj (1) for all S S n. < la, x 2 1 via induction on x (we slightly abuse the notation to let tp+1 represent oo). The base case is to consider the interval [to, t1). Initially, t1). The ordering F(to.t)) defines the job priority in (fu, t.). Schedules 01 and 02 are processing (either) the same or different jobs at time t. If (t)
(2)
(2)
(1) (0) pJ S Dz' = p3 (0). Fix any time
Pj
they are processing the same job J., it follows
(t) for every job J with priority (2) (t) for every job JJ with priority lower than J.. p (2) (0) Pj
(t)) = 0 p) (t)
higher than Je: pj (t) p (1 (0) <
(1)
It also follows _ (t) < p.
2 (t). as p3 S pp for every job Jj with higher priority than J,. If they are processing different jobs Ja (in o1) and Jh (in σ2), it follows that J, has a lower priority than J, in F(to, 11) and J, has been completed in 0 at time f. Therefore, any job J, with a priority higher than Ja has been completed in 01, i.c., P) (t()) = 0 p, (t): any job J, with a priority no higher than Ja has not been processed in 02, i.c., P3 (t) S S S p5' = p -p))((t) (t). The arguments hold for every t E (to, t1). For the inductive step, suppose (t) <
(t) for all 1 S S n, t < ty for
some k 2 1. Consider the interval [tx, t. By inductive hypothesis, we have p) (1((t)) S pf (te( for all 1 < j < n. The inductive step uses generalized version of the arguments to show the base case. Fix any time E (tx, f.41). The ordering F F(ta, 1x+1) defines the job priority in (tx, 1. If
T and 02 processing the same job Js, it follows pj (1) p. (2) (1) for every job Jj with
(1)
31

---

Published as a conference paper at ICLR 2025
priority higher than J
(() (t) ( (1x) S (1))))))) (1 (1) for every job J3 with a priority lower (1) (1) ps
than Jsi pa
(8(0(() (1), Pj
(2) (1x) S Pj (lx) for every job Jn with higher priority than J.. If
they are processing different jobs Ja (in σ1) and Jo (in 02), follows that 2 (t) 0 S 2 (1) for
any job Jj with priority higher than J. and pj (1) Pp (1x) S (1x) - Pj (1) for any job J, with priority no higher than Ja.
(2)
Lemma J.5 (Lemma 6.3 Restated). All algorithms mentioned in this paper (RG, ARG, PRG, RG", and RR) monotonic.
Proof for Lemma 6.3
Any RG-based algorithm (RG, ARG, PRG, and RG¹) is monotonic by It trivial to see that RR monotonic.
Lemmas J.3
and J.4
Theorem J.6 (Theorem 6.4 Restated). Given a monotonic algorithm A with competitive ratio CA one can obtain a (1 + c) speed min(cA, " h-competttive (RR-augmented) algorithm.
Proof for Theorem 6.4 With (1 + e)-speed machine, we allocate one-unit speed to algorithm A and c-unit speed to RR. That is, for every time unit, both algorithms run in parallel: algorithm A is run at a rate of I+ and RR is run at a rate of I+e' Let the completion time for Jj be Cj in this schedule.
When running A standalone on unit-speed machine, the completion time O satisfies C
maxigiSn Pj CA -e..," where S is the optimal max- and CA is the competitive ratio of O rj S5
algorithm A. Similarly, for RR running standalone with e-speed, we have maxigián where CJ the completion time in this schedule.
25
Due to the monotonicity of algorithms A and AR, have:
C5-Ti-
min(C;
CR) - Tj
max min . S" n S*} = min(cA, n ") S*
max 15J5
max
Pj
1335n
Pj
13j5h
Thus, the combined algorithm achieves competitive ratio of minfcA; -)
J.1 OPTIMALITY OF RG
The proof of Theorem B.1 can be extended to show that "no deterministic algorithm can achieve a n. for online coirvoairvyyant max-stretch scheduling with a machine
competitive ratio better than Itc of speed (1 + c), even if all jobs are released at time 0." The idea of the extension is follows.
Consider n identical jobs all with job size 1 to be released at time O. Run any algorithm A against this set of jobs. By time 1, let Jı be the job with the least amount of the processed size 4, We have 4 < Itc by the pigeonhole principle. We can then construct an instance with n jobs, all released at time O, where the job sizes defined as pj Itt + À and the rest geometrically increasing sizes, i.e., p1 1/2 pi. P5 2 v/. p4 = 4/3 2/2.... .... pM - = where s is large constant and À a small constant. In this setup, the optimal max-stretch using a unit-speed machine approaches while the max-stretch achieved by algorithm A with faster machine least approximately _x... This establishes lower bound for the (1 (1+ cs-ee competitive ratio 1+c" Therefore, algorithm
RG achieves asymptotically optimal robustness under speed augmentation.
K JOB SIZE DISTRIBUTIONS IN EXPERIMENTS
We aim to replicate real-world data size distributions in our synthetic datasets. Figure 8 shows the
job size distributions in the real-world datasets (Google Google (019)), Alibaba Alibabal (2023). and Azure Cortez et al. (017)). Job sizes generally follow an exponential distribution, except for Google's 's data, which has more randomness in the right tail. With the maximum job size ratio P.
set p" max (1, log X A} where X is random variable with X ~ 2d(0 1) and A scaling
32

---

Published as a conference paper at ICLR 2025
Google
Azure
Alibaba
Density
02
0.80
4:28
080
6.0
0.54
6.M
1.00
4.8
812
Job Size
Job Size
Job Size
Figure 8: Real-world Job Size Distribution.
Job Size Distribution (KDE)
0.20
0.15
Densiyy
0.10
Figure Synthetic Distribution
factor ensuring p) < P. Figure 9 shows the Kernel Density Estimation (KDE) of the job sizes in the synthetic datasets, showing that the synthetic job sizes follow exponential distribution aligned with the real-world applications.
L EXPERIMENTS FOR VARIANCE OF STRETCH
1.00
Vanaace
Variance
Variance
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
GWR
RG
ARG
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG+
1.00
Varanca
0.75
0.75
Variance
0.75
0.50
0.50
1-
0.50
+
0.25
0.25
GWR
RG
ARG
AR
RG
GWR
RG
ARG
AR
RG+
GWR
RG
ARG
RR
RG+
Figure 10: The variance of stretch with increasing johs. Fach box represents the distribution of the normalized variance scores.
number of jobs set Jobs seleased in time [o, 5000] uniformly random. The job sizes drawn from [1, 10). The prodiction ervor (i.e., Py p.).
Columa D), (R IC)), (RICL IC), (RCC), 6000 (R2C2), and 10000 (R2C3).
This section presents the experimental results for GWR, RR, RG, ARG, and RG in minimizing the variance of stretch, defined as:
variance of stretch
1
Σ
(S 3)
n
33

---

Published as a conference paper at ICLR 2025
1.00
1.00
Vanaace
Variance
Variance
8.50
0.50
0.25
0.25
025
0.00
0.00
0.00
GWR
RG
ARG
AA
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RA
RG+
1.00
Varlance
0.75
Variance
0.75
Variance
0.75
0.50
0.50
0.50
+1
11-
0.25
0.25
0:5
0.00
0.00
GWR
RG
ARG
RR
RG
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG+
Figure 11: The variance of stretch with an increasing P. The job siacs are drawn from interval [1, P). where P se (RICI). (R (RIC), (RIC3), 10 (R2CI), (R2C2), (R2C3).
of johs at 4500. are released time
[0, 5000) uniformly at random. The prediction error is
where 3 = Sy. The variance of stretch measures fairness from the view of jobs if they are compared to each other. We run the experiments the synthetic datasets under the same settings as Section 7 In presenting the results, we apply a min-max normalization to the variance scores, i.e., dividing the variance by the difference between the maximum and minimum variance of all problem instances under each setting.
Figures 10 and Figure II present the normalized variance score under increasing n and with perfect predictions. The performance ordering of these algorithms generally aligns with that in the max-stretch minimization: a lower max-stretch performance ratio corresponds to lower variance score. RG+ shows its superior performance under all the settings. This suggests that RG+ ensures fairness in resource allocation measured in the stretch space. In contrast, RR suffers the consistent worst variance scores. This worsened performance is the cost of ignoring the job size information in fair scheduling.
GWR
ARG
AR
Variance
32
128
512
Prediction Error
Figure The variance of stretch with increasing prediction The prediction error incresses from 512. The number of jobs fixed at 4500. Jobs are released in time (o, 5000) uniformly at random. The job sizes are drawn from 10).
Figure 12 presents the results under an increasing 77. The variance scores of GWR and RR are constants, as their executions are irrelevant to job size predictions. The variance score of RG and ARG increases with increasing prediction error, showing weakening fairness guarantee with worsening predictions. RG+ demonstrates its robustness in minimizing the variance of stretch under imperfect predictions: the variance score increases slowly and is capped as y) increases. Overall, the distinction in the variance scores is evident: RG+ outperforms the rest, followed by RG and ARG, and then GWR, with RR the worst.
34

---

Published as a conference paper at ICLR 2025
Performance Ratio (Response Time)
Perf Performance Ratio (Response Time)
Performance [ResponSe Time)
1.50
4
1.25
1.00
GWR
RG
ARG
AR
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
AR
RG+
Performance Ratio (Response Time)
Performance Ratio
(Response Time)
w
Per Performance Ratio (Response Time).
2.0
1.5
GWR
RG
ARG
AR
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG
Figure 13: Performance ntios for menn response time with increasing jobs. Fach box represents the distribution
performance ratios. The number of
1000 (Row Columa
(RIC2), 3000 (RIC3), 4500 (R2C1), 6000
(R2C2), and 10000 (R2C3). Jobs are released in time (0, 5000) unifermly at random. The job sizes are drawa from [1, 10). The (i.e. Py p3)
prediction
Performance Ratio
(Response Time)
2.0
Performance Ratio
(Response Time)
Performance Ratio (Response Time)
1.0
0.5
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG+
Performance Ratio (Response Time)
#
Performanc Ratio
(Response Time)
25
Performance Ratio (Response
2.0
2.
2.
15
1.5
1.0
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
RR
RG+
GWR
RG
ARG
AR
RG+
Figure Performance where P is set (RICI) 2 (RIC2 IC2), 5 (RIC)). 10 (R2C1), 20 (R2C2), and 40 (R2C3). The number of jobs is fixed at 4500.
mean response
an increasing
sizes are interval [1. P).
Jobs are released time [0, 5000) uniformly random. The prediction error set to 1.
3.5
GWR
3.0
Performance Ratío
(Response Time)
RG
2.0
1.5
0.5
16
64
128
512
Prediction Error
Figure 15: Performance ratios for the mean response time with an increasing prodiction envor The prodiction envor increases from to 512.
The number of jobs fixed 4500. Jobs are releused in time [0. 5000) uniformly at random. The job sizes are drawn from [1, 10].
35

---

Published as a conference paper at ICLR 2025
M EXPERIMENTS FOR RESPONSE TIME
This section presents the experimental results for GWR, RR, RG, ARG, and RG in minimizing the mean response time, defined
1 n
response time
C rj
The mean response time is used to measure the efficiency of scheduling. A lower response time indicates lower waiting time and an improved quality service. While our proposed algorithms ensure fairness of scheduling, we are interested in whether this comes with a cost in efficiency. We compare the mean response time our algorithms with that GWR and RR. We measure the performance ratio for the response time, defined as the ratio between the mean response time obtained by an algorithm and the optimal value given a problem instance. Shortest Remaining Processing Time First (SRPT) is used compute the optimal mean response time Baker (1974). We the experiments on the synthetic datasets under the same settings as Section
Figures 13 and 14 present the performance ratio for the mean response time under increasing n and P with perfect predictions. RR has the worst performance, as active jobs mutually delay each other when they constantly share the resource equally. The performance ordering of the other algorithms aligns with that in the max-stretch minimization. It suggests that reducing the max-stretch does not come with high cost response time. While RG achieves outstanding performance minimizing response time, its augmented variant, RG + emerges the champion again.
Figure 15 presents the results under an increasing 7/. The performance ratios of RG and ARG increase marginally with an increasing prediction error, showing their robustness in minimizing response time with imperfect predictions. In addition, the performance ratio stays close to that of GWR, even with badly wrong predictions. Though the performance ratio increases that of RG, RG shows its superior performance by its winning performance ratio and the robustness to the prediction error. Overall, RG performs well in minimizing response time while having a strong guarantee for fairness.
N
EXPERIMENTS ON REAL-WORLDD DATASETS
Performance Ratio
GWR
1.40
RG
1.35
AR
1.30
1.25
1.20
1.15
1.10
5
Prediction Error
Figure 16: Performance ratios with an increasing prediction real-world trace-log data from Google Cloud. The prediction increases
from 1 to
Figure 16 and 17 presents the results on the real-world datasets. The data are server trace logs collected from Google, Azure, and Alibaba Cloud. Each dataset contains the arrival time and job size of the jobs submitted to the cloud. We generate job size predictions with a prediction error from I to 6: with the prediction error 1) and job size p", set P, f P exp(Y) with Y ~ U(( log 17, log 17). On Azure and Alibaba datasets, RG and ARG, under a low prediction error, are comparable to GWR, with RR the worst. The performance of RG and ARG gradually becomes worse than RR as the prediction error increases. RG+ consistently outperforms the others. The overall performance of all algorithms on Alibaba and Auzre datasets aligns with the results the synthetic datasets. On the Google dataset, the performance ratios are not sensitive to the prediction error due to the distribution of job size being closer to uniform than exponential. RG+ consistently achieves the best performance. This time, however, RR outperforms RG, ARG, and GWR due to high maximum job size ratio P
36

---

Published as a conference paper at ICLR 2025
Performance Ratio
GWR
350
RG
300
RR
250
200
150
100
50
2
Prediction Error
Figure Performance increasing prediction real-world trace-log Cloud. prediction increases
from 1 to 6.
Performance Ratio
60
RG
AR
50
40
35
25
2
Prediction Error
Figure 18: Performance ratins with an increasing prediction emmr real-world race-log data from Alibaba Cloud. The prediction emor increases
from to
in the Google dataset (compared to the others). RR's performance does not worsen with increasing P, but the others do.
O ADDITIONAL EXPERIMENTS WITH A UNIT-SPEED RG
Performance Ratio
GWR
ARG
4
RE
3
2
2
16
32
64
128
512
Prediction Error
Figure 19: Performance ratios for max stretch with an increasing prediction erorr y,. The prediction error increases from 512. The number of jobs fixed 4500. Jobs released in 5000] uniformly random. job sizes drawn [1, 10].
We performed additional experiments where we set the speed RG+ to be the same as the others. Figures 19 20 and presents the results for max-stretch, variance of stretch, and response time. The label RGF denotes the RG running with unit-speed machine, where 0.3-speed is allocated to RR and the rest 0.7-speed to RG.
The performance of RGF is not as good as RG due to the slower machine, but the performance generally stays bounded in between RG and RR for all metrics. This is expected. The intuition is that when RG performs well on an instance, some portion of the processing is shared to RR, thus decreasing the overall performance; when RR performs well, again, some portion is shared to RG,
37

---

Published as a conference paper at ICLR 2025
0.8
Variance
RR
0.6
RGI
0.4
0.2
0.0
2
8
16
32
64
128
512
Prediction Error
Figure 20: The variance of stretch with an incrensing prediction emoo 1). The prediction error increases from to 512, The number of jobs fixed 4500, Johs released time [o, 5000) uniformly random. The job sizes drawn from 10].
3.5
Performance Ratío (Response Time)
3.0
ARG
2.5
RG+
2.0
RGF
1.5
1.0
0.5
128
512
Prediction Error
Figure 21: Performance ratios for the response time with increasing prediction The prediction increases from 512.
The number of jobs is fixed at 4500. Jobs are released in time (o, 5000) uniformly at random. The job sizes are drawn from [1, 10].
thus decreasing the overall performance. In return, however, the robustness is persevered, making the performance relatively stable under varying prediction errors.
38


Reviews:
[{"review_id": "B9mpS7ekFT", "reviewer": "Reviewer_k4zw", "summary": "This paper uses the consistency-robustness framework to study the problem of learning-augmented job scheduling in multiple settings. The results are provided under multiple settings as functions of different notions of prediction errors, trade-offs between consistency-robustness, and resource augmentation settings. The paper then evaluates the performance of the proposed algorithms using both synthetic and multiple real data traces.", "questions": "The answer to both comments on weaknesses will be great.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-- This is a very well-written paper with a comprehensive set of results both on the theoretical side and experiments. \n\n-- The theoretical results sound solid and consider multiple settings that are common to consider in the analysis of such problems. \n\n-- The experiments are great additions to the paper, especially since the author reports results for both synthetic and real traces.", "weaknesses": "-- Overall, this paper presents a good set of results. However, the authors do not provide insights on the additional challenges with respect to closely relevant prior work and how their techniques and algorithms differ from existing results. The current version of the introduction only states the problem, introduces the notions and preliminaries, and states the technical contributions. There is a big missing part on the challenges to achieve such results and, in doing so, what type of techniques are required. \n\n-- Generally, the paper does not provide predictions based on lower bounds and notes on the Pareto-optimality of the provided consistency-robustness tradeoff.", "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": "FMPOF1la3d", "reviewer": "Reviewer_Lc8Q", "summary": "This paper studies an online scheduling problem where the objective is the notion of max-stretch, which is designed to balance fairness over jobs. Here, the stretch of a job is defined as the ratio of its response time and the job size, and the \"max-stretch\" is the maximum stretch of jobs. There exist some previous works on both offline and online versions of the scheduling problem, but they assume exact knowledge of job sizes. This paper considers the setting where job sizes are not precisely given while some predictions about the values are available. The paper studies several types of prediction models, for which nearly tight algorithms are developed.", "questions": "What is the novel component of this work compared to the previous works on online scheduling with predictions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a comprehensive study of the max-stretch scheduling, not only considering the problem with predictions but also the offline and online problem with exact job sizes (Section 3). \n- This paper considers several settings of different prediction models, concerning job sizes, the maximum job size, and the minimum job size. For all these settings, efficient algorithms are developed with a rigorous theoretical analysis. \n- Trade-offs between consistency and smoothness are also analyzed, and how to improve robustness via resource augmentation is addressed.\n- Numerical results with real-world datasets are given.", "weaknesses": "While the paper gives a comprehensive analysis of the online scheduling problem with predictions, the concept of scheduling with predictions is not entirely new. As very briefly summarized in the related work section, various works exist for online scheduling with predictions. One may argue that this paper extends the literature to the max-stretch scheduling.", "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": "ggApHAYwkK", "reviewer": "Reviewer_xyBg", "summary": "The authors consider the problem of preemptively scheduling jobs on a single machine to minimize the maximum stretch, where the stretch of a job is the response time of the job normalized by its processing time. The jobs arrive online and the processing times are unknown and are only revealed once a job is completed, i.e., jobs need to be processed non-clairvoyantly.\n\nSince the problem admits strong adversarial lower bounds, the authors consider learning-augmented algorithms that initially have access to predictions on the minimum and maximum processing time over the jobs and, for each arriving job, receive a prediction of the jobs processing time upon arrival.  \n\nThe authors give algorithms that achieve a consistency (competitive ratio for accurate predictions) that matches the best-known clairvoyant algorithm, and are smooth w.r.t. a prediction error. Furthermore, the authors show that well established standard techniques are not enough to achieve the best-possible robustness unless the algorithm has access to a faster machine (speed-augmentation).\nBesides this, the authors also give a polynomial-time algorithm for the corresponding offline problem and empirical experiments for the presented algorithms.", "questions": "# Questions:\n\n1. More of a comment than a question: It is interesting to me that your algorithms nearly do not use the predicted processing times and essentially only use them for the classification whether a job is big or small. Maybe you can prove similar results (with different error measures) if the predictions are p_max, p_min and, for each job, a bit that predicts the job to be either small or big.\n2. Theorem 6.1 shows that the blackbox combination of two algorithms will not benefit from the predictions. However, this does not exclude the possibility of a different technique to achieve an improved consistency and a robustness of O(n)? If it does not exclude that possibility, then calling Theorem 6.1 the “Necessity of Resource Augmentation” might be misleading.\n3. Experiments: I assume that GWR gets access to the precise processing times? Any idea on why the competitive ratio does not increase with the prediction error in Figure 6?  \n4. Just to make sure I understand since I was a bit confused reading it: Section 4.3 still assumes that $p_\\min^e$ is given up-front but, in contrast to Section 4.2, it might be wrong even with respect to the predicted job sizes, i.e., $p_\\min^e \\not= \\min_j p_j$ might hold. Is this right?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "# Strengths:\n\n* The learning-augmented results given in the paper are quite complete and answer most of the questions that one could have (consistency, smoothness, discussion of the robustness). \n* The algorithmic ideas are presented in a nice way by iteratively removing more assumptions from Section 4.2 to 4.4.\n* I like that the authors also resolve the complexity of the offline problem with Theorem 3.2. The idea to reduce the problem to deadline scheduling (minimizing the maximum lateness) by finding the “correct” deadlines via binary search over the set of line intersections is very elegant. \n* The fact that Preferential Round  Robin (Theorem 6.1) does not work is a nice separation from many existing results on learning-augmented algorithms for scheduling problems.\n* The experiments seem well-done.", "weaknesses": "# Weaknesses:\n\n* The main part of the paper does not really highlight the techniques that are used to prove the theoretical results, apart from the discussion on the overestimation of job sizes at the beginning of Section 4.1. Since the algorithmic ideas are similar to the Algorithm by Bender et al. (2002), it would have been nice to highlight the differences and challenges in the proof that are caused by using predictions instead of precise processing times. The way it is written now, it is hard to estimate the technical contributions.\n* The appendix could use one more iteration of proofreading. Some examples:\n  * The authors state on page 14 that EDF is optimal for minimizing the maximum lateness, but use it already on page 13.\n  * The phrasing of Theorem A.1 does not seem to quite match the statement that you actually show. For example: If you plug-in the processing time vector $(p_1^*,...,p_n^*)$ in Theorem A.1, then the theorem says that there exists a schedule with minimum max-stretch $\\max_{1 \\le j \\le n} \\frac{C_j-r_j}{p_j}$. However, this holds directly by definition of the problem. For this reason, Lemma A.3 does not seem to be implied by the statement of Theorem A.1, but by the proof of the theorem, which indeed implies the lemma.  Otherwise, the approach of the authors to prove the offline result makes sense.\n  * There are several repetitions already on the first two pages of the appendix.\n\n* Apart from the first point, the presentation in the main part is mostly fine with the following small exceptions:\n  * Lines 038-040: You state that job sizes are typically estimated using ML.  Do you mean in other theoretical learning-augmented results or in practice? If you mean the latter, it would be nice to have a reference for this. \n  * Line 046: I think there are learning-augmented results on scheduling problems with additive errors. Maybe clarify that this refers to your error.\n  * Lines 094-096: I agree that the assumption of knowing the precise processing times may be unrealistic. However, it is a bit strange to use the adversary as an argument since having an adversary might not be a very practical assumption as well.\n  * Related work/offline scheduling: Would be nice to reference  some flow-time (response-time) results and briefly discuss the differences. (As your offline problem seems to be a special case of minimizing the maximum weighted response time, such a discussion seems relevant.)   \n  * Maybe mention a bit earlier that preemption is allowed.\n * Experiments: I am not sure if we learn something by comparing the speed-augmented RG+ to the other algorithms running at normal speed. It seems like an unfair comparison. Maybe it would be more interesting to also run RG+ on normal speed to empirically analyze the impact of Theorem 6.1 on real-world instances.", "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": "czIvksNZ6h", "reviewer": "Reviewer_YoQS", "summary": "The authors consider the minimum max-stretch scheduling problem under the learning augmented framework. Jobs $J_j$ $1\\leq j \\leq n$ arrive sequentially. Job $J_j$ arrives at time $r_j$, has compute time $p_j^*$ and is released at time $C_j$. The goal is to minimize the max stretch, $\\max_{j \\in [n]} \\frac{C_j-r_j}{p^*_j}$.\n\nThe authors present several algorithms:\n- An offline algorithm achieving optimal max-stretch in poly-time, improving upon previous literature where a poly-time approximation algorithm was known.\n- A family of relaxed-greedy algorithms to schedule online under different types of available predictions.\n- An algorithm that explores the smoothness consistency trade-off\n- An algorithm for the resource augmented setting", "questions": "Is the algorithm in Thm 3.1 poly time or not?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results presented in the paper are quite nice and turn in an array of contributions. They address a relevant problem in scheduling under a currently popular and pertinent lense, algorithm with predictions.\n\nThe paper is not very well written but remains relatively easy to parse.", "weaknesses": "The paper lacks insights into the results and techniques. It is currently a list of theorems, and it takes some time to figure out how they are related to each other and what the actual contribution is. Listed below is a list of elements on which the paper could improve.\n\nOn offline scheduling:\n- The first theorem (Thm 3.1) and the first paragraph contradict each other. The Thm says the algorithm is poly time in $n$, the paragraph says it is not. \n- Earliest deadline first is referenced without being defined (defined only in the appendix).\n- The paragraph states that there are infinite candidates for the max-stretch. That is not a convincing argument: with $r_{max}$ the max release time, $U=\\frac{r_{max}+\\sum_j p_j}{\\min_j p_j}$ is an upper bound on the max-stretch. Then there are $U/\\epsilon$ candidates for $\\epsilon$ approximations of the max stretch.\n- The nice contribution of Thm 3.2 is Lemma A.1.: instead of doing a binary search over uniformly spread candidate max stretch, the authors find a list of candidates that contains the true max stretch. This entails that the proposed algorithm is optimal instead of approximately optimal. This is a nice contribution, but it takes reading the Appendix to figure it out.\n\nOn Relaxed-Greedy:\n- Streamline the pseudo-code of relaxed greedy. In its current form, it does not help the reader. Maybe every subroutine does not need to be detailed. (e.g. JobRelease() takes 4 lines but is fairly useless)\n- The main algorithmic idea is the reduction to two job-size, where the criteria for job length classification depends on $p_{min}$ and $p_{max}$. It would be helpful to get this insight earlier: it would help the reader understand the algorithm. It would also highlight why $p_{min}$ and $p_{max}$ play a special role.\n- Thm 4.6 and 4.7: there is too many theorems in the paper, it is hard to tell what's important and what's not. Those two could easily become propositions.\n- Definitions 4.8 and 4.9 are clutter: it is the same as the previous ones with $\\alpha$ replaced with $\\alpha_{r_j}$. If there is a difference I missed it should be highlighted, otherwise, I suggest dropping them. I am also not convinced by the use of vocabulary $r$-long.\n\nOn $RG^x$: \nIt should be said earlier in the text that FIFO is O(P) competitive and that $RG^x$ interpolates between FIFO and the proposed algorithms.\n\n\n\nOn notations:\n- Maybe replace $p_j$ with $\\hat{p}_j$ and $p^*_j$ with $p_j$", "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": "qJl0EfIM6O", "reviewer": "Reviewer_KufQ", "summary": "The paper studies the scheduling problem of preemptively minimizing the maximum stretch on a single machine. It assumes that both job arrivals and processing times are uncertain.  This problem can be interpreted from the perspective of fairness, as an algorithm needs to give every job at least a k-fraction of the processor on average to achieve a max-stretch of at most k.\n\nFor this online problem strong lower bounds (n = number of jobs) on the competitive ratio exist, which is the worst-case ratio between an algorithm's max-stretch and an optimum's max-stretch. Thus, the authors apply the learning-augmented framework to this online problem. That is, they assume that predictions on the unknown processing times are given to an algorithm when a job arrives, and present bounds on the competitive ratio depending on the quality of these predictions. Here, the quality \\eta is measured by the worst case ration between predicted and actual processing times. In the clairvoyant online setting, where an algorithm is oblivious to future job releases but jobs arrive with known processing times, a O(\\sqrt(P)) competitive algorithm is known, which is asymptotically almost best-possible. Learning-augmented algorithms are a recently popular technique for beyond worst case analysis, and have become an established subfield in the intersection of algorithm theory and machine learning.\n\nThe main results of the present paper can be summarized as follows:\n- An algorithm (RELAXED-GREEDY) that uses predictions on the processing times but assumes to know the maximum and minimum prediction at time 0 with a competitive ratio of at most O(\\eta^3 \\sqrt{P}). That is, if the prediction error is small, the algorithm achieve a performance close that of the best-known algorithm for the clairvoyant setting.\n- Variants of the previous algorithms that do not need the assumption of knowing the maximum and minimum prediction value in advance, but instead receive a prediction on these values. The performance guarantees then depend also on the quality of the predictions on these aggregated values.\n- A further variation of the previous algorithm in which the user can control the trade-off between the consistency bound (the bound assuming the predictions are correct) and the error-dependent bound using a hyperparameter.\n- A general method to additionally achieve a robustness in O(n) using a processor that is (1+\\eps) times faster than the optimum's machine (speed augmentation)\n- An empirical evaluation of the proposed algorithms.", "questions": "- In line 86 you claim that your algorithm achieves \"optimal robustness of O(n) with (1+\\eps)-speed\", but I could not find a proof for this claim or a reference to related work. In particular, Theorem 3.5 only considers a lower bound regarding a unit speed processor. It is not obvious to me why this should still hold under speed augmentation, specifically because for other objectives such as total flow time, speed augmentation suffices to achieve a constant competitive ratio [Kalyanasundaram and Pruhs 2000]. I think this is an important question to address, because if a constant competitive ratio is possible under speed augmentation, in my opinion, the result of Theorem 6.4 is way less interesting.\n- Line 418-423: It is unclear in the main part why monotonicity is important. I figured out that it is used in Line 1637 for the proof of Theorem J.6. I do not understand why this property is even necessary for the proof. The proof of Theorem J.6 is not very detailed, so it is hard to understand why monotonicity is important. I think it is not necessary to obtain this result: You run your main algorithm on the speed-1 machine and RR on the speed-\\eps machine, but both work on copies of the actual instance. Whenever one of the algorithms finishes a job which is still running in the other algorithm, the actual job can complete in the actual schedule. However, we can still make the other algorithm continue working on the job because it works on its independent copy, and the actual processing time is known now. Thus, the overall bound is still the minimum of the two bound of the algorithms, and no algorithm gets \"distracted\" by a completion of a job in the other algorithm.\n\n\nAdditional remarks:\n- The idea of a distortion prediction error has first been considered by Azar, Leonardi and Touitou (STOC 21). I would at least add this reference when the error is defined in line 48.\n- Line 60: I think the definition of smoothness and robustness is equivalent. I think smoothness should be explained differently.\n- Personally, I think that stating bounds in the related work section is not helpful. The considered problems are very different and the variables are not explained. Instead, I would prefer to have more references to related work on algorithms (scheduling) with predictions.\n- If you keep the results on the offline problem, I would at least mention in the results section. Otherwise, this comes quite unexpected in the paper, and it is not clear (in the beginning of section 3) what the benefit of this result in the context of the results mentioned earlier is.\n- Line 207: the maximum is not defined properly", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper seems to be the first to consider max-stretch in the non-clairvoyant setting. The results are a nice package and a solid contribution to the area of learning-augmented algorithms. Thus, it generally also fits well to ICLR.\n- The paper addresses the crucial assumptions of knowing the minimum and maximum processing time in advance, which was made by previous works. They show that relaxing these assumptions to prediction information only loses small factors in the competitive ratio.\n- Empirical experiments indicate that their algorithms perform well on real-world data sets.", "weaknesses": "There are two questions that may influence the set of results, and thus, the overall contribution. Thus, I currently value them slightly negatively, but I am open to change this depending on the rebuttal.\n\nBesides that, I think the main weakness is the presentation. I have the feeling that the abstract and the initial parts of the introduction are filled with too many technical details, and are not approachable for the broader ML community. In particular, I am missing a better introduction and highlighting of learning-augmented algorithms and a stronger motivation and connection to machine learning (as ICLR is an ML conference). I think a slightly more informal introduction could strongly increase the readability. \nSome other examples where I got confused:\n- The paragraph on \"prediction errors\" also contains the definition of the prediction model, and moreover distinguishes between several different models, which are hard to grasp at this point in the writeup.\n- Line 87: You mention \"preferential round robin\", but it is unclear what that is or in which reference one can find it.\n- Line 89: In point 4 of the list of contributions, you only mention that you conduct experiments, but not outline any interesting findings.\n- Line 94: Why is this assumption unrealistic? In practice?\n- Line 397: \"This shows the necessity of resource augmentation\". This is a strong claim, and I am not sure if it is correct. Just because some technique does not work, this does not imply that one immediately needs strong assumptions such as speed augmentation.", "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)