Computer Science Department
School of Computer Science, Carnegie Mellon University
How Many Servers are Best in a Fual-Priority FCFS System?
Takayuki Osogami, Adam Wierman, Mor Harchol-Balter, Alan Scheller-Wolf*
Keywords: Scheduling, queueing, multiserver, priority, preemptive,
FCFS, response time, M/GI/k, dimensionality reduction, busy period,
We ask the question, "for minimizing mean response time, which is
preferable: one fast server of speed 1, or k slow servers each of
speed 1/k?" Our setting is the M/GI/k system with two priority
classes of customers, high priority and low priority, where G is a
phase-type distribution. We find that multiple slow servers are often
preferable --- and we demonstrate exactly how many servers are
preferable as a function of load and G. In addition, we find that
the optimal number of servers with respect to the high priority jobs
may be very different from that preferred by low priority jobs, and we
characterize these preferences. We also evaluate the optimal number
of servers with respect to overall mean response time, averaged over
high and low priority jobs. Lastly, we ascertain the effect of the
variability of high priority jobs on low priority jobs.
This paper is the first to analyze an M/GI/k system with two
priority classes and a general phase-type distribution. Prior
analyses of the M/GI/k with two priority classes either require
that G be exponential, or are approximations that work
well when G is exponential, but are less reliable for more
variable G. Our analytical method is very different from the prior
literature: it combines the technique of dimensionality reduction with
Neuts' technique for determining busy periods in multiserver systems.
Our analysis is approximate, but can be made as accurate as desired,
and is verified via simulation.
*Carnegie Mellon University, Graduate School of Industrial Administration