Robust Queueing Theory
We propose an alternative approach for studying queues based on robust optimization. We model the uncertainty in the arrivals and services via polyhedral uncertainty sets, which are inspired from the limit laws of probability. Using the generalized central limit theorem, this framework allows us to...
| Автори: | , , |
|---|---|
| Інші автори: | |
| Формат: | Стаття |
| Опубліковано: |
Institute for Operations Research and the Management Sciences (INFORMS)
2019
|
| Онлайн доступ: | http://hdl.handle.net/1721.1/120847 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-3807-8607 |
| _version_ | 1826193417808379904 |
|---|---|
| author | Bandi, Chaithanya Bertsimas, Dimitris J Youssef, Nataly |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bandi, Chaithanya Bertsimas, Dimitris J Youssef, Nataly |
| author_sort | Bandi, Chaithanya |
| collection | MIT |
| description | We propose an alternative approach for studying queues based on robust optimization. We model the uncertainty in the arrivals and services via polyhedral uncertainty sets, which are inspired from the limit laws of probability. Using the generalized central limit theorem, this framework allows us to model heavy-tailed behavior characterized by bursts of rapidly occurring arrivals and long service times. We take a worst-case approach and obtain closed-form upper bounds on the system time in a multi-server queue. These expressions provide qualitative insights that mirror the conclusions obtained in the probabilistic setting for light-tailed arrivals and services and generalize them to the case of heavy-tailed behavior. We also develop a calculus for analyzing a network of queues based on the following key principles: (a) the departure from a queue, (b) the superposition, and (c) the thinning of arrival processes have the same uncertainty set representation as the original arrival processes. The proposed approach (a) yields results with error percentages in single digits relative to simulation, and (b) is to a large extent insensitive to the number of servers per queue, network size, degree of feedback, and traffic intensity; it is somewhat sensitive to the degree of diversity of external arrival distributions in the network. |
| first_indexed | 2024-09-23T09:38:57Z |
| format | Article |
| id | mit-1721.1/120847 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:38:57Z |
| publishDate | 2019 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1208472022-09-30T15:57:47Z Robust Queueing Theory Bandi, Chaithanya Bertsimas, Dimitris J Youssef, Nataly Sloan School of Management Bandi, Chaithanya Bertsimas, Dimitris J Youssef, Nataly We propose an alternative approach for studying queues based on robust optimization. We model the uncertainty in the arrivals and services via polyhedral uncertainty sets, which are inspired from the limit laws of probability. Using the generalized central limit theorem, this framework allows us to model heavy-tailed behavior characterized by bursts of rapidly occurring arrivals and long service times. We take a worst-case approach and obtain closed-form upper bounds on the system time in a multi-server queue. These expressions provide qualitative insights that mirror the conclusions obtained in the probabilistic setting for light-tailed arrivals and services and generalize them to the case of heavy-tailed behavior. We also develop a calculus for analyzing a network of queues based on the following key principles: (a) the departure from a queue, (b) the superposition, and (c) the thinning of arrival processes have the same uncertainty set representation as the original arrival processes. The proposed approach (a) yields results with error percentages in single digits relative to simulation, and (b) is to a large extent insensitive to the number of servers per queue, network size, degree of feedback, and traffic intensity; it is somewhat sensitive to the degree of diversity of external arrival distributions in the network. 2019-03-11T13:17:14Z 2019-03-11T13:17:14Z 2015-06 2019-01-28T17:22:15Z Article http://purl.org/eprint/type/JournalArticle 0030-364X 1526-5463 http://hdl.handle.net/1721.1/120847 Bandi, Chaithanya, Dimitris Bertsimas, and Nataly Youssef. “Robust Queueing Theory.” Operations Research 63, no. 3 (June 2015): 676–700. https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-3807-8607 http://dx.doi.org/10.1287/OPRE.2015.1367 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) MIT web domain |
| spellingShingle | Bandi, Chaithanya Bertsimas, Dimitris J Youssef, Nataly Robust Queueing Theory |
| title | Robust Queueing Theory |
| title_full | Robust Queueing Theory |
| title_fullStr | Robust Queueing Theory |
| title_full_unstemmed | Robust Queueing Theory |
| title_short | Robust Queueing Theory |
| title_sort | robust queueing theory |
| url | http://hdl.handle.net/1721.1/120847 https://orcid.org/0000-0002-1985-1003 https://orcid.org/0000-0003-3807-8607 |
| work_keys_str_mv | AT bandichaithanya robustqueueingtheory AT bertsimasdimitrisj robustqueueingtheory AT youssefnataly robustqueueingtheory |