Probability Seminar Ziv Scully (CMU)

SOAP: One Clean Analysis of All Age-Based Scheduling Policies
  • What Scientific Computing English Seminars
  • When 11-12-2018 from 14:30 to 15:30 (Europe/Amsterdam / UTC100)
  • Where KdVI (building 105-107) F3.20
  • Contact Name
  • Web Visit external website
  • Add event to calendar iCal

We consider an extremely broad class of M/G/1 scheduling policies called SOAP: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe not even conceived. SOAP policies range from classic policies, like first-come, first-serve (FCFS), foreground-background (FB), class-based priority, and shortest remaining processing time (SRPT); to much more complicated scheduling rules, such as shortest expected remaining processing time (SERPT), the famously complex Gittins index policy, and other policies in which a job's priority changes arbitrarily with its age. While the response time of policies in the former category is well understood, policies in the latter category have resisted response time analysis. We present a universal analysis of all SOAP policies, deriving the mean and Laplace-Stieltjes transform of response time.