TY - JOUR
T1 - M/M/c Queue with Two Priority Classes
AU - Wang, Jianfu
AU - Baron, Opher
AU - Scheller-Wolf, Alan
PY - 2015/5
Y1 - 2015/5
N2 - This paper provides the first exact analysis of a preemptive M/M/c queue with two priority classes having different service rates. To perform our analysis, we introduce a new technique to reduce the two-dimensionally infinite Markov chain (MC), representing the two class state space, into a one-dimensionally infinite MC, from which the generating function (GF) of the number of low-priority jobs can be derived in closed form. (The high-priority jobs form a simple M/M/c system and are thus easy to solve.) We demonstrate our methodology for the c = 1, 2 cases; when c > 2, the closed-form expression of the GF becomes cumbersome. We thus develop an exact algorithm to calculate the moments of the number of low-priority jobs for any c ≥ 2. Numerical examples demonstrate the accuracy of our algorithm and generate insights on (i) the relative effect of improving the service rate of either priority class on the mean sojourn time of low-priority jobs; (ii) the performance of a system having many slow servers compared with one having fewer fast servers; and (iii) the validity of the square root staffing rule in maintaining a fixed service level for the low-priority class. Finally, we demonstrate the potential of our methodology to solve other problems using the M/M/c queue with two priority classes, where the high-priority class is completely impatient.
AB - This paper provides the first exact analysis of a preemptive M/M/c queue with two priority classes having different service rates. To perform our analysis, we introduce a new technique to reduce the two-dimensionally infinite Markov chain (MC), representing the two class state space, into a one-dimensionally infinite MC, from which the generating function (GF) of the number of low-priority jobs can be derived in closed form. (The high-priority jobs form a simple M/M/c system and are thus easy to solve.) We demonstrate our methodology for the c = 1, 2 cases; when c > 2, the closed-form expression of the GF becomes cumbersome. We thus develop an exact algorithm to calculate the moments of the number of low-priority jobs for any c ≥ 2. Numerical examples demonstrate the accuracy of our algorithm and generate insights on (i) the relative effect of improving the service rate of either priority class on the mean sojourn time of low-priority jobs; (ii) the performance of a system having many slow servers compared with one having fewer fast servers; and (iii) the validity of the square root staffing rule in maintaining a fixed service level for the low-priority class. Finally, we demonstrate the potential of our methodology to solve other problems using the M/M/c queue with two priority classes, where the high-priority class is completely impatient.
KW - multiserver queue
KW - multiclass
KW - preemptive priority
KW - different service rates
UR - https://www.dropbox.com/s/9kfyu2fj27rnulf/MMcPriorityQueue.m?dl=0
UR - http://www.scopus.com/inward/record.url?scp=84930817338&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84930817338&origin=recordpage
U2 - 10.1287/opre.2015.1375
DO - 10.1287/opre.2015.1375
M3 - 21_Publication in refereed journal
VL - 63
SP - 733
EP - 749
JO - Operations Research
JF - Operations Research
SN - 0030-364X
IS - 3
ER -