Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee

Before a programming deadline, many students’ programs queue for a few grading servers. Ordering them by predicted running time cuts the mean wait, but known bounds with predictions hold on average or against an optimum, not per job. We prove an identity for k non-preemptive, work-conserving servers with time limit L. A job’s extra wait over first-come first-served (FCFS) equals the net running time of jobs that overtook it, divided by k, up to a tight error of (2 − 2/k)L. A guard around any scheduler caps the work that passes each job, so every job stays within a promise G, whatever the arrivals and predictions. Its additive constant (3 − 2/k)L is exact, and completion reports delayed by δ add at most L + δ. On one test term, gradient-boosted trees, a recurrent network and a heterogeneous graph neural network predicted running times about equally well. On three course terms withheld until the method was frozen, a guard promising 600 s kept 0.894 (class-term interval 0.116–0.933) of shortest-job-first’s reduction in the simulated 99th-percentile wait before deadlines at the busiest load. The gain shrank above full load. On a second platform, run at twice its target load, the promise held but the gain did not appear.