MAD Dispersion Measure Makes Extremal Queue Analysis Simple

Wouter van Eekelen (), Dick den Hertog () and Johan S.H. van Leeuwaarden ()
Additional contact information
Wouter van Eekelen: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands
Dick den Hertog: Amsterdam Business School, University of Amsterdam, 1012 WX Amsterdam, Netherlands
Johan S.H. van Leeuwaarden: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands; Department of Mathematics and Computer Science, Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands

INFORMS Journal on Computing, 2022, vol. 34, issue 3, 1681-1692

Abstract: A notorious problem in queueing theory is to compute the worst possible performance of the GI/G/1 queue under mean-dispersion constraints for the interarrival- and service-time distributions. We address this extremal queue problem by measuring dispersion in terms of mean absolute deviation (MAD) instead of the more conventional variance, making available methods for distribution-free analysis. Combined with random walk theory, we obtain explicit expressions for the extremal interarrival- and service-time distributions and, hence, the best possible upper bounds for all moments of the waiting time. We also obtain tight lower bounds that, together with the upper bounds, provide robust performance intervals. We show that all bounds are computationally tractable and remain sharp also when the mean and MAD are not known precisely but are estimated based on available data instead. Summary of Contribution: Queueing theory is a classic OR topic with a central role for the GI/G/1 queue. Although this queueing system is conceptually simple, it is notoriously hard to determine the worst-case expected waiting time when only knowing the first two moments of the interarrival- and service-time distributions. In this setting, the exact form of the extremal distribution can only be determined numerically as the solution to a nonconvex nonlinear optimization problem. Our paper demonstrates that using mean absolute deviation (MAD) instead of variance alleviates the computational intractability of the extremal GI/G/1 queue problem, enabling us to state the worst-case distributions explicitly.

Keywords: extremal queue problem; GI/G/1 queue; random walk theory; tight bounds; distribution-free performance analysis (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1130 (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:orijoc:v:34:y:2022:i:3:p:1681-1692

Access Statistics for this article

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