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*

November 2003

Keywords: Scheduling, queueing, multiserver, priority, preemptive, FCFS, response time, M/GI/k, dimensionality reduction, busy period, phase type

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.

16 pages

*Carnegie Mellon University, Graduate School of Industrial Administration

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

This page maintained by