Energy-Efficient Scheduling with Predictions
Authors: Eric Balkanski
Noemie Perivier
Clifford Stein
Hao-Ting Wei
Venue: NeurIPS 2023 poster (2023)
Keywords: Scheduling
algorithms with predictions
speed scaling
energy minimization

Abstract: An  important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling,   the operating system controls the speed at which a machine is processing jobs  with the dual objective of  minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since  machine-learned predictions  about future  requests can often be learned from historical data, a recent line of work  on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions.   In particular, for energy-efficient scheduling, Bamas et. al. [NeurIPS '20] and Antoniadis et. al. [SWAT '22]
  designed algorithms with predictions for the  energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining  worst-case bounds even when the prediction error is arbitrarily large.

In this paper, we consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including  energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Finally, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets.

Energy-Efficient Scheduling with Predictions
Eric Balkanski Columbia University eb3224@columbia. edu
Noemie Perivier Columbia University up2708@columbia. edu
Clifford Stein Columbia University cl cliff@ieor columbia.edu
Hao-Ting Wei Columbia University w12738@columbie. edu
Abstract
An important goal of modern scheduling systems efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which machine is processing jobs with the dual objective of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learndd predictions about future requests can often be learned from historical data, a recent line of work on learning-augae augmented algorithms aims to achieve improved performance guarantees by leveraging predictions. In particular, for energy-efficient scheduling, Bamas et. al. [NeurIPS '20] and Antoniadis et. al. [SWAT 222] designed algorithms with predictions for the energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining worst-case bounds even when the prediction error is arbitrarily large.
In this paper, we consider general setting for energy-efficies scheduling and provide a flexible
algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficies scheduling problems, cluding energy minimization with deadlines, while also maintaining bounded competitive ratio regardless of the prediction error. Finally, we empirically demon- strate that this framework achieves improved performance on real and synthetic datasets.
Introduction
Large data centers and machine learning models are important contributors to the growing impact that computing systems have climate change. An important goal is thus to efficiently manage power usage order to not only complete computing tasks a timely manner but to also minimize energy consumption. In many operating systems, this tradeoff can be controlled by carefully scaling the speed at which jobs run. An extensive area of scheduling has studied such online (and offline) speed scaling problems (see, e.g., (I). Since the speed of many processors is approximately the cube root of their power [25 [5), these works assume that the power processor is equal to speed to some power 1. where is thought of being approximately 28 10 and the total energy consumption is power integrated over time.
Online energy-efficient scheduling algorithms have mostly been evaluated using competitive analysis. which provides robust guarantees that hold for any instance. However, since competitive analysis evaluates algorithms over worst-case instances, can often be pessimistic. In particular, it ignores the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Previous results
Our results with predictions
Problem
without predictions
with predictions
Consistency
Robustness
Flow time
2 [
(1 +1+ (2
1+220+1 Ad
Fractional weighted
2 14
None
X
flow time
Integral weighted flow time
O((
a log
)
(1 + (( Tog
a
)²))
1+ ling
2 A X
O 4a ((--))
Deadlines
10
+ A
Table The best-known competitive ratios for energy-efficient scheduling problems, previous work studying these problems in the algorithms with predictions framework, and our consistency and robustness results, for any À E (0, 1]. Note that when À is sufficiently small, the consistency improves over the best-known competitive ratios, while also maintaining bounded robustness. A detailed comparison with the results of 7 4 for deadlines provided in Section 1.2
fact that, in the context of scheduling. future computation requests to computing systems can often be estimated from historical data. A recent line of work on algorithms with predictions aims to address this limitation by assuming that the algorithm designer is given access machine-learned predictions about the input. In the context of online algorithms, where this line of work has been particularly active, the predictions are about future requests and the goal is to achieve improved competitive ratios when the predictions are accurate (consistency), while also maintaining the benefits of worst-case analysis with guarantees that hold even when the predictions are arbitrarily wrong (robustness).
In this framework with predictions, Bamas et al. 7 and Antoniadis et al. 4 recently studied the energy minimization with deadlines problem, which is classical setting for energy-efficient scheduling (see, e.g., [28] (0). However, there are many scenarios where the jobs do not have strict deadlines and the goal is instead to minimize the job response time. In energy plus flow time minimization problems, which are another family of energy-efficient scheduling problems that have been extensively studied in the setting without predictions, the objective is to minimize combination of the energy consumption and the flow time of the jobs, which is the difference between their release
date and completion time (see, e.g., 2 12 14 3))
In this paper, we study a general energy-efficient scheduling problem that we augment with predictions. This general problem includes both energy minimization with deadlines, which has been previously studied with predictions, and energy plus flow time minimization, which has not been previously studied with predictions, as well as many other variants and generalizations. In particular, the flow time problem with predictions introduces challenges that require novel Saaming--uugment scheduling algorithms (see Section 3 for additional discussion).
1.1 Our results
An instance of the General Energy-efficient Scheduling (GES) problem is described by a collection I of n jobs and an arbitrary quality of service cost function F. Each job T.r..PP Pt) E I consists of a release time ry, a processing time Py. and an identifier j (and potentially other parameters such as weights ey or deadlines d,). A schedule S is specified by the speeds sy (t) at which job is processed by the machine time f. The goal to find schedule of minimum cost E(S) + F(S, J). where the energy consumption of a schedule is E(S) = Jizo E, 8, (t) for some constant a >> 0. In the general energy-efficient scheduling with predictions (GESP) problem, the algorithm is given at time = 0 collection J of ń predicted jobs (j, (.f.));),, which is similar prediction model as in (7]. For all our results, we assume that the quality cost function F is monotone and subadditive, which are two mild conditions that are satisfied for the problems with flow times and with deadlines.
Near-optimal consistency and bounded robustness. Our first goal is to design an algorithm for the GESP problem that achieves a good tradeoff between its consistency (competitive ratio when the predictions are exactly correct) and robustness (competitive ratio when the predictions are arbitrarily wrong). Our first main result is that for any instance of the GES problem for which there exists constant competitive algorithm and an optimal offline algorithm, there is an algorithm with predictions that is 1 + consistent and ((1) robust for any constant (0, 1] (Corollary 3.5). Since problems

---

with the flow time and the problem with deadlines admit constant conpeettt algorithms,, we achieve a consistency that is arbitrarily close to optimal while also maintaining constant robustness for these problems (see Table [ for a summary of problem-specine
upper bounds). We complement this result by showing that there is a necessary trade-off between consistency and robustness for the flow time problem: for any À > O, there is no + X-consistent algorithm that is 1/)) 1/A)-robust (Appendix A.2).
The competitive ratio as a function of the prediction error. The second main result is that our algorithm achieves competitive ratio that smoothly interpolates from the 1 + consistency to the constant robustness as a function of the prediction error (Theorem (.4). To define the prediction error, we denote by J + I i J the jobs that are correctly predicted. We define the prediction error \ [+)], which is the maximum between the optimal cost of scheduling the jobs J. \ I+ that arrived but were not predicted to arrive and the cost of the jobs JVJ+ that were predicted to arrive but did not arrive. This prediction error is upper bounded by the prediction error in 7 for the problem with uniform deadlines.
" = [PT(.T] max (OPT(J \
Extension to jobs that are approximately predicted correctly. We generalize our algorithm and the previous result to allow the correctly predicted jobs I+ to include jobs that are approximately predicted correctly, where the tolerable approximation is parameterized by a parameter chosen by the algorithm designer. The result for this extension requires an additional smoothness condition on the quality cost F(S. JJ) of schedule. This condition is satisfied for the flow time problem, but not by the one with deadlines
Experiments. In Section 5 we show that when the prediction error is small, our algorithm empirically outperforms on both real and synthetic datasets the online algorithm that achieves the optimal competitive ratio for energy plus flow time minimization without predictions.
1.2 Related work
Energy-efficient scheduling. Energy-efficient scheduling was initiated by Yao et al. [28). who studied the energy minimization with deadlines problem in both offline and online settings. These offline and online algorithms were later improved in 13 10] Over the last two decades, energy- efficient scheduling has been extended to several other objective functions. In particular, Albers and Fujiwara [2] proposed the problem of energy plus flow time minimization, which has been studied extensively (see, e.g..
18
Learning-augmmented algorithms. Algorithms with predictions is a recent and extremely active area, especially in online algorithms, where it was initiated in [2] 27). Many different scheduling
problems have been studied with predictions (see, e.g., [19 24 17
20 6 21)..
dearning-augmentn energy-efficier scheduling. Energy- -efrrceet scheduling with predictions has been studied by Antoniadis et al. 4 and Bamas et al. 77,, who focus on the problem with deadlines, which is special case of our setting. The prediction model in Bamas et al. 7 is the closest to ours. For the problem with deadlines, the algorithm 77 achieves a better consistency-robusteess tradeoff than our algorithm, but their algorithm and prediction model do not extend to more general energy-efficient scheduling problems such as the flow time problem. In addition, the competitive ratio as function of the prediction error is only obtained in [7] in the case of uniform deadlines where the difference between the deadline and release date of a job is equal for all jobs (the authors mention that defining algorithms for general deadlines becomes complex and notationally heavy when aiming for bounds as a function of the prediction error). Thanks to our algorithmic framework and definition of prediction error, our bound generalizes the non-uniform deadlines without complicating our algorithm. Antoniadis et al. 4 propose a significantly different prediction model that requires an equal number of jobs in both the prediction I and true set of jobs J. Consequently, their results are incomparable to ours and those by Bamas et al.
We note that Bamas et al. 7 give an alternate approach to transform an arbitrary algorithm with predictions for the problem with uniform deadlines to an algorithm that allows small deviations in the release time of the jobs. This approach can be applied to algorithm for the problem with uniform deadlines.
3

---

2 Preliminaries
In the General Energy- Efficient Scheduling (GES) problem, an instance is described by a collection I of n jobs and a real-valued cost function F(S, J] that takes as input the instance J and a schedule S for J, and returns some quality evaluation of the schedule. Each job (j, (i,))) E I consists of release time rj, processing time Py. and an identifier j (and potentially other parameters such as weights vy and deadlines d,). We often abuse notation and write E I instead of (j. Py) E J. For any time interval I, we let Ji = {j E I :Ty E ] be the subset of jobs of I with release time in I. For intervals I = [0, 1) or = [4, oo], we write Igt and Jzt-
A feasible schedule for a set of jobs I is specified by S = (s,())22,ee33 where s()) == Ejedg, 8,(t) is the speed at which the machine runs at time t. Thus, 8,(t)/s(t) is the fraction of the processing power of the machine allocated to job j at time +F] During time interval J, there are J, (t)ddt units of work for job j that are completed and we let S, be the sub-schedule (=),())e, The cost function we consider is a combination of energy consumption and quality cost for the output schedule. The energy consumption incurred by schedule is E(S) = S1z0 dt, where a > 1 is a problem-dependee constant, chosen so that the power at time is s(t) To define the quality of schedule, we introduce the work profile W == {w] (t) her,, of schedule S for job j.
where w (t) = Pj [r (y())d du is the amount of work for j remaining at time t.
We consider general objective functions of the form F J) and the goal is to compute a feasible schedule of minimum cost. F(S. f((WS.))).
F(S.) F(S++
(n)) ) is an arbitrary quality cost function that is function of the work profiles and the jobs' parameters. In the energy minimization with deadlines problem, F(S, J = oc if there is a job j with completion time of such 0 otherwise. In the energy plus flow time minimization problem,
that c5 dg. and F(S, have F(S.J)= = =EEo of - ry (see Section 3.3 for additional functions F). A function F(S, J) is subadditive if for all sets of jobs J1 and J2. we have F(S, U I2) S F() + ((S)J)) F is monotone if for all sets of jobs J and schedules S and S' such that (t) S w (t) for all j E I and / 2 rj. we have that F(S,T)= S F(S', We assume throughout the paper that F is monotone subadditive, which holds for the deadlines and flow time problems. We let (JT and OPT(J)= == (J), be an optimal offline schedule and the optimal objective value.
The general energy-eflicee scheduling with predictions problem. We augment the GES problem with predictions regarding future job arrivals and call this problem the General Energy-Efficient Scheduling with Predictions problem (GESP). In this problem, the algorithm is given at time t 0 prediction I {(ú, } regarding the jobs J = {(j, rj PP)} that arrive online. An important feature of our prediction model is that the number of predicted jobs | can differ from the number of true jobs |
Next, we define measure for the prediction error which generalizes the prediction error in 7 for the problem with uniform deadlines to any GES problem. With J+ = J n being the correctly predicted jobs, we define the prediction error as
1 max(OPT( \ N(t), OPT( \ {tt)], OPT(J)
((IT))=
where OPT(J) \ (+) is the optimal cost of scheduling the true jobs (5 J. Pj) such that either the prediction for j was wrong or there was no prediction for j and that DPT( J+) is the optimal cost of scheduling the predicted jobs (j. f.f.,P)) such that either the prediction for j was wrong or
never arrived. The prediction error n(J, JJ ) is then the maximum of these costs, normalized by the optimal cost OPT(J) of scheduling the predicted jobs. We assume that J * 0 to ensure that 7T[J, J) is well-defined. This prediction error is upper bounded by the prediction error I/w worod || considered in 77] for the problem with uniform deadlines, which we prove in Appendix F.T Here tre and pred are the true and predicted workload at each time step t, i.e., the sum of the processing times of the jobs that arrive at t.
For ease of notation, we allow the machine to split its processing power at every time step over multiple jobs. In practice, this is equivalent to partitioning time into arbitrarily small time periods and splitting each time period into smaller subperiods such that the machine is processing one job during each subperiod.

---

We note that in the above enror model, j.oob/ is in the set of correctly predicted jobs I+ only if all the parameters j have been predicted exactly correctly. To overcome this limitation, we introduce in Section a more general error model where some small deviations between the true and predicted parameters of a job j are allowed for the correctly predicted jobs J+. In Appendix F.1
we provide
further discussion of this prediction model in comparison with 7 4.
Performance metrics. The standard evaluation metrics for an online algorithm with predictions are its consistency, robustness, and competitive ratio as a function of the prediction error 23
22
The competitive ratio of an algorithm ALG as function of prediction error nj is c(1)
costaLa ALG is p-robust if for all 1j 2 c(n) S p (competitive ratio when max ((J.J))mm OPT(J)
the error arbitrarily large) and y-consistent if c{0) S f (competitive ratio when the prediction is
exactly correct). We say that the competitive ratio of ALG is smooth if it smoothly degrades from
to as the prediction error 17 grows.
3 The Algorithm
In this section, we develop a simple and general algorithmic framework for GESP and analyze the resulting consistency, robustness, and competitive ratio as a function of the prediction error. We first note that the algorithm with predictions from (7 for the problem with deadlines does not easily generalize to some of the other problems that we consider, including the flow time problem (see Appendix F.3 for additional discussion). A major difference is that our algorithm consists of two distinct phases.
Predictions cannot be completely trusted. We also note that first natural approach to assume that the predictions are exactly correct and aim for a 1-consistent algorithm. For the problem with deadlines, Bamas et al. 7 showed that there is no 1-consistent algorithm with bounded robustness. In Appendix A. we show that this approach would also fail for the flow time problem because the algorithm might start by processing jobs too fast and consume too much energy when trusting the predictions. More generally, in Appendix [A.2] we show that there is necessary trade-off between consistency and robustness for the flow time problem by proving that any 1 + X-consistent algorithm must be ((v1 + robuss.
3.1 Description of the algorithm
The algorithm, called TPE, takes as input an arbitrary quality of service cost function F, predictions J. a confidence level X E (0, 1] in the predictions, an offline algorithm OFFLINEALG for F. and an online algorithm ONLINEALG for F (without predictions). We denote by OFF(T) = the objective value achieved by OFFLINEALG over J.
Algorithm 1 Two-Phase Energy Efficient Scheduling (TPE)
Input: predicted and true sets of jobs I and J, quality of cost function F, offline and online algorithms (without predictions) OFFLINEAI.G and ONLINEALG for problem F, confidence level
A E (0, 1].
1: for t 2 do
2:
if (FF((TT))
> X (J) then
3: l 1
4: break
5:
(s,(t))jJeer + ONLINEALO((33)((
6: (8)(t))22needz)) + OFFLINEALG((
7: for 2 tx do
8: (s,(1) -ONIINEALGG(SS (Z2))()
9: (s,00)eee
(8,(()) -8)(0))))
10: return (s,(t)
5

---

The algorithm proceeds in two phases. In the first phase (Lines 1-5), TPE ignores the predictions and runs the auxiliary online algorithm ONLINEALG over the true jobs J=t that have been released by time L. More precisely, during the first phase of the algorithm, 8j (1) is the speed according to the online algorithm ONLINEALG for all jobs. The first phase ends at the time iy when the cost of the offline schedule computed by running OFFLINEALG on jobs Jgr reaches the threshold value A (F). As we will detail in the analysis section, this first phase guarantees a bounded robustness since we ensure that the offiin cost for the true jobs reaches some value before starting to trust the predictions (hence, TPE does not initially 'burn' too much energy compared to the optimal offline cost, unlike the example described in Appendix A.
In the second phase (Lines 6-9), TPE starts leveraging the predictions. More precisely, TPE needs to set the speeds for three different types of jobs: (1) the remaining jobs that were correctly predicted (i.e., J2tz n Fzh, (2) the remaining jobs that were not predicted (i.e., Jzt, \ I2i,) ) (3) the jobs that were not correctly scheduled in the first phase and still have work remaining at the switch point la (which are a subset of Jzt,). To schedule these jobs, TPE combines two different schedules. The first one is the offline schedule $ == OFFLINEALG((2nn
for the jobs P2r, that are predicted to arrive in the second phase. Each future job in the true set that was correctly predicted (i.e., j E TR.. n T2t on Line 9) will then be scheduled by following 5. The second schedule is an online schedule for the set of jobs J \ I2l, Jen UZ1 \ JZZAA which includes all jobs that have not been completed during the first phase (S ) and the incorrectly predicted jobs that are released during the second phase (Jts..) \ F2t2). This online schedule is constructed by running ONLINEALG on the set J Fztx (Line 8). Note that the total speed of the machine each time step is the sum of the speeds of these two online and offline schedules.
3.2 Analysis of the algorithm
We analyze the competitive ratio of TPE as a function of the prediction error 17, from which the consistency and robustness bounds follow. Missing proofs provided in Appendix B We separately bound the cost of the algorithm due jobs in Jets Jzea J2t, and Jzt, n I2ex- We do this by analyzing the costs of schedules S == ONLINEALG(J \ Fzu) and S == OFFLINEALG( (x2x) In the next lemma, we first analyze the cost of combining, i.e., summing, two arbitrary schedules.
Lemma 3.1. Let Jn be set of jobs and S₁ be feasible schedule for Jr, let T2 be set of jobs and S2 be a feasible schedule for Jz. Consider the schedule S == Si + for Ji U Jr which, at each time runs the machine at total speed s(t) s1(t) + s2(t) and processes each job j E In at speed (t) and each job j E T2 at speed 82,(t). Then, cost(S, Jn U F2) S (cost(S). + cost((2.. J2)
We next upper bound the cost of the schedule output by TPE as a function of the prediction error n, which we decompose into ?/1 (PT(5) and 1/2 (PT(F( The proof uses the previous lemma repeatedly, first to analyze the cost of the schedule S0n == ONLINEALG(J \ J2a, ) for the set of jobs I Iz (Ters) U (Jzza \ I2r,), then to analyze the cost of the final schedule, which combines 5 and $ = OFFLINEALG(
CPT(F)
OPT(
Lemma 3.2. Assume that OFFLINEALG is compccomeeeeivee and that ONLINEALG is "tm--compeiitiee Then, for all X E (0, 1], the schedule S output by TPE run with confidence parameter X satisfies (o < (PT()) (Tof + voil (one((ATio)) ((ATig)) 2/2 + kr))
Proof. We start by upper bounding cost(Son, J F2ez). First, by the algorithm, we have that OFF(Je()) S X (F) Since OFFLINEALG is compeoiett,,ive, we get
OPT(T2(,)) < OFF(Je.,) S X OFF(J) S Aroof OPT(5).
We also have that OPT( \ (22)) < OPT(T \ 3) S OPT( where the first inequality is since
Jze \ JZe, S J \ J and the second is by definition of m/ Recall that (*) denotes the optimal

---

offline schedule for the problem and consider the schedule S' = 5 + (I2u (T2un for
J I2h Jeta (Jza F2 We obtain that
OPT(J \ I2ra) S cost(S', . f2c))= _ { + ( )zzu)²)
(A (M:PT( OPT(O) (AAoOF)
mi
where the second inequality is by Lemma 3.1
Since we assumed that ONLINEALG is Yon Competttt,e,
cost(Sem .J (Zza) & Yon OPT(J (za) Yoa OPT(3) ((Aron)) + 1/7
1
We now bound the cost of schedule S. First, note that cost(S, (8, OFTLINEALG( 5 Toff OPT(Fzu) $ Yoft (PT( where the first inequality is since OFFLINEALG is Yofr competitiee and the last one since Jze J. Therefore, by applying again Lemma 3.1
we get:
cost(S, (cost(S..2za) cost(S ,J .J\JZ() 12()))
s (170m OPT( + (Ton OPT(F) (127or) a + 1/ )
= OPT( (1oi + 70n ((Aror)) + m7
We next state a simple corollary of Lemma 3.1
Corollary 3.3. OPT(J 9) 2 (1 11-18 7
OPT(F), and, assuming that OFFLINEALG is "Yoff"
competitive, we have: if (FF(TT S XOFF(JT, then mp2 2 (1 (AYog)
We are ready to state the main result of this section, which is our upper bound on the competitive ratio of TPE.
Theorem 3.4. For any X E (J, TPE with a "oo compeetitie algorithu ONLINEALG and compeetiie offline algorithm OFFLINEALG achieves a competitive ratio of
if OFF(TT S XOFF((
Yon
T0r to ((Ara))
(/)))))
otherwise.
max
The consistency and robustness immediately follow (for simplicity, we present the results in the case where OFFLINEALG is optimal). Additional discussion this competitive ratio is provided in Appendix 3.4
Corollary 3.5. For any À (0, 1). TPE with competttte algorithm ONLINEALG and an optimal offline algorithm OFFLINEALG is + 2 X² competitive if m = (consistency) and maxt7on. 22a -competitive for all 1), 122 (robustness). In particular, for any constant TPE e-consistent and ((1)-robust.
e 0, with
3.3 Results for well-studied GES problems
We apply the general framework detailed in Section 3 to derive smooth, consistent and robust algorithms for a few classically studied objective functions.
Energy plus flow time minimization. Recall that cs denote the completion time of job j. The quality cost function is defined as: F(S.J) = Ejer(cs ryy, with total objective cost(S, F(S,J) E(S). By direct application of Corollary 3.5 get that for all À (0, 1]. Algorithm ]
7

---

run with the 2-competitive online algorithm from consistent and 1+2.2 x rrobust.
3 and confidence parameter À is (1 - 2 )²)
Energy plus fractional weighted flow time minimization. In this setting, each job has a weight ey. The quality cost is J) = Σjer D/y Sizr, w/ (t)dt. We can use as ONLINEALG the 2-
competitive algorithm from [4]
Energy plus integral weighted flow time minimization. In this setting, each job has a weight v/- The quality cost function is defined as: F(S,J) = Ejer Vy(cg - rj))- We can use as ONLINEALG the O((a/ log a) ccompetitive algorithm from [12].
Energy minimization with deadlines. In this setting, there is also deadline d, for the completion of each job. By writing the quality cost as F(S.J) EEeJ 6 >. where 6 <g +oo if cg > dj and 0 otherwise, the total objective be written cost(S, J] E(S) + F(S, J). We can
as ONLINEALG the AVERAGE RATE heuristic (28) (which is 2d commoettiie for uniform deadlines
77.. In particular, for uniform deadlines, and for all é E (0, 1]. by setting ( obtain
consistency of (1 + c) for a robustness factor of O(4"² /ca=1)
3.4 Discussion on the competitive ratio
We assume in this section that OFFL.N is optimal. Note that for small 7/ and 7/2, the competitive
1+ (A +0²")
ratio is upper bounded as
which smoothly goes to + Yon x
(consistency
7/1 1-
case) when ?), 1/2 go to O. Moreover, our upper bound distinguishes the effect of two possible sources of errors the algorithm: (1) when removing jobs from the prediction (71 0 and 7/2 goes 1), the upper bound degrades monotonically to ( (2) when adding jobs to the prediction (72 = 0 and m goes to +oo). the upper bound first degrades, then improves again, with an optimal asymptotic rate of Ton- This is since our algorithm mostly follows the online algorithm when the cost of the additional jobs dominates.
4
The Extension to Small Deviations
Note that in the definition of the prediction error 77. a job j is considered to be correctly predicted only r, fU and p, pj. In this extension, consider that job is correctly predicted even its release time and processing time are shifted by a small amount. We also allow each job to have some weight fy > 0, that be shifted as well. Assuming additional smoothness condition on the quality cost function F(...), which is satisfied for the energy plus flow time minimization problem and its variants, we propose and analyze an algorithm that generalizes the algorithm from the previous section.
The algorithm, called TPE-S and formally described in Appendix takes the same input parameters as Algorithm TPE, with some additional shift tolerance parameter 1y hhit E: [0. 1) that is chosen by the algorithm designer. Two main ideas each job j (because the true processing time P, of job j could be shifted and be slightly larger than p3) and to introduce small delays for the job speeds (because the true release time rý of some jobs) could be shifted and be slightly later than fz). Details can be found in Appendix
artificially increase the predicted processing time P; of
Experiments
We empirically evaluate the performance of Algorithm TPE-S on both synthetic and real datasets. Specifically, we consider the energy plus flow time minimization problem where F(S,J) = Σjer Cj - Tý and consider unit-work jobs (i.e., Py for all j) and fix a = 3.
5.1 Experiment settings
Benchmarks. TPE-S Algorithm 2 with the default setting = 0.02, shift and a 0.4, where is a parameter that controls the level of prediction error, that call the error parameter.

---

Perlodic Prediction
Power Prediction
Messages- Prediction
Prediction error
Compestive (380
TIE compettivve
Compostt raRo
TiE-5
TrE-5 compeetivve
S retio
TRE-
2 Roomppttivee
2.0
Compentter
1.
Standard deviation
Standard deviation
Standard deviation
Standard deviation
Figure I: The competitive ratio achieved by our algorithm, TPE-S, and the benchmark algorithm, as function of the error parameter a (from left-most most to the second from the right), and the competitive ratio of TPE-S for larger range of function of a (right-most).
Periodic
Periodic Confidence parameter
ce ratle
TrBS
TPE 5
Compettwve
3.6
02 G4
Shift
Confidence parameter
Figure 2: The competitive ratio achieved by our algorithm, TPE-S, as a function of the shift tolerance parameter
chitt (Ieft) and as function the confidence parameter (right).
2-COMPETITIVE is the 2-competitive online algorithm from 3 that sets the speed at each time t to n(t)*, where n(t) is the number of jobs with r, S unfinished at time t, and uses the Shortest Remaining Processing Time rule.
Data sets. We consider two synthetic datasets and a real dataset. For the synthetic data, we first generate a predicted set of jobs J and we fix the value of the error parameter a > 0. To create the true set of jobs J, we generate, for each job j E J, some error err(i) sampled i.i.d. from ((0 o). The true set of jobs is then defined as I = { + err(j)) j J). which is the set of all predicted jobs, shifted according to {err(j))} Note that for all E J. E Johift only if
If ryl = |err(i) < B(J) 131 Hence, larger σ > 0 corresponds to a larger prediction error n78 For the first synthetic dataset, called the periodic dataset, the prediction is set of 300 jobs. with 1th job's arrival = i/a. For the second synthetic dataset, we generate the prediction by using a power-law distribution. More precisely, for each time E {1..... T), where we fix T 75, the number of jobs' arrivals at time is set to M(1 p(a)), where p(a) is sampled from power law distribution of parameter o, and M is some scaling parameter. all experiments, we use the values 100, M 500.
apain (PT())
We also evaluate the two algorithms the College Message dataset from the SNAP database 26). where the scheduler must process messages that arrive over days, each with between 300 and 500 messages. We first fix the error parameter a > then, for each day, we define the true set J as the arrivals for this day, and we create the predictions J by adding some error err(t) to the release time of each job i, where eir(i) is sampled i.i.d. from (0,
5.2 Experiment results
For each of the synthetic datasets, the competitive ratio achieved by the different algorithms is averaged over 10 instances generated i.i.d., and for the real dataset, it is averaged over the arrivals for each of the 9 days.
Experiment set 1. We first evaluate the performance of the algorithms as a function of the error parameter σ. In Figure T. we observe that TPE-S outperforms 2-COMPETITIVE when the error parameter small. In the right-most figure of Figure [ the competitive ratio of TPE-S plateaus when the value of a increases, which is consistent with our bounded robustness guarantee.
Experiment set 2. the second set of experiments, we study the impact of the parameters 1/ spshint and A of the algorithm for the periodic dataset (results for the other datasets can be found in Appendix E and fix a = 0.4. the left plot of Figure 2 we observe the importance of allowing some shift in the predictions the performance of our algorithms first rapidly improves as function of of shitt

---

and then slowly deteriorates. The rapid improvement is because an increasing number of jobs are treated by the algorithm as being correctly predicted when 17shin increases. Next, the right plot, we observe that the competitive ratio deteriorates as function of X, which implies that the algorithm can completely skip the first phase that ignores the predictions and run the second phase that combines the offline and online schedules when the prediction error is not too large. Note, however, that larger value leads to better competitive ratio when the predictions are incorrect. Hence, there general trade-off here.
6 Limitations
The results in Section 3 and Section require the quality cost function F to be monotone subadditive, which holds for the flow time problem and the problem with deadlines but might not hold for some other energy-efficient scheduling problems. The results in Section require an additional smoothness assumption on F. which holds for the flow time problem but not for the problem with deadlines. Finally, we have only tested our algorithm on the three datasets described in Section 5
Acknowledgements
Eric Balkanski was supported by NSF grants CCF-2210502 and IIS-2147361. Clifford Stein was supported in part by NSF grant CCF-221 8677 and ONR grant Chang Chair in Industrial Engineering and Operations Research.
and by the Wai T.
10

---

References
the [1] Susanne Albers. Energy-efficient algorithms. Communications the ACM, 53(5):66 86-9, 2010.
[2] Susanne Albers and Hiroshi Fujiwara. Fnergy-efffcient algorithms for flow time minimization.
ACM Transactions on Algorithms (TALG), 3(4))49-cs, 2007.
[3] Lachlan LH Andrew, Adam Wierman, and Ao Tang. Optimal speed scaling under arbitrary power functions. ACM SIGMETRICS Performance Evaluation Review, 37(2):39-41, 2009.
[4] Antonios Antoniadis, Peyman Jabbarzade Ganje, and Golnoosh Shahkarami. A novel prediction setup for online speed-scaling. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands, volume 227 of LIPIcs, pages 9:1 9:1-9:20, 2022. doi: 10.4230/LPPtssSWAAT.20
URL https: org 10. 1tt.1..//...II...... SWAT 2022.9
[5] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. arXiv preprint arXiv:2209.04058. 2022.
[6] Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions. arXiv preprint 2rXiv:2205.012477 2022.
[7] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL http:: af
neurips 16c0 Abstract. html
cc/ cc/paper/2en
[8] Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit (1 (1)=cmmetttitve algo- rithms. In Proceedings of the twentieth annual ACM-SIAM) symposium on Discrete algorithms, pages 1238-1244. SIAM, 2009.
[9] Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM J. Comput. 138))11684-1698, 2014. doi: 10. 137/130911317. URL btttpa://doi..o org/ 1137/130911317
[10] Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scaling to manage energy and temperature. Journal of the ACM (JACM), 54(1):1-39, 2007.
[11] Nikhil Bansal, Ho-Leung Chan, Tak-Wah Lam, and Lap-Kei Lee. Scheduling for speed bounded processors. In International Colloquium on Automata, Languages, and Programming, pages 409-420. Springer, 2008
[12] Nikhil Bansal, Kirk Pruhs, and Cliff Stein. Speed scaling for weighted flow time. SIAM Journal on Computing, 39(4):1294-1300) 2010.
[13] Nikhil Bansal, David P Bunde, Ho-Leung Chan, and Kirk Pruhs. Average rate speed scaling. Algorithmica, 6074))877-889, 201
[14] Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs. Speed scaling with an arbitrary power function. ACM Transactions on Algorithms (TALG), 9(2):1-14, 2013.
[15] David M Brooks, Pradip Bose, Stanley E Schuster, Hans Jacobson, Prabhakar N Kudva, Alper Buyuktosunoglu, John Wellman, Victor Zyuban, Manish Gupta, and Peter W Cook. Power- aware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6):26-44, 2000.
[16] Woo-Hyung Cho, Shane Henderson, and David Shmoys. Scheduling with predictions. arXiv preprint arXiv:2212210433, 2022.
[17] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 285-294, 2021.

---

[18] Tak-War Lam, Lap-Ket Kei Lee, Isaac KK To, and Prudence WH Wong. Speed scaling functions for flow time scheduling based on active job count. European Symposium on Algorithms, pages 647-659. Springer, 2008.
[19] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1859-1877, 2020.
[20] Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant schedul- ing. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 357-368, 2022.
[21] Alexander Lindermayr, Nicole Megow, and Martin Rapp. Speed-oblivious online scheduling: Knowing (precise) speeds is not necessary. arXiv preprint arXiv:2302.00998, 2023.
[22]
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
J. ACM, (::44:24:1 2021, doi: 10.1145/3447579. htttp::////// 1145/
3447579
[23] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Proceedings of the 8th ACM conference on Electronic commerce, pages 288-294, 2007.
[24] Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:18, 2020. ISBN 978-3-95977-134-4.
[25] Trevor Mudge. Power: A first-class architectural design constraint. Computer, 34(4):52-58. 2001.
[26] Pietro Panzarasa, Tore Opsahl, and Kathleen M Carley, Patterns and dynamics of users' behavior and interaction: Network analysis of an online community. Journal of the American Society for Information Science and Technology, (0(5):911-933) 2009.
[27] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2018.
[28] Frances Yao, Alan Demers, and Scott Shenker. A scheduling model for reduced cpu energy. In Proceedings of IEEE 36th annual foundations of computer science, pages 374-382 IEEE, 1995.
12


Reviews:
[{"review_id": "vKHMKt9dEM", "reviewer": "Reviewer_fguw", "summary": "This paper adds to the literature on energy efficient scheduling by defining an algorithm that extends the problems of \"energy minimization with deadlines\" and \"energy plus flow time minimization\" to the case where predictions about future jobs are available. The paper assumes an existing algorithm for online and offline energy efficient scheduling (wrt to a particular objective function) as well as an algorithm that makes predictions. In this case they give consistency - how far cost of the with-predictions variant deviates from the without-predictions variant - and robustness - how bad things can get when predictions are very wrong - bounds for their algorithm and compare them to existing results in the literature.\n\nThey explore several other properties of these algorithms and give an extension of the algorithm to small deviations - i.e. the case where predictions don't have to be exactly correct to be considered \"good\".\n\nExperiments are done on two synthetic and one real (SNAP College Message) dataset. \n", "questions": "I don't understand on line 162, prediction error is defined with an alpha-norm, but perhaps reading the relevant citation more carefully could help there.\n\nI'm wondering about the assumption that the speed of the machine is equal to the sum of the speeds of all jobs currently executing. Is overhead from context switching / cache misses negligible in real life, or is this just a simplification for theoretical analysis?\n\nHave the authors considered codifying their proofs in proof assistant software (e.g. Lean, Coq)?\n", "limitations": "The discussion is sufficient. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper tackles an important problem, where improved algorithms will have a positive environmental impact. \n\nThe paper contributes a new bound on a problem that hasn't been studied yet. It also adds insight into previously studied variants of the problem.\n\nRelevant claims seem to be justified with proofs - although I was unable to fully check everything, but what I did check was consistent.\n", "weaknesses": "This paper is abstract and jargon / notation heavy and will be difficult for someone without deep familiarity with the problem domain to read. On place that I had trouble were understanding how speed is assigned to a job.\n\nThe variable lambda is prominently used, but is not given an intuitive definition until line 195. I would like to see a definition of this \"confidence level\" variable nearby where the intuitive definition of alpha is given.\n\nAround line 196, I would like to see examples or citation of what some of these ONLINE and OFFLINE algorithms are, as well as an example of or reference to an algorithm for prediction.\n\nLine 29: Replacing: \"is equal to speed to some power\" with \"is equal to speed *raised* to some power\" would make this easier to understand. It does make sense as-is, but the added clarification would have helped me.\n\nLine 174: Using eta as a function and a numeric variable is confusing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and overall positive review. We hope the answers below address the reviewer’s concerns. Please let us know if this is not the case, we would be happy to also answer any follow-up questions.\n\n$\\bullet$ “One place that I had trouble were understanding how speed is assigned to a job.”\\\nThe assignment of speed $s_j(t)$ to a job $j$ at time $t$ is the main technical part of our algorithm and it is indeed subtle as it depends on both $j$ and $t$. More precisely, if time t is during the first phase of the algorithm, then $s_j(t)$ is the speed according to the online algorithm OnlineAlg for all jobs $j$. If $t$ is during the second phase of the algorithm, then $s_j(t)$ is assigned according to the offline algorithm OfflineAlg for the correctly predicted jobs $j$ and it is assigned according to OnlineAlg for the incorrectly predicted jobs $j$. We will add some discussion in the description of the algorithm to clarify this.\n\n$\\bullet$ “The variable lambda is prominently used, but is not given an intuitive definition until line 195.”\\\nlambda is the parameter that controls the tradeoff between consistency and robustness in our results.  Intuitively, the more we trust the predictions, the smaller lambda should be chosen. On page 2, we define lambda as being a parameter such that our results hold “for any lambda in (0, 1]” (see caption of Table 1). We will clarify this in the next version of the paper.\n\n$\\bullet$ “Around line 196, I would like to see examples or citation of what some of these ONLINE and OFFLINE algorithms are, as well as an example of or reference to an algorithm for prediction.”\\\nIn Section 3.3, we provide a discussion of such algorithms, as well as many references.  We would be happy to move some of that discussion to earlier in the paper. Regarding a “reference to an algorithm for prediction”, we provide several references in the introduction for relevant algorithms with predictions.\n\n$\\bullet$ “I don't understand on line 162, prediction error is defined with an alpha-norm, but perhaps reading the relevant citation more carefully could help there.”\\\nWe emphasize that this prediction error on line 162 is not the prediction error we use in this paper but the one considered in [7], so we do not provide a detailed discussion of it. This other definition follows from the impossibility result shown in [7] (Appendix C).\n\n$\\bullet$ “Is overhead from context switching / cache misses negligible in real life, or is this just a simplification for theoretical analysis?”\\\nIt is common in the scheduling literature (with or without predictions) to assume that context switching has a negligible cost and to ignore it. This assumption is justified in many, but not all computing environments. However, there are some environments that have a high cost for preemption (such as those that involve a physical process or those that depend upon a massive amount of data), and typically this is handled by not allowing any preemptions.  There have been some works that assign a cost to preemption and/or limit the number of preemptions. Our work does not handle these cases, but it is a good future research direction.\n\n$\\bullet$ “Have the authors considered codifying their proofs in proof assistant software (e.g. Lean, Coq)?”\\\nNo, we have not. We strongly believe that using such software is not standard for papers in this area at NeurIPS."}, {"review_id": "u7WrKmaqW3", "reviewer": "Reviewer_BEvj", "summary": "The paper considers speed scaling scheduling with learning augmented predictions. In contrast to previous works that considered the deadline-based version of the problem, the current paper studies a more general model that allows for different quality of service objectives to be optimised alongside the energy consumption of the schedule. These include for example the well studied total flow time objective. \n\nSimilarly to other results in the learning augmented algorithms literature, the employed approach is that of combining at runtime an offline and an online algorithm for the problem.\n\nFinally, experimental results over real and sytnthetic datasets are provided.\n\n", "questions": "I am wondering if there is a way to simplify the competitive ratio formula in Theorem 3.4 -- even perhaps at a slight loss of the proven guarantee? I did check the discussion in the appendix which is helpful but still does not give a very clear picture of the obtained result.", "limitations": "No conceivable limitations or potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The biggest strength of the paper is the generality of the considered model and how it implies algorithms with predictions for a number of different speed-scaling settings.\n\nOther strengths include that the paper is well written, and obtains a clean and general framework.", "weaknesses": "The prediction error is quite unnatural in my personal opinion. But going for it is that it generalizes the prediction error considered in [7].\n\nThe major weakness is that jobs are considered to be predicted correctly if the prediction for the job is 100% accurate. This is a bit unnatural and it could be argued that if the predicted parameters of every job are very close to the real ones then the predictions are adequate and should be useful. This is tackled in Section 4 (and mainly Appendix C) but to my understanding it only allows for small errors per job -- which is a weakness compared to other papers in the area in general and specifically previous papers on speed scaling with predictions.\n\nThe technique employed in the paper is quite standard and I couldn't identify any really new idea. Nevertheless the results are not obvious and had to be worked out.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review. We believe there is a misunderstanding regarding the major weakness raised by the reviewer, which we address first below. Please let us know if this is not the case, we would be happy to also answer any follow-up questions.\n\n$\\bullet$ “This is tackled in Section 4 (and mainly Appendix C) but to my understanding it only allows for small errors per job -- which is a weakness compared to other papers in the area in general and specifically previous papers on speed scaling with predictions.” \\\nThe competitive ratio we achieve gracefully degrades as a function of the (per job) shift tolerance parameter $\\eta^{shift}$, which is chosen by the algorithm designer depending on the instance. In particular, $\\eta^{shift}$ can be set to be large to allow for large errors per job (at the cost of a worse competitive ratio). Thus, we disagree with the claim that our algorithm only allows for small errors per job.\n\n$\\bullet$ “The technique employed in the paper is quite standard and I couldn't identify any really new idea. Nevertheless the results are not obvious and had to be worked out.”\\\nWe respectfully disagree with the claim that our techniques are standard. In particular, many algorithms with predictions first trust the predictions and then, if the cost becomes too large, switch to an online algorithm that ignores the predictions. Our approach is to instead first run an online algorithm that ignores the predictions and then switch to trusting the predictions. We are not aware of previous work that has used this approach. If the reviewer has a reference to a paper that uses such an approach, we would be grateful if they shared it.\n\n$\\bullet$ “I am wondering if there is a way to simplify the competitive ratio formula in Theorem 3.4 -- even perhaps at a slight loss of the proven guarantee? I did check the discussion in the appendix which is helpful but still does not give a very clear picture of the obtained result.”\\\nWe attempted to further simplify the formula but, unfortunately, weren’t able to do so. We agree with the reviewer that the formula is complicated. We are happy to move some of the discussion about this formula from the appendix to the main body of the paper.\n\n"}, {"review_id": "RA50lsezrK", "reviewer": "Reviewer_RAEY", "summary": "The authors study energy-efficient scheduling with predictions. There\nare already previous works on minimizing energy consumption in a setting\nwith deadlines. The authors provide a unified way to address both\nthe scheduling with deadlines as well as (weighted) flow time plus energy cost.\nIt was already known that no algorithm can be both 1-consistent and robust\nand therefore one has to aim for a trade-off between consistency and robustness.\nThey provide consistency and robustness trade-offs which scale roughly with\n(1/lambda), where lambda is the trade-off parameter. They also show a lower\nbound on robustness scaling with sqrt(1+1/lambda), i.e., there is still a\nspace for improvement.\nThey also discuss deterioration of their bounds between consistency and\nrobustness as a function of a prediction error defined in a natural way,\nespecially with their extension to approximately correct predictions.\nI did not notice any lower bounds on the dependence on prediction error,\nalso the formula stating the dependence is not easy to understand (maybe a plot\nwould help?). But overall, I find the contribution of this paper solid and\nI will be happy to see it accepted.\n", "questions": "* you could elaborate a bit on how does your competitive ratio behave as a dependency on prediction error, if possible to give a clean answer.", "limitations": "* Authors stated their theoretical results formally, including all assumptions made", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "they provide an unified framework for a broad range of problems in energy efficient scheduling", "weaknesses": "* resulting bounds for the Deadline setting are weaker than in previous works\n* results not tight yet", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and positive review. \n\n$\\bullet$ “elaborate a bit on how does your competitive ratio behave as a dependency on prediction error”\\\nSuch a discussion is provided in Appendix G.1. We would be happy to move that discussion to the main body of the paper. A slightly edited version of this discussion is given below for convenience.\nThe competitive ratio smoothly approaches the consistency bound as the prediction error tends to 0. In addition, it distinguishes the effect of two possible sources of errors: \n\n(1) when there is a growing number of predicted jobs that do not arrive ($\\eta_1 = 0$ and $\\eta_2$ goes to 1), the upper bound degrades monotonically to $O(1/\\lambda)$. \n\n(2) when there is a growing number of unpredicted jobs that arrive online ($\\eta_1$ goes to infinity and $\\eta_2 = 0$), the competitive ratio first deteriorates and then improves, with an asymptotic rate equal to the competitive ratio $\\gamma_{on}$ achieved by the online algorithm OnlineAlg. This behavior is because our algorithm mostly follows the online algorithm when the cost of the additional jobs dominates.\n"}, {"review_id": "bETMlCatPj", "reviewer": "Reviewer_HbG7", "summary": "This paper studies an energy-efficient scheduling problem under the setting of prediction. In this problem, each job has a release time and processing time. The job arrives online and the algorithm can determine the speed of the machine. The higher speed means a higher energy cost. The total energy cost integrates the speed cost over all time points. Besides the energy cost, the objective contains a job cost function that relies on the schedule. In this paper, the authors assume this cost function is subadditive to capture more applications.\nThe schedule is defined as the speed of the machine each time. The goal is to find a feasible schedule with the minimum total cost.\n\nThis paper considers the above problem under the setting of prediction, where their prediction is the release time and processing time of each job. The main contribution of this work is a learning-augmented algorithm that achieves (1+\\epsilon) consistency and bounded robustness. The authors also give the ratio function depending on the prediction error. Finally, the authors verify the performance of the proposed algorithm in some real datasets.\n", "questions": "I would appreciate it if the authors add a discussion about how to compute the error function given two instances.", "limitations": "This is a theoretical paper, there is no potential negative societal impact.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The submission is carefully written and structured, so reads well given the technicality of the material. Especially, the authors provide sufficient intuitions to help understand the algorithm.\nThe proposed learning-augmented algorithm can be applied to several problems. Although one still needs to utilize the classical online and offline algorithms for each specific problem, the proposed framework provides some intuitions to show how to combine these two algorithms.\n", "weaknesses": "I am one of the reviewers of the previous version of this paper. My previous major concerns are: (1) the authors didn’t provide a comparison of the proposed framework and the existing works, thus it is unclear how good this framework is if we apply it to some specific problem; (2) the considered problem is too general and may not admit a polynomial time algorithm.\n\nIn this version, the author addresses these two points appropriately. For the first point, the authors added Table 1 to discuss four related special cases. For the second point, the authors considered the approximation ratio in the proof of Theorem 3.4.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and positive review. \n\n$\\bullet$ “I am one of the reviewers of the previous version of this paper. My previous major concerns are […] In this version, the author addresses these two points appropriately.”\\\nWe are happy to hear that the previous weaknesses were addressed appropriately.\n\n$\\bullet$ “I would appreciate it if the authors add a discussion about how to compute the error function given two instances.”\\\nFirst, we would like to emphasize that our algorithm does not require knowledge of the prediction error $\\eta$. Nevertheless, if one wanted to compute this prediction error, they would have to compute the optimal offline cost OPT of three different instances. There are previous works that have studied the offline version of energy-efficient scheduling. In particular, [28] gives an optimal offline algorithm for the energy minimization with deadlines problem and [2] gives an optimal offline algorithm for the energy plus flow time problem in the case of unweighted unit-size jobs.\n\n"}]

Author rebuttal:

Meta-review: The paper considers an important scheduling problem. The reviewers generally appreciated the technical results and the problem. The main critique is that the error model used could be considered unnatural. Still, the results are likely tobe of interest to the community.
Decision: Accept (poster)