Minimalistic Predictions for Online Class Constraint Scheduling

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 processing time p j and 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 [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 learningaugmented 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.