Rigorous Systems Research Group (RSRG) Seminar

We are interested in scheduling policies for the G/G/1 queue where we wish to minimize the average sojourn time. It is well known that this objective is minimized by the Shortest Remaining Processing Time (SRPT) policy; however, this policy needs to know all job sizes upon arrival in the system. If this information is not available then the server needs to resort to so-called blind policies. Naturally, we now wonder which blind policy to choose in order to perform as good as possible, and how big the performance gap is when compared to the SRPT policy. This talk addresses these two questions and presents a known blind policy that is (in some sense) optimal. The proof of this result displays a promising hybrid of competitive analysis and applied probability techniques.