SOAP: One Clean Analysis of All Age-Based Scheduling Policies - VVSOR - VVSOR

Vereniging voor Statistiek en Operations Research
12 December 2018

SOAP: One Clean Analysis of All Age-Based Scheduling Policies

We would like to invite you to the following talk of the Eindhoven Stochastics Colloquium:

Ziv Scully (Carnegie Mellon University)  – SOAP: One Clean Analysis of All Age-Based Scheduling Policies

Wednesday 12 December, 11:00-11.45, Room MF 12 (4th floor, MetaForum Building, TU/e)

 

ABSTRACT:
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.

Upcoming events of the Eindhoven Stochastics Colloquium: http://www.win.tue.nl/StoSem/