Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: Asymptotics of the stationary distribution

David Gamarnik, Alexander L. Stolyar

Research output: Contribution to journalArticle

Abstract

We consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin-Whitt sense, namely the nominal utilization is, where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Qr(∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case. This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form, on both Qr(∞) and the number of idle servers. The bounds are uniform w. r. t. parameter r and the service policy. In particular, we show that. Therefore, the sequence, is tight and has a uniform exponential tail bound. We further consider the system with strictly positive abandonment rates, and show that in this case every weak limit, has a sub-Gaussian tail. Namely, E[exp(theta(Q̂(∞))2)]< ∞, for some θ>0.

Original languageEnglish (US)
Pages (from-to)25-51
Number of pages27
JournalQueueing Systems
Volume71
Issue number1-2
DOIs
StatePublished - Jun 1 2012
Externally publishedYes

Fingerprint

Servers
Queueing system
Stationary distribution
Heavy traffic
Queue
Scaling

Keywords

  • Exponential bounds
  • Heavy traffic
  • Limit interchange
  • Multiclass multiserver system
  • Stationary distribution asymptotics

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Cite this

Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime : Asymptotics of the stationary distribution. / Gamarnik, David; Stolyar, Alexander L.

In: Queueing Systems, Vol. 71, No. 1-2, 01.06.2012, p. 25-51.

Research output: Contribution to journalArticle

@article{6b775b2bc3b4423c8ff8e7629f7bf316,
title = "Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: Asymptotics of the stationary distribution",
abstract = "We consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin-Whitt sense, namely the nominal utilization is, where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Qr(∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case. This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form, on both Qr(∞) and the number of idle servers. The bounds are uniform w. r. t. parameter r and the service policy. In particular, we show that. Therefore, the sequence, is tight and has a uniform exponential tail bound. We further consider the system with strictly positive abandonment rates, and show that in this case every weak limit, has a sub-Gaussian tail. Namely, E[exp(theta(Q̂(∞))2)]< ∞, for some θ>0.",
keywords = "Exponential bounds, Heavy traffic, Limit interchange, Multiclass multiserver system, Stationary distribution asymptotics",
author = "David Gamarnik and Stolyar, {Alexander L.}",
year = "2012",
month = "6",
day = "1",
doi = "10.1007/s11134-012-9294-x",
language = "English (US)",
volume = "71",
pages = "25--51",
journal = "Queueing Systems",
issn = "0257-0130",
publisher = "Springer Netherlands",
number = "1-2",

}

TY - JOUR

T1 - Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime

T2 - Asymptotics of the stationary distribution

AU - Gamarnik, David

AU - Stolyar, Alexander L.

PY - 2012/6/1

Y1 - 2012/6/1

N2 - We consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin-Whitt sense, namely the nominal utilization is, where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Qr(∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case. This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form, on both Qr(∞) and the number of idle servers. The bounds are uniform w. r. t. parameter r and the service policy. In particular, we show that. Therefore, the sequence, is tight and has a uniform exponential tail bound. We further consider the system with strictly positive abandonment rates, and show that in this case every weak limit, has a sub-Gaussian tail. Namely, E[exp(theta(Q̂(∞))2)]< ∞, for some θ>0.

AB - We consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin-Whitt sense, namely the nominal utilization is, where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Qr(∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case. This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form, on both Qr(∞) and the number of idle servers. The bounds are uniform w. r. t. parameter r and the service policy. In particular, we show that. Therefore, the sequence, is tight and has a uniform exponential tail bound. We further consider the system with strictly positive abandonment rates, and show that in this case every weak limit, has a sub-Gaussian tail. Namely, E[exp(theta(Q̂(∞))2)]< ∞, for some θ>0.

KW - Exponential bounds

KW - Heavy traffic

KW - Limit interchange

KW - Multiclass multiserver system

KW - Stationary distribution asymptotics

UR - http://www.scopus.com/inward/record.url?scp=84861871968&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861871968&partnerID=8YFLogxK

U2 - 10.1007/s11134-012-9294-x

DO - 10.1007/s11134-012-9294-x

M3 - Article

AN - SCOPUS:84861871968

VL - 71

SP - 25

EP - 51

JO - Queueing Systems

JF - Queueing Systems

SN - 0257-0130

IS - 1-2

ER -