Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee
- 1College of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
- 2College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
- 3Division of Logistics and Transportation, Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China
Abstract
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.
Related
- Mean Gain Is Not a Guarantee: Risk-Controlled Open-Loop Scheduling for Ka-Band LEO Semantic Downlinks
- Integrating survival analysis and machine learning for modeling overtaking duration on rural two-lane highways
- PL conditions do not guarantee convergence of gradient descent-ascent dynamics
- Density-Driven Area Coverage for Nonholonomic Multi-Robot Systems with Safety Guarantee
- Diminishing Returns of Data in Sparse Autoencoders: Functional Behavior does not Guarantee Feature Reproducibility
BibTeX
@article{guo2026predictiondriven,
title = {{Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee}},
author = {Yazhou Guo and Zexin Lin and Chengyang Huo and Yurong Song},
journal = {Mathematics},
year = {2026},
month = nov,
doi = {10.3390/math14214020},
url = {https://www.mdpi.com/2227-7390/14/21/4020},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee
AU - Yazhou Guo
AU - Zexin Lin
AU - Chengyang Huo
AU - Yurong Song
PY - 2026
DA - 2026/11/03
JO - Mathematics
DO - 10.3390/math14214020
UR - https://www.mdpi.com/2227-7390/14/21/4020
AB - 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.
SN - 2227-7390
ER -