Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics
We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy-traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly two weakly converges to a two-dimens...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120946 https://orcid.org/0000-0003-4865-7645 https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1811070929355145216 |
|---|---|
| author | Eschenfeldt, Patrick Clark Gamarnik, David |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Eschenfeldt, Patrick Clark Gamarnik, David |
| author_sort | Eschenfeldt, Patrick Clark |
| collection | MIT |
| description | We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy-traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly two weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is comparable to that of the traditional Halfin-Whitt model, but there are key differences in the queueing behavior of the JSQ model. In particular, only a vanishing fraction of customers will have to wait, but those who do incur a constant order waiting time. Keywords: queueing theory; parallel queues; diffusion models |
| first_indexed | 2024-09-23T08:43:54Z |
| format | Article |
| id | mit-1721.1/120946 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:43:54Z |
| publishDate | 2019 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1209462022-09-30T10:51:07Z Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics Eschenfeldt, Patrick Clark Gamarnik, David Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Eschenfeldt, Patrick Clark Gamarnik, David We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy-traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly two weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is comparable to that of the traditional Halfin-Whitt model, but there are key differences in the queueing behavior of the JSQ model. In particular, only a vanishing fraction of customers will have to wait, but those who do incur a constant order waiting time. Keywords: queueing theory; parallel queues; diffusion models 2019-03-13T14:16:24Z 2019-03-13T14:16:24Z 2018-02 2019-02-13T17:59:33Z Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/120946 Eschenfeldt, Patrick and David Gamarnik. “Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics.” Mathematics of Operations Research 43, 3 (August 2018): 867–886 © 2018 INFORMS https://orcid.org/0000-0003-4865-7645 https://orcid.org/0000-0001-8898-8778 http://dx.doi.org/10.1287/MOOR.2017.0887 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Eschenfeldt, Patrick Clark Gamarnik, David Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title | Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title_full | Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title_fullStr | Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title_full_unstemmed | Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title_short | Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics |
| title_sort | join the shortest queue with many servers the heavy traffic asymptotics |
| url | http://hdl.handle.net/1721.1/120946 https://orcid.org/0000-0003-4865-7645 https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT eschenfeldtpatrickclark jointheshortestqueuewithmanyserverstheheavytrafficasymptotics AT gamarnikdavid jointheshortestqueuewithmanyserverstheheavytrafficasymptotics |