Uniform Bounds for Scheduling with Job Size Estimates

on YouTube ↗27m

" summary

Single-server queuing with Poisson arrivals and multiplicative beta-alpha bounded noise on job size estimates gets a new rank-based scheduler RaDiCal that is provably 1-consistent and 3.5-graceful (so perfect performance as alpha,beta→1 and a 3.5 bound on degradation). Naive and Checkmark fail; analysis uses two tools SOAP (response-time formula for age-ranked policies) and WINE (R-work integral reducing mean delay to SRPT comparisons via the intermediate SCALE policy), and the proofs show the policy is implementable and effective.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:58Agenda
3. 1:22Stochastic Queue Model
4. 5:46Noise Model
5. 8:21Common Goals
6. 11:46Recap
7. 12:38Rank Functions
8. 14:04Whats the right rank function
9. 15:19Checkmark
10. 17:33Comparison
11. 20:01Soap
12. 20:51Wine
13. 21:49Work
14. 22:49Wine Theorem
15. 25:32Conclusion