Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
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–W...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/75009 https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1811097845601665024 |
|---|---|
| author | Gamarnik, David Stolyar, Alexander L. |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Gamarnik, David Stolyar, Alexander L. |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | 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 1−a/r√ 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 Q [superscript r] (∞). 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 O(r√) on both Q [superscript r] (∞) and the number of idle servers. The bounds are uniform w.r.t. parameter r and the service policy. In particular, we show that lim sup[subscript r]Eexp(θr[superscript −1/2)Q[superscript r](∞))<∞ . Therefore, the sequence r[superscript −1/2]Q[superscript r](∞) 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 [ˆ over Q](∞) of r[superscript −1/2]Q[superscript r](∞) has a sub-Gaussian tail. Namely, E[exp(θ([ˆ over Q](∞))[superscript 2])]<∞ , for some θ>0. |
| first_indexed | 2024-09-23T17:05:32Z |
| format | Article |
| id | mit-1721.1/75009 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:05:32Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/750092022-09-29T23:37:36Z Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution Gamarnik, David Stolyar, Alexander L. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Gamarnik, David 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 1−a/r√ 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 Q [superscript r] (∞). 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 O(r√) on both Q [superscript r] (∞) and the number of idle servers. The bounds are uniform w.r.t. parameter r and the service policy. In particular, we show that lim sup[subscript r]Eexp(θr[superscript −1/2)Q[superscript r](∞))<∞ . Therefore, the sequence r[superscript −1/2]Q[superscript r](∞) 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 [ˆ over Q](∞) of r[superscript −1/2]Q[superscript r](∞) has a sub-Gaussian tail. Namely, E[exp(θ([ˆ over Q](∞))[superscript 2])]<∞ , for some θ>0. National Science Foundation (U.S.) (Grant CMMI-0726733) 2012-11-26T17:30:26Z 2012-11-26T17:30:26Z 2012-04 2012-02 Article http://purl.org/eprint/type/JournalArticle 0257-0130 1572-9443 http://hdl.handle.net/1721.1/75009 Gamarnik, David, and Alexander L. Stolyar. “Multiclass Multiserver Queueing System in the Halfin–Whitt Heavy Traffic Regime: Asymptotics of the Stationary Distribution.” Queueing Systems 71.1-2 (2012): 25–51. https://orcid.org/0000-0001-8898-8778 en_US http://dx.doi.org/10.1007/s11134-012-9294-x Queueing Systems Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Gamarnik, David Stolyar, Alexander L. Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title | Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title_full | Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title_fullStr | Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title_full_unstemmed | Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title_short | Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution |
| title_sort | multiclass multiserver queueing system in the halfin whitt heavy traffic regime asymptotics of the stationary distribution |
| url | http://hdl.handle.net/1721.1/75009 https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT gamarnikdavid multiclassmultiserverqueueingsysteminthehalfinwhittheavytrafficregimeasymptoticsofthestationarydistribution AT stolyaralexanderl multiclassmultiserverqueueingsysteminthehalfinwhittheavytrafficregimeasymptoticsofthestationarydistribution |