A Caltech Library Service

Multi-Server queueing systems with multiple priority classes

Harchol-Balter, Mor and Osogami, Takayuki and Scheller-Wolf, Alan and Wierman, Adam (2005) Multi-Server queueing systems with multiple priority classes. Queueing Systems, 51 (3-4). pp. 331-360. ISSN 0257-0130. doi:10.1007/s11134-005-2898-7.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access ReadCube access - Correction
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.
Errata:Harchol-Balter, M., Osogami, T., Scheller-Wolf, A. et al. Correction to: Multi-server queueing systems with multiple priority classes. Queueing Syst (2021).
Funding AgencyGrant Number
Pittsburgh Digital Greenhouse2003
Subject Keywords:M/GI/k, M/PH/k, multi-server queue, priority queue, matrix analytic methods, busy periods, multi-class queue, server farm, preemptive priority
Issue or Number:3-4
Classification Code:AMS subject classification: 60K25, 68M20, 90B22, 90B36
Record Number:CaltechAUTHORS:20200810-134515351
Persistent URL:
Official Citation:Harchol-Balter, M., Osogami, T., Scheller-Wolf, A. et al. Multi-Server Queueing Systems with Multiple Priority Classes. Queueing Syst 51, 331–360 (2005).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104884
Deposited By: Rebecca Minjarez
Deposited On:12 Aug 2020 22:27
Last Modified:28 Sep 2021 21:57

Repository Staff Only: item control page