Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2005 | metadata_only
Journal Article

Multi-Server queueing systems with multiple priority classes


We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—"smart" prioritization (giving priority to the smaller jobs) versus "stupid" prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes.

Additional Information

© 2005 Springer Science + Business Media, Inc. Received 2 October 2004; Revised 8 March 2005. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003.


Harchol-Balter, M., Osogami, T., Scheller-Wolf, A. et al. Correction to: Multi-server queueing systems with multiple priority classes. Queueing Syst (2021). https://doi.org/10.1007/s11134-021-09710-1

Additional details

August 19, 2023
September 7, 2023