CMU-CS-02-201
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-02-201

Competitive Analysis of M/GI/1/ Queueing Policies

Nikhil Bansal, Adam Wierman

November 2002

CMU-CS-02-201.ps
CMU-CS-02-201.pdf


Keywords: Queueing, competitive analysis, scheduling, M/G/1; FB, LAS, SET, feedback, least attained service, shortest elapsed time, SRPT, shortest remaining processing time, regular variation


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.

15 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]