MAD dispersion measure makes extremal queue analysis simple
From MaRDI portal
Publication:5087732
DOI10.1287/IJOC.2021.1130zbMATH Open1492.90045arXiv1907.13019OpenAlexW2965663106MaRDI QIDQ5087732FDOQ5087732
Authors: Wouter van Eekelen, D. Den Hertog, Johan S. H. van Leeuwaarden 
Publication date: 1 July 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
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 variance, making available recently developed techniques from Distributionally Robust Optimization (DRO). Combined with classical random walk theory, we obtain explicit expressions for the extremal interarrival time and service time distributions, and hence the best possible upper bounds, for all moments of the waiting time. {We also apply the DRO techniques to 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 estimated based on available data instead.
Full work available at URL: https://arxiv.org/abs/1907.13019
Recommendations
- Extremal \(GI/GI/1\) queues given two moments: exploiting Tchebycheff systems
- Applying optimization theory to study extremal \(GI/GI/1\) transient mean waiting times
- On Approximations for Queues, I: Extremal Distributions
- On Approximations for Queues, II: Shape Constraints
- Set-valued performance approximations for the \(GI/GI/K\) queue given partial information
\(GI/G/1\) queuerandom walk theorytight boundsdistribution-free performance analysisextremal queue problem
Cites Work
- Title not available (Why is that?)
- Applied Probability and Queues
- Regret in the Newsvendor Model with Partial Information
- Title not available (Why is that?)
- A Combinatorial Lemma and Its Application to Probability Theory
- Moments of non-negative mass
- Lectures on Stochastic Programming
- On Approximations for Queues, I: Extremal Distributions
- Stochastic convexity and its applications
- Some inequalities for the queue GI/G/1
- Bounds and Asymptotics for Planning Critical Safety Stocks
- Managing Capacity and Inventory Jointly in Manufacturing Systems
- Sharp Bounds on Laplace-Stieltjes Transforms, with Applications to Various Queueing Problems
- A MEAN–VARIANCE BOUND FOR A THREE-PIECE LINEAR FUNCTION
- More bounds on the expectation of a convex function of a random variable
- Robust optimization with ambiguous stochastic constraints under mean and dispersion information
- Novel heavy-traffic regimes for large-scale service systems
- On the heavy-tail behavior of the distributionally robust newsvendor
- Time (in)consistency of multistage distributionally robust inventory models with moment constraints
- Algorithms for the upper bound mean waiting time in the \(\mathrm{GI}/\mathrm{GI}/1\) queue
- Bounds for cumulants of waiting-times in gi/gi/1 queues
- Title not available (Why is that?)
- Convex optimal uncertainty quantification
Cited In (1)
This page was built for publication: MAD dispersion measure makes extremal queue analysis simple
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087732)
