Minimalistic Predictions for Online Class Constraint Scheduling
Authors: Dorian Guyot
Alexandra Anna Lassota
Venue: ICLR 2025 Poster (2025)
Keywords: Scheduling
Class Constraints
Predictions
Online Algorithms
Primary area: optimization
TL;DR: We use minimal predictions to solve class constrained scheduling and improve bounds on the competitive ratio.

Abstract: We consider online scheduling with class constraints. That is, we are given $m$ machines, each with $k$ class slots. Upon receiving a job $j$ with class $c_j$, an algorithm needs to allocate $j$ on some machine $i$. The goal is to minimize the makespan while not assigning more than $k$ different classes onto each machine.
While the offline case is well understood and even (E)PTAS results are known [Jansen, Lassota, Maack SPAA'20, Chen Jansen Luo Zhang COCOA'16], the online case admits strong impossibility results in classical competitive analysis [Epstein, Lassota, Levin, Maack, Rohwedder STACS'22].

We overcome these daunting results by investigating the problem in a learning-augmented setting where an algorithm can access possibly erroneous predictions. We present new algorithms with competitive ratios independent of $m$ and tight lower bounds for several classical and problem-specific prediction models. We thereby give a structured overview of what additional information helps in the design of better scheduling algorithms.

Published as a conference paper at ICLR 2025
MINIMALISTIC PREDICTIONS FOR ONLINE CLASS CONSTRAINT SCHEDULING
Dorian Guyot University of Fribourg Fribourg, Switzerland dorian, dorian.guyot@umm gut.ggguottuui......om
Alexandra Lassota
Eindhoven University of Technology Eindhoven, The Netherlands a a assotaatuee .ne.
ABSTRACT
We consider online scheduling with class constraints. That is, we are given m ma- chines, each with class slots. Upon receiving a job j with processing time P, and class Cj, an algorithm needs to allocate j on some machine i. The goal is to min- imize the makespan while not assigning more than different classes onto each machine. While the offline case is well understood and even (E)PTAS results are known [Chen Jansen Luo Zhang COCOA' 16; Jansen, Lassota, Maack SPAA'20), the online case admits strong impossibility results in classical competitive analysis [Epstein, Lassota, Levin, Maack, Rohwedder STACS' 22].
We overcome these daunting results by investigating the problem in a learning- augmented setting where algorithm can access possibly erroneous predictions. We present new algorithms with competitive ratios independent of m and tight lower bounds for several classical and mooblem-specifne prediction models. We thereby give structured overview of what additional information helps in the design better scheduling algorithms.
INTRODUCTION
Makespan minimization on parallel identical machines is fundamental and intensively stud- ied problem and a classical example for online algorithm analysis through Graham's 's famous list scheduling algorithm Graaaam (1966). In this problem, jobs arrive online and upon arrival of job j. an algorithm needs to assign j to a machine. Note that there exist two main ways for the jobs to be made available to the algorithm: one by
over time. We consider the former.
Motivated by its various applications in product planning, data placement, and load balancing, we consider a variant with class constraints Jansen et al. (2020). That is, we given machines and n jobs with job j having processing time pj and class cj. Each machine can schedule jobs from at most k different classes. We say that machine has k class slots. A class slot on machine i is occupied by a class e if at least one job of class e is scheduled on i. We consider classical makespan minimization, that is, minimizing the maximum load any machine:
minimize
max (m(m)
Σ
S.t.
He | scheduled on m²) < k Vi E [m]]
scheduled on
A famous special case of this problem is cardinality constrained scheduling, where each class only contains single job. Thus, the class restriction is equivalent to limiting the number of jobs on a ma- chine. Cardinality constraints naturally appear in variety of applications, ranging from distributing students in universities to assembly line optimizations or circuit board design Zhang et al. (2009).
The offline cases [ et al. (2016). This motivated an extensive study of approximation algorithms. Among the latest findings, there PTAS results known for the class constraint scheduling variant relying on modeling the problem as well-structured integer programs, and even an EPTAS for the cardinality constraint special case Jansen al.] (2020); Chen al. (2016).
-oll-understood. Both problems are known to be NP-hard Shachnai & Tamir
For the online setting, no competitive ratio better than the trivial bound of m can be achieved for class constraint scheduling. For cardinality constraint scheduling, constant lower bound of 2 is known

---

Published as a conference paper at ICLR 2025
Epstein et al. (2022). The competitive ratio maXjer / /m/////mmmspppPPT is a widely used measurement for the performance of an online algorithm. It measures the maximum ratio over the set of all instances I between the online algorithm's 's (I) and an offline optimal solution's (OPT) objective value. Here, OPT is the best schedule that can be computed with complete information and unbounded running time.
Although the lower bounds seem unreachable, the setting does not reflect the power of most real- world applications, where certain aspects of the input can be learned using historical data with application-sensitive modeling. We use this approach to investigate the problem in a learning- augmented setting where an algorithm can access such predictions (see, e.g., Mitzenmachhr & Vassilvitskii (2022)). However, these predictions might not perfectly reflect the current instance. Measuring this error allows parameterized performance guarantees most prominent among those are consistency and robustness of algorithms w.r.t. the prediction model. Consistency is the com- petitive ratio for perfect predictions. Robustness is an upper bound on the competitive ratio for any prediction w.r.t. the error of this prediction.
The above definitions are generally applicable to all prediction models. Thus, another main ingre- dient is to select a reasonable and well-performing prediction model for the given problem. In this work, we study the two most prominent prediction models: full input predictions (see, c.g.. Purohit
et al. 2018); Azar et al. 2021); Im al. (202I) and the references in the papers) and action predic- tions (see, e.g.. Antoniadis et al. (2023): Bamas et al. (2020)] Lindermayr & Megow (022)) Anand al.] (2022) and the references in the papers). Although we show that these measures perform fairly well, a huge drawback is the learnability and encoding length of information of these predic- tions. Thus, we also present an application-sensttii prediction model, which for most real-world instances is significantly smaller and easier to learn, yet still allows great consistency and robustness guarantees.
PREDICTION MODELS
The two arguably most prominent prediction models in the literature are full inpur prediction and action prediction. In the former model, as the name states, the whole instance is predicted. This means that we are given the set of jobs along with their processing times and respective classes. In the latter, all actions are given, that is, list of length n with values between to m are given where the Æth entry states on which machine to put job jt- Predictions are either static, that is, we are given a list of n machines and assign job to the jth machine in the list, or adaptive, meaning that upon each arrival of new job j. we get the machine predicted on which j should be placed on.
Both prediction models need to predict significant amount of information because the encoding length of the information dependent on the number of jobs n, and are hard learn as they are sensitive to small changes in the instance. Thus, aiming for minimalistic predictions, we introduce a third prediction model specifically designed for this application named class size prediction. predicts the total processing time of each class, but gives no information the number of jobs nor specific processing times.
OUR CONTRIBUTION
We overcome the daunting lower bounds for online class constraint scheduling by investigating the problem in a tions. We study three different prediction models: full input predictions, action predictions, and we introduce a new applicition-specffic prediction model called class size prediction. For each of the prediction models, we design algorithms that beat the known lower bound of m for online class constraint scheduling.
setting where an algorithm can access possibly erroneous predic-
All prediction models lead to algorithms with different approximation guarantees and running times. As each of them can perform best for certain instances, and due to different eligibility of implement- ing such predictions, we believe that each of them is of independent interest. After presenting all results, we have more in-depth evaluation of the different models.
Note that there is no purely online algorithm without access to predictions on the cardinality con- straint scheduling which performs better than m (see Theorem
2

---

Published as a conference paper at ICLR 2025
In this paper, show the following algorithms, where l is the error of the respective prediction: For minimizing the makespan for online class constraint scheduling on m identical machines, there is
algorithm with predicted input with competitive ratio at most (4/OPT + a) where OPT is an offline optimal solution and a is the competitive ratio of an offline approxima- tion algorithm (see Theorem B)
algorithm with static predicted actions with a competitive ratio most (E + 1) (see Theorem 6
an algorithm running with class size predictions with a competitive ratio at most E/OPT 2 + c where c an accuracy parameter (see Theorem
Input and action predictions, after carefully defining the model and error, yield, rather straightfor- wardly, algorithms with good consistency and robustness guarantees. However, the simplicity comes the cost of large and difficult-to-achiee the prediction, we thus consider the class size prediction model. Here, the information load is only dependent on the number of classes and not on the number of jobs.
predictions. To minimize the information provided by
For perfect class size predictions, we manage to improve the competitive ratio of online class con- straint scheduling significantly from m to a 2- c. To do so, we proceed in two steps: (i) we solve the predicted instance by treating each class as one splittable job and solve this problem using known results obtaining a schedule plan; (ii) then we post-process the schedule plan to obtain some ex- ploitable structural properties. In particular, we define structure that guarantees that actual job sizes do not match the way we split the jobs in (i), we only get a bounded amount of extra processing time each machine. This is achieved by defining graph for the schedule plan, rep- resenting possible ways to move computation time from one machine to another without changing the classes present on each one. cycle removal procedure is then applied this graph sim- plify it and introduce a hierarchy between the machines without changing the machines' individual makespans. This hierarchy is then used starting point to define how place the incoming jobs and the unexpected loads that come with them.
if the
In all prediction models, we assume that the number of classes known to the algorithm. In fact, we prove that this is essential: if the number of classes is either not given or predicted possibly erro- neously, then there exists no algorithm, regardless of which further (possibly erroneous) predictions are given that can beat a competitive ratio of m (Theorem [ and Corollary 2
Finally, we prove all of our competitive algorithms to be (nearly) tight, i.e., no algorithm with access to the same predictions can yield a (significantly) better competitive ratio (see Theorems and
12
FURTHER RELATED WORK
Packing and scheduling problems are widely studied, and empowering them with additional in- formation has already been intensively studied. We recommend Chen & Pouts (1998); (Strusevich | Christensen et al.] (2016) for survey on scheduling and packing algorithms and Dwibeed & Mohanty (2022) for survey on semi-online scheduling. The task of minimizing the makespan on parallel identical machines is probably the most studied objective for scheduling since the six- ties, and considerable body of literature exists. It is well known be NP-hard and admits PTAS. Graham Graham (1966) is famous for his List scheduling algorithm for which he showed its (2 1/m) 11m1)mmmmmppppp competitivennes. It has been proven to be optimal for m E {3, 43 Faigle al. (1989) and the competitive ratio has been successively lowered for higher number of machines to 1.923 Galambos & Woeginger (1993); [Bartal et al. (1995): Karger et al. (1996); Albers (1999). The cor- responding lower bound also improved over the years to 1.85358 for m 80 Gormley et al. (2000).
The more recent line of research learning-augmentinn algorithms offers novel approach that in- tegrates additional (and possibly erroneous) predictions to the input to achieve better performances, if they accurate, while maintaining good performance when they are not. These predictions are commonly divided into two categories: predicting a part of the online input (input prediction) Azar et al. (2022a b): Bamas et al. (2020): Lykouris & Vassilvitskii (2018): Purohit al. (2018), or pre-
3

---

Published as a conference paper at ICLR 2025
dicting actions of the algorithm (action prediction) Antoniadis al. (2020): Bamas al. 2020 Lattanzi et al. 2020). The recent paper Lindermayr & Megow (2022) also proposes a more exotic type of prediction for non-clairvoyant scheduling (when the processing time of job is not known until it is placed on a machine): permutation prediction, which can be seen as sort of action pre- diction. In this input model, a permutation of jobs is predicted that hints at priority order. This builds on previous results that show that knowing the Weighted Shortest Remaining Processing Time order of jobs enough find an optimal schedule |Smihh (1956). Very recently, non-clairvoyant scheduling with precedence constraints (information about a job is revealed only when all of its pre- decessors have been completed) was also studied in the 2023). To the best of our knowledge, none of these algorithms or ideas have been extended to work for the class constraint scheduling problem, so we this gap in this paper.
paradigm Lassota al.)
STRUCTURE OF THIS DOCUMENT
We start by demonstrating that each individual prediction is incapable of surpassing the pessimistic bound of m if the number of classes is not known beforehand or is subject to potentially erroneous predictions.
Following our goal to find minimalistic predictions for online class constraint scheduling, we inves- tigate the prediction models by the amount of information they generate. That is, we first analyse full input predictions, then turn attention to action predictions, and eventually arrive at the most involved and problem specific one: class size predictions. We conclude the paper with discussion on the results and the relation between the prediction models.
KNOWING THE NUMBER OF CLASSES IS ESSENTIAL
In the following sections, we assume that the number of classes is always given and that this in- formation is correct. We argue that these preconditions are necessary (but not sufficient) to design any algorithm that beats the trivial worst-case competitive ratio of m. This section dedicated to proving this statement.
Theorem 1. There exists no algorithm with a competitive ratio better than m if the number of classes in the instance is not given (nor can be computed correctly from the given predictions).
Proof. Let m 2 2. Consider some machine i that has a job of class e assigned to No algorithm can decide to put any other job of class on any other machine than as the algorithm needs to guarantee the feasibility of any instance. Thus, cannot choose to occupy extra class slots in case the instance has mk many different classes.
Now assume an instance with m equally sized jobs of the same class. Any algorithm has to stack these jobs on the same machine, where the optimal solution would have been to spread the m jobs on the m machines, yielding a competitive ratio of m.
The same argument holds if the number of classes is predicted, but might be erroncous as an algo- rithm needs guarantee fcasibility. Thus, derive the following corollary.
Corollary 2. There exists algorithm with a competitive ratio better than m if the number of classes in the input is (possibly erroneously) predicted.
Note that this precondition is not enough on its own and does not prevent the lower bound from Epstein et al. 2022)
3 FULL INPUT PREDICTION
In this commonly assumed prediction setting, the whole input is predicted. That is, we get predicted all jobs along with their processing times, classes, and identifier to be able to map them to the actual arriving jobs. Processing times and classes be predicted wrongly, but assume the identifier to be correct and that each predicted class is among the set of actual classes in the instance, which natural restriction commonly cases designed work for specific set of classes.
4

---

Published as a conference paper at ICLR 2025
As proved in Section 2 knowing the correct number of classes present is necessary to overcome competitive ratio m.
Full Input Prediction Algorithm The algorithm first computes a solution to the predicted in- stance. As the offline problem is already NP-hard, it either spend exponential time compute an optimal solution, or compute near-oppiie -otimmal solution in polynomial time, e.g., using the PTAS by Jansen, Lassota, and Maack Janssnn et al. (2020). We call this schedule S. Upon receiving job j. the class was predicted correctly, the algorithm places the job as in S. Otherwise, job is placed on the machine with the least load in S that has its class.
The prediction error E is the sum of differences between the predicted processing time and actual processing time of job j. Note that if the class was predicted wrongly, it can be interpreted as having non-existent job predicted, thus its whole processing time is added to the error.
For minimizing the makespan for online class constraini scheduling machines, there is an algorithu running in time ((nnk)+T with predicted input with a competitive ratio at most (e/OPT a) where T is the time needed compute the offline solution S and is the competitive ratio of an algorithm A computing the offline solution S.
Theorem 3.
identical
Proof. If all predictions are correct, the Full Input Prediction Algorithm places each job as in the offline solution, yielding its competitive ratio a. If a job is predicted correctly, but the class was predicted correctly, it only adds its eπrоr to the makespan. Otherwise, its whole processing time might be added, which is captured by the error. Hence, the additive increase on the fullest machine is at most L.
Computing S takes time T per definition. Finding the corresponding job in S for the incoming job takes time (n)) as it might need to be compared to all jobs. If the class was predicted incorrectly, the lowest loaded eligible machine needs to be found in time O(m)). This leads an overall running time of (nnnk) + T.
Theorem 4. For minimizing the makespan for online class constraint scheduling identical machines, no algorithm with static full input predictions can achieve a competitive ratio smaller than + e/OPT)
In our proofs, make use of an adversary that can manipulate the stream of jobs to incur the worst performance of the algorithm being studied. We consider the strongest form of adversary, namely an adaptive adversary that can react the algorithm's 's decisions while is running, as illustrated in the following proof:
Proof. Choose k, O, 2 2 arbitrarily. Predict mk jobs with processing time and distinct classes. Any algorithm has to place jobs on each machine. This clearly an optimal solution. The adversary now decides that all processing times of classes placed machine 1 have in fact been predicted incorrectly. In particular, all & classes on machine 1 get an additional job of t/k, yielding an increased makespan and an error of l.
Theorem and Theorem 4 together yield: Corollary 5. The Full Imput Prediction Algorithm is tight w.r. the competitive ratio.
4 ACTION PREDICTION
In this variation, the actions (i.e. on which machine to place a job) are predicted. The error measure the number of wrong predictions As no information is available on the upcoming jobs, the best strategy is to follow the predictions. In detail, we define the following algorithm.
Action Prediction Algorithm Upon receiving job and predicted machine P,. place j P, possible (i.e. if there are still free class slots). Otherwise, put on one the eligible machines with the lowest load.
5

---

Published as a conference paper at ICLR 2025
For minimizing the makespan for online class constraint scheduling identical machines, there is an algorithm running in time ((mnk) with static or dynamic predicted actions with competitive ratio at most (1+
Theorem 6.
Proof. If all predictions are correct, the Action Prediction algorithm obviously yields an optimal schedule.
When placing job on machine such that the machine gets load bigger than OPT then there might be two reasons: either the current prediction is wrong or there are no other possibilities, due previous wrong prediction.
If the current prediction is wrong, the additional error could reach the size of the largest job Pmax- We have Pmax v OPT. the prediction could not be followed because that machine's class slots are already used, then there were previous wrong predictions that took this job's ss class slot. In the worst case, a previous error could result in moving the entire processing time scheduled on the original machine in the optimal schedule on top of another machine. Since OPT is the maximum load on any machine in an optimal schedule, at most that much processing time can moved to the current machine by such previous error.
Thus, each error can only cause an increase of the makespan of at most OPT. Hence, & errors can increase the makespan by most c OPT.
Regarding running time, each step costs time at most ((mk) to find and verify an eligible machine place a job. In total, this yields running time of (mmnk).
Li
Note that l can get large as n, however, the maximal error is bounded by m OPT by placing all jobs into the same machine.
Theorem 7. For minimizing the makespan for online class constraint scheduling on m identical machines, no algorithm with static or dynamic predicted actions can achieve competitive ratio smaller than é for E S m 1.
Proof. Let k: = 2 and 2 2 be chosen arbitrarily. The instance contains + classes.
The adversary first produces stream of jobs of size and class We predict machine i for the ith job. This stream of jobs stops either when each machine gets exactly one job (following the prediction) or if two jobs get placed on the same machine.
In the first case, jobs have been produced. The adversary then produces large jobs of size N >> and class 2. These jobs need to stacked onto a single machine for the instance to stay feasible. The adversary then concludes with - 1 jobs of size 1 and of classes 3, 4, .... + 1, which fill the remaining class slots. An optimal schedule would have placed the m jobs of the first stream evenly machines. Thus, we had errors in the prediction. N is large enough for the makespan to basically be & N instead of OPT N and we get a competitive ratio of
l machines
that the l large jobs can be spread among the remaining &
In the second case, we have stacked two jobs of size 1 on top of each other. The adversary then produces m jobs of small size and classes 3, ... m + 1. An optimal solution would have spread the first m jobs and placed the small jobs on top. There was no prediction error, and the makespan 2 OPT.
This shows that regardless of which decision we take, an algorithm cannot achieve competitive ratio better than
Theorem and Theorem 7 together yield:
Corollary 8. The Action Prediction Algorithm tight with respect to the competitive ratio.
5 CLASS SIZE PREDICTION
Next, we turn our attention to the application-sensitie prediction model: class size predictions. Here, instead of predicting the whole input, only the accumulated processing time of each class is

---

Published as a conference paper at ICLR 2025
predicted. As before, the number of classes is assumed to be known. Intuitively, error should capture the distance between the predicted classes and the actual ones. Indeed. we use this natural interpretation by using -type error measure: the absolute difference between the actual size of each class and its predicted size.
Class Size Predictions Algorithm
The algorithm proceeds in three steps:
1. Use an algorithm to solve the class/cardinality constraint scheduling problem on the pre- dicted input (interpreting each class to be splittable job) to obtain schedule plan S.
2. Postprocess S such that no two machines have the same subsets of classes for subsets larger than obtaining the schedule S'. Define hierarchy H the machines based on S', which will be specified below.
3. Upon arrival of a job j of class c, assign to a machine using the order defined by H, where machine can be used until it has no available processing time for class according to 5"
Roughly speaking, the algorithm follows planned schedule to assign the arriving jobs. The main work lies generating a planned schedule with the structural property that no two machines share the same subset of classes (for subsets larger than 1). Only then do consistency and robustness guarantees hold. Note that, in contrast to full input predictions, we do not need to predict any job identifier. Further, we like to mention that can any algorithm solve the class/cardinality constraint scheduling problem on the predicted input (interpreting each class to be one splittable job) obtain a schedule plan S. Splittable means that job does have be put on machine as a whole, but instead, can be split arbitrarily into small pieces.
First step We solve the class/cardinality constraint scheduling problem on the predicted input to obtain a preliminary schedule plan S. Note that we interpret every class to only contain one job, and that this job can be split arbitrarily.
Let be the competitive ratio of the chosen algorithm A, and T its running time. The best algorithm (running polynomial time with respect to n) regarding the competitive ratio is an EPTAS provided by Chen et al. (2016). Of course, one could spend an exponential amount of time to compute an optimal solution, i.e., a ==
Second step Let S be the schedule plan obtained in the first step. W.L.ogg, assume that each class occupies a consecutive slot on a machine, otherwise the schedule can be rearranged without changing the makespan guarantee.
Let G = (V, E) be a graph derived from as follows:
generate two vertices (ar(ie) ,32 (iii))))) for each class e present each machine i in S. We call the vertices (3.e) input vertices, and x/ (i.e) outpul vertices, respectively,
introduce an edge from each z(((e) to each x2 (i,e) where c + c', i.c., an edge from each input vertex on machine to each output vertex of another class on the same machine i. We call these edges conversion edges, and
insert edge from each (1.c) to each xf{ (6'ee) where i * f', i.c. edge from each output vertex to each input vertex of the same class on a different machine. We call these edges transfer edges.
We call this graph the conversion and transfer (CT) graph of S. See Figure for an example.
We now aim to alter S to satisfy our desired structural property. To do so, we introduce the following procedure which runs as long as there is cycle C' in the CT-graph G of S:
Identify the output vertex de in corresponniig to the class slot of smallest accumulated processing time Pmin in S.
2. For each transfer edge (xf.d 1 in C, transfer Pminn processing time class from machine machine j' in S.

---

Published as a conference paper at ICLR 2025
Figure 1: An example of conversion and transfer graph. Each column represents a machine and each rectangle class slot. Input vertices the left of each class slot and output vertices the right. Conversion edges are dashed and transfer edges are continuous.
3. Delete all vertices corresponding to class slots with zero processing time on machine (which holds at least for zi and z:2
This procedure does not alter the makespan of the original schedule as for each machine along the cycle, there as much processing time added as removed. Each iteration breaks a cycle, removes at least one class slot and never introduces more cycles vertices, and thus terminates. Call the altered final graph G' and the corresponding schedule 5"
Third step We use the acyclic structure of G' to develop strategy assign jobs machines. Let M(c) denote the set of all machines handling class c. Consider hypergraph H = (V, E) related to G' with V = Unec M(c), i.e. the vertex sets correspond all machines which admit at least one class in S", and E {(M(c)), Ve). that is, each hyperedge connects for each class all machines that schedule class e in S' In the following, we prove that H has a strong acyelic property, namely H is Berge-acyclic (Berge (1985)).
Definition 1. A hipartite incidence graph of a graph G = (V, F)) is the graph obtained by G such that it has one vertex for each vertex and each edge in G, and an edge (v,e), v V,e É, v e for e E E w.r.t. G.
Definition 2. graph G (V, is Berge-acyclic if its bipartite incidence graph is acyclic. Lemma 9. H is Berge-acyclic.
Proof. By definition is bipartite, and any cycle in it alternates between the two components of the bipartition. In cycle C each path of the form transfer edge exists from v to v' and the other way around. Note that v * of because this directly reflects the fact that there exists transfer edges from machine to itself. Similarly, each path of the form e - --- e' exists if and only if e, 3 e and thus a conversion edge exists from to e' and the other way around. Again, * because C' is cycle and this is reflected in the fact that conversion edges only go to different classes inside any given machine.
of exists if and only if v, v' and thus
a cycle and
Thus, there is one to one correspondence between cycles in G" and cycles in L. We know that G' is acyclic and as a result I is too, making // Berge-acyclic.
Select a machine i will and set to be the root of H. Since is Berge-acyelic, each hyperedge has unique vertex Te that is closest to the root, i.c., reachable by only hyperedge for classes not containing i, and itself with zero hyperedges for all other classes. The corresponding machine j to x is called the parent machine of class All other machines scheduling that class in S' are child machines of class c, and cannot also be child machines an other class. See Figure 2 for an illustration.
Given with the structural implications for S', we can now state the rules to place an arriving job j with class ey:
if there is a child machine for ej that, according to S", still has unassigned processing time for class Cj. place there,
8

---

Published as a conference paper at ICLR 2025
Class
Class 2
Class
Figure 2: An example of hypergraph H. Class 1 is machines 1 and 2, class on machines 1, 3 and 7, class 3 on machines 2. 4, and 6, and class 4 on machines and Machine is the root and inside each class, arrows go from the parent machine to the child machines.
2. else, place j on the parent machine of cj.
Lemma 10. The job assignment rules above ensure that for any class c:
1. the amount of excess in processing time of placed on a child machine of e most OPT.
2. the amount of excess in processing time of placed on the parent machine of never exceeds the prediction error for
Proof. Regarding the first property, a a.oob, j is never placed on a child machine i that has no available processing time for that class Cy- Further, Pmas I OPT, thus if job exceeds the processing time assigned to Cy on i, it can only do so by at most OPT. In addition to this, child machines can only be child machines of single class. Indeed, two different parent machines, then two different paths to the root exist in the incidence graph, which prohibited by H being Berge-acyclic. These two properties lead to the fact that overflows of different classes cannot accumulate the same machine and that this overflow never exceeds OPT.
machine has
Regarding the second property, job is only placed on the parent machine when all the child machines are full; thus, the excess in processing time caused by jobs on the parent machine can only be smaller equal to the prediction error for this class.
The running time has to be analyzed separately for the preprocessing phase, which is only once at the beginning, and the job assigning phase, which is run for soc, We first analyze the running time of the preprocessing performed before receiving any job. The cardinality constraint problem can be solved in almost linear time Chen et al. (201)):
201/e² log" (1/c) log(1/<)) + On log logn)
The cycle removal procedure can be run in O + b²))) cycle can be found in the
incidence graph by running BFS in O(EE + IV]) O(mk(k 1) + mk(m 1) 2mk) O(mk(m k)). Each iteration removes at least three edges (one conversion and two transfer), so in the worst case, the cycle removal runs in time 0mm2k2(m k²)).
Assigning jobs is computationally cheap, as the algorithm only needs to find any child machine that is not overflowing if there is one the parent machine if there are none. This can be computed by a single pass over all machines, running in (m).
Altogether, get:
For minimizing the makespan for online class constraint scheduling identical machines, there is an algorithm running in time O + (mm2 + k))) with predictions of the processing time of each class with a competitive ratio most t/OPT competitive ratio for an algorithm A used to solve the offline class/cardinality constraint scheduling problem the predicted instance, and T is the running time of A.
Theorem 11.
where is the

---

Published as a conference paper at ICLR 2025
Proof. There are two types of overflow: the ones caused by bad placement due to jobs not summing up to the remaining time in a class slot and the ones due to class size prediction errors.
For the first kind, Lemma 10 states that overflows happen only child machines and are of size at most OPT. Because a machine can only be a child machine of a single class, there cannot be an excess in processing time of more than OPT any machine, adding one to the competitive ratio and leading to a competitive ratio of + a.
For the second kind, in the worst case, the entire prediction emror accumulates on single machine adding e/OPT to the competitive ratio.
Both types happen the same machine the same time, thus have competitive ratio of 1/OPT + a.
We can show that this competitive ratio is optimal up to constant factor:
Theorem 12. For minimizing the makespan for online class constraint scheduling on m identical machines, no algorithm with static class size predictions can achieve &competitiee ratio smaller than E/OPT.
Proof. Let 2, and & S m. The instance contains mk classes. The adversary predicts that all classes are negligible size e. We first get mk jobs of distinct classes and negligible size e. Then, the adversary picks machine For each class This results a prediction error = kN and a schedule with a makespan of NN where the optimal solution would have been to put big job per machine leading optimal makespan of N. The competitive ratio of this instance is thus kN/N = and 1/OPT' = kN/N = k too.
the adversary sends job of size N >
Theorem and Theorem 12 together yield:
Corollary 13. The Class Size Prediction Algorithm is tight up to a constant factor with respect to the competitive ratio.
6 CONCLUSION AND FUTURE WORK
We study online class constraint scheduling in a can access possibly erroneous predictions. We study different models of predictions, and thereby give structured overview of what additional information helps in the design of better scheduling algorithms. In particular, we study full input, action, and the problem-specific class size predictions. For each model, design an algorithm and analyse its consistency and robustness. Additionally, we prove for all algorithms that they are (nearly) tight, i.e., no algorithm can perform (significantly) better with respect to these measures.
setting where an algorithm
The results show that no prediction model generally outperforms the others; their suitability heavily relies the given circumstances. While all algorithms offer good robustness and consistency guar- antees, the algorithm using action predictions most efficient in terms of runtime. This efficiency comes from its direct prediction of actions, whereas the other models need to first compute such actions (i.e., the schedule plan) from the input data. This is NP-hard in general, but approximately optimal solutions can be derived by polynomial time approximation schemes. Access accurate action predictions is the most challenging one, as small differences in the input might lead to very different optimal actions, which makes them hard to learn. Comparatively, input predictions are easier to learn. However, the amount of information is dependent on the number of jobs. Class size prediction turn generates an amount of information just depending on the number of classes, which can be drastically less than the number of jobs making it the most achievable model to be learned.
For each of the models, we give (nearly) matching lower and upper bounds w.r.t. their consistency and robustness. This gives a quite complete picture of the prediction complexity of the problem, but there are interesting extensions to study. In particular, the assumption that know the number of classes in advance could be relaxed if one allows for an error on the class slot limit. Further, we focused on identical machines, but extending the algorithms also work (un-)related machines would broaden the applicability to real-word settings.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Susanne Albers. Better bounds for online scheduling, SIAM J. Comput., 29(2))459-477) 1999.
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In ICML, volume 162 of Proceedings of Machine Learning Research, pp- 582-598.
PMLR, 2022.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 345-355. PMLR, 2020. htt:ttt::////ttm http::/proocecingaa http:
mlr. s.r.press/vll9 ant ontdiiisnnaaaaaaaa htmmmmmmmma..mmmmm....mmmm
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms, 1922:19:1-19:34, 2023,
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In STOC, pp. 1070-1080. ACM, 2021.
Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for minimizing flow time. In Joseph (Seffi) Naor and Niv Buchbinder (eds.), Proceedings of the 2022 ACM- SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 12, 2022, pp. 252 274. SIAM, 2022a. doi: 10.11137119788661197777
URL https://doii .ww.oiorrg/// 103700.1113111 TTT.13......111111 77111119771111177111
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In
Joseph (Seffi) Naor and Niv Buchbinder (eds.), Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference Alexandria, VA, USA, January 9 12, 2022, pp. 35-66. SIAM, 2022b. doi: 10.1137/1.97886119777777 0. 37 978 111166197777777 977073.3
StRlhtts:: //oi orr//
étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL htttpps:/pprcoeed...ggg hew.:eeeeddddn....e............. neurips wwtpaaaisss.ccc..eeeee tttpcc/pppppe. cctppaper/222///aee..
html
Yair Bartal, Amos Fiat, Howard J. Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci., 51(33:359-336 1995.
Claude Berge. Graphs and Hypergraphs. Elsevier Science Ltd, 1985.
Bo Chen and Gerhard J. Potts, Chris N.and Woeginger. A Review of Machine Scheduling: Com- plexity, Algorithms and Approximability pp. 1493-1641. Springer US, Boston, MA, 1998. ISBN 978-1-4613 041-4663-03---
doi: 00000007977781--411-000------999
URL https: /oi. /doii /r.
1007 978 461 01119988---111000---9333-3 125
Lin Chen, Klaus Jansen, Wenchang Luo, and Guochuan Zhang. An efficient ptas for parallel ma- chine scheduling with capacity constraints. T-H. Hubert Chan, Minming Li, and Lusheng Wang (eds.), Combinatorial Optimization and Applications, pp. 608-623, Cham, 2016. Springer International Publishing. ISBN 978-3-319-48749.66
Henrik I. Christensen, A. Khan, Sebastian Pokutta, and Prasad Tetali. Multidimensional bin packing and other related problems: A survey. 2016.
Debasis Dwibedy and Rakesh Mohanty. Semi-online scheduling: survey. Computers & Op- erations Research. 139:105646, 2022. ISSN 0305-0548. doi: https://bbl.rrg//0.111/// 2021. URL https: http:://wwww..cceeeeeeeeee... http:///wwececcc..oooooeeeeeeaaa 8030500587100555

---

Published as a conference paper at ICLR 2025
Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder. Cardinality constrained scheduling in online models. In STACS. volume 219 of LIPIcs, pp. 28:1-28:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
Uirich Faigle, Walter Kern, and György Turán. On the performance of on-line algorithms for partition problems. Acta Cybern., 92)):07-119, 1989. URL attps://cybe:: bibl.
szeged. hu/ index. http://atcccyaaammaaataccc///e/a 3359
Gábor Galambos and Gerhard J. Woeginger. An on-line scheduling heuristic with better worst ratio than graham's 's list scheduling. SIAM J. Comput., 22(2):349-33) -55,, 1993.
Todd Gormley, Nick Reingold, Eric Torng, and Jeffery R. Westbrook. Generating adversaries for request-answer games. In David B. Shmoys (ed.), SODA, pp- 564-565. ACM/SIAM, 2000. URL http::/dl. acm. org/ / c tat ion. wtt.:tttttt..t..n....o.oomm... wtw.ffmmddd333222 338608
R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 4569):156311581 1966. doi: (0.1002//.1538-7770 156.515387775566661... 1966.tb01709.x
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant schedul- ing with predictions. In SPAA, pp. 285-294. ACM, 2021.
Klaus Jansen, Alexandra Lassota, and Marten Maack. Approximation algorithms for scheduling with class constraints. In SPAA, pp. 349-357. ACM, 2020.
David R. Karger, Steven J. Phillips, and Eric Tomg. A better algorithm for ancient scheduling problem. J. Algorithmm, 20(2):400-430, mar 1996. ISSN 0196-6774. doi: 10. 10.1006/jagm. 1996. 0019. URL httpttt::///ttt http://00o.oog///../////
0996.0019
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In ICML, volume 202 of Pro- ceedings of Machine Learning Research, pp. 18563-18583. PMLR, 2023.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Shuchi Chawla (ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 1859-1877. SIAM, 2020. doi: 3781611975994 .144
URL https::/ http://i..or/ro////// 11377.
Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant schedul- ing. In Kunal Agrawal and I-Ting Angelina Lee (eds.), SPAA '22: 34th ACM Symposium on Parallelism Algorithms and Architectures, Philadelphia, PA, USA, July 11 14, 2022, pp. 357- 368. ACM, 2022. doi: 10. 00.1145534901488358877,
URL https: /ooi www.ac..rrrr///ooo..oooooooeeeee
/ 11457
34901 43, 3538579
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssnn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. html
PMLR, 2018. URL
http:://proceedingg mlr. pzzss//80/Lykoouut
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65 (7):33 2022.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In NeurlPS, pp. 9684-9693, 2018
Hadas Shachnai and Tami Tamir. Polynomial time approximation schemes for class- constraied packing problems. In Klaus Jansen and Samir Khuller (eds.), Approximation Algorithmss for Combinatorial Optimization, pp. 238-249, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. ISBN 978-3-540-44436.
Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logisties Quarterly, 3(1-2):59 66. 1956. doi: http:://ibbooogg/...000///aaaa.. o/on1 in bra ry. wi wowpy..co//o//ab////eeeeee 1002 3800030106
URL hetps:
12

---

Published as a conference paper at ICLR 2025
Vitaly A. Strusevich. Hans kellerer, ulrich pferschy and david pisinger, Knapsack Problems, springer, berlin (2004) ISBN 3-540-40286-1 546pp., EUR 99, 95, Oper. Res. Lett.. 33(2):217- 219. 2005. doi: 10.10166f..r.220440..0000.. URL ULL_ttpss///c...or///00111111111
2004. 07. 002
Conglin Zhang, Gang Wang, Xiaoguang Liu, and Jing Liu. Approximating scheduling machines with capacity constraints. 06 2009. ISBN 08----42--22299 doi:
29.
13


Reviews:
[{"review_id": "fWYa4JO0BL", "reviewer": "Reviewer_ZJ1K", "summary": "The paper considers the problem of online makespan minimization with class constraints. There are $m$ machines and $n$ jobs, each of which have a class associated with them. The goal is to assign jobs to machines to minimize the makespan (the max load on any machine) subject to the constraint that no machines has more than $k$ distinct classes associated with it. \nAlthough the offline problem admits an EPTAS, the online problem seems to be associated with strong lower bounds of $m$. In other words, a random assignment of classes to machines and then jobs to the classes is the best one can hope to do in this setting.\n\nThe authors consider this problem in the learning augmented setting where we are given a prediction about the instance before hand. The competitive ratio depends on the deviation from the true outcome from the prediction and the worst case competitive ratio.  The authors talk about three main types of prediction:\n\n1) Full Input Prediction - The entire instance is predicted along with the class type and the process time.  The error is taken as the difference in the process times if the class prediction is correct and the entire process time if the class prediction is incorrect. \n2) Full Action Prediction - The entire action is predicted of which jobs ...\n3) Class Size Predictions - The total process time for each class is predicted but not hte number of jobs. \n\nIn all the models, the authors achieve competitive ratios better than $m$.", "questions": "N/A", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The algorithms they produce are fairly simple for the first two models. Essentially one simply computes the best according to the offline optimum and then adjusts for mistakes in a straightforward way using values. \nThe most interesting algorithm is for the class size prediction model where we only have a prediction about the total size of each class.  Here they show that one can compute the offline optimal for the whole sequence and then partition the set of used machines so that no two have the same set of classes on them. This can now define a hierarchy and a corresponding simple procedure shows how we can place the jobs as they arrive.", "weaknesses": "The contributions seems poor for a publication at ICLR. The only interesting algorithm is the for the class based model and even then the algorithm doesn't introduce any new techniques or ideas which generalize to other problems.", "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": "v8J9bR0BqN", "reviewer": "Reviewer_QrRR", "summary": "This paper studies online scheduling with class constraints. There are $m$ machines, $n$ jobs each with some processing time, jobs arrive one-by-one and must be placed on one of the $m$ machines. In addition to the standard goal of minimizing the makespan, there is a class constraint: each job belongs to one of finitely many classes and each machine can only support a total of $k$ classes. Since there are strong impossibility results in this setting, this paper considers the setting when the online algorithm has access to predictions about the input. The authors consider three different types of predictions and provide matching upper and lower bounds on the competitive ratios.", "questions": "1. Can you motivate the class size prediction model a bit more? Why does predicting the total processing time of each class make sense? Can you contextualize this with an application? (I suspect, for example, that one could use historical data and analyze the load of different types of jobs for a workflow and use that as the prediction. But it would be good to see a discussion of this in the paper.)\n2. To compute the schedule plan, you assume that each class can be split into arbitrary-sized pieces. But the actual jobs themselves are not splittable - is this correct? \n3. If you get more fine-grained information about the class sizes, do you think we could do better? For example, instead of the total processing time, maybe a distribution of the total processing time?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper studies an important problem in online scheduling, i.e., that of class constraints.\n* The paper studies the problem quite comprehensively - it shows the need for knowing the number of jobs, and proceeds to show upper and lower bounds on the competitive ratio for three different prediction models. Furthermore, the competitive ratios also show the dependence on the accuracy of the predictions.\n* The algorithm for class size prediction is very interesting. For example, I liked how it leverages existing algorithms to come up with a schedule and then modifies it to arranges machines in a hierarchy.\n* The paper is well written and easy to follow.", "weaknesses": "* Overall, this paper is well written. I am not *super* familiar with this specific sub-area, so I can't think of any major weaknesses. There are some minor presentation suggestions:\n    1. I didn't understand Figure 1 until I read the text carefully. I suggest editing the figure to make it more self-contained. In its current form, the figure is very hard to understand.\n    2. As I was reading the text and encountered the word \"adversary\", especially in your proofs, I wasn't super sure about the power of the adversary. It would be good to clarify whether it is oblivious or adaptive.\n    3. Lines 103-107: It seems like this is formalized in Theorem 1? I found that easier to understand than this description. It might help to add a pointer to Theorem 1 here so that readers can refer to that instead if needed.", "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": "s2F0PKs20e", "reviewer": "Reviewer_rcrR", "summary": "The authors study the problem of online scheduling of tasks of possibly different classes and durations on $m$ machines, under the constraint that each machine can take care of at most $k$ different types of classes. More specifically, the authors study the problem of learning-augmented online scheduling, where predictions are given to the agent, and the objective is to design algorithms that achieve good performance if those predictions are accurate, while being robust if they are not.\n\nThe authors start by showing that no algorithm can achieve non-trivial regret when the number of classes is unknown. Then, they consider predictions on the class and durations of the jobs. They propose an algorithm, bound its competitive ratio and provide a lower bound for this problem, showing that this algorithm is optimal up to constant terms. Then, they consider predictions on the machine on which the jobs should be scheduled. Here again, they propose an algorithm, bound its competitive ratio and provide a lower bound for this problem, showing that this algorithm is optimal up to constant terms. Finally, they consider predictions on the total makespan of each class of jobs. They propose an algorithm, bound its competitive ratio and provide a lower bound for this problem, showing that this algorithm is optimal up to constant terms.", "questions": "Could you please consider rewriting the proof of Theorem 7?\n\nIn Section 5, it seems unclear to me why we can virtually allow to split jobs without paying for it in the competitive ratio. Could you discuss this fact?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This papers adresses a natural problem, and study a variety of predictions types, providing a good understanding of this problem. The paper is mostly clearly written and self-contained. Although I am not an expert on the subject, and I can not really assess the novelty of the technics used, it appears to fill a gap in the set of existing results.", "weaknesses": "Some parts of the article could be rephrased to improve their clarity : \n- In general, I believe it could be usefull to remind some definitions (objective, constraints, what is the optimal ratio etc) using mathematical formalism.\n- I find the proof of Theorem 7 particularly unclear. Could you formalize more the problem instance you are considering?\n\nMinor remarks : \n- The beginning of Section 2 should read : \"we assume\", \"we argue\" instead of \"we assumed\", \"we argued\" (except if you are refering to the previous sections instead of the following sections?)\n- The legend in Figure 2 does not seem to match the figure. Class 3 seems to be scheduled on machines 2,4,5,6 (instead of 3,4,5,6), and class 4 seems to be scheduled on machines 3,8 (instead of 3,4).", "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": "RbolFCNqco", "reviewer": "Reviewer_3H61", "summary": "This paper studies online scheduling with class constraints. Here, the constraints impose that the number of distinct classes a machine can take is bounded. The offline version of the problem is known to be NP-hard while PTAS exists for it. For the online setting, as expected, there exist impossibility results for deducing competitive ratios. Given these hardness results, the paper considers scenarios where the scheduler has access to some information about the problem instance. Here, the information is given by some possibly noisy predictions about the problem instance. The paper studies three different models: (1) full input prediction, (2) action prediction, and (3) class size prediction. Algorithms that guarantee nearly tight competitive ratios for the settings are provided and analyzed in the paper.", "questions": "Would it be possible to motivate the problem settings, especially the three prediction regimes, in the context of concrete practical applications? The reader would be interested in how the learning process and the prediction results can be obtained and how the prediction errors are estimated. Without discussing this, the paper would be a better fit for a theoretical computer science venue.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Concrete problem settings with different prediction models are proposed and studied.\n2. Tight algorithms for the three settings are provided with a rigorous theoretical analysis.", "weaknesses": "1. It is not clear whether the prediction models appear in practice. \n2. No concrete practical application is discussed.", "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)