Near-Optimal Learning-Augmented Online Scheduling with and without Rejection

We study learning-augmented online scheduling on $m$ identical parallel machines, both with and without rejection. Each arriving job reveals its processing time and a predicted machine assignment, which may instead recommend rejection when allowed. Decisions are irrevocable, and the objective is makespan plus any rejection penalties. Our algorithms use two load caps in the no-rejection setting and cost comparisons with a prediction-free reference scheduler when rejection is allowed. Both are $(1+\epsilon )$-consistent, degrade smoothly with prediction error, and retain worst-case guarantees under arbitrary predictions. We further establish robustness lower bounds for all deterministic online algorithms satisfying the same consistency requirement, showing that both algorithms attain optimal robustness for sufficiently small $\epsilon$ and remain near-optimal over wider parameter ranges. We conclude our work with an empirical analysis of our method.