Competitive Analysis of M/GI/1 Queueing Policies
Nikhil Bansal, Adam Wierman · 2003
We propose a framework for comparing the performance of two queueing policies. Our framework is motivated by the notion of competitive analysis, widely used by the computer science community to analyze the performance of online algorithms. We apply our framework to compare M/GI/1/FB and M/GI/1/SJF with M/GI/1/SRPT, and obtain new results about the performance of M/GI/1/FB and M/GI/1/SJF. Keywords: Queueing; competitive analysis; scheduling; M/G/1; FB; LAS; SET; feedback; least attained service; shortest elapsed time; SRPT; shortest remaining pro-cessing time; regular variation 1