Robust Queueing Theory

Chaithanya Bandi (), Dimitris Bertsimas () and Nataly Youssef ()
Additional contact information
Chaithanya Bandi: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Dimitris Bertsimas: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Nataly Youssef: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2015, vol. 63, issue 3, 676-700

Abstract: 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.

Keywords: queueing theory; robust optimization; heavy tails; queueing networks (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1367 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:3:p:676-700

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().