MAD dispersion measure makes extremal queue analysis simple

DOI10.1287/IJOC.2021.1130MaRDI QIDQ5087732zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1907.13019

zbMATH Keywords

\(GI/G/1\) queuerandom walk theorytight boundsdistribution-free performance analysisextremal queue problem

Mathematics Subject Classification ID

Queues and service in operations research (90B22)

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.

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

Cites work

• scientific article; zbMATH DE number 3755546 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3350905 (Why is no real title available?)
• A Combinatorial Lemma and Its Application to Probability Theory
• A MEAN–VARIANCE BOUND FOR A THREE-PIECE LINEAR FUNCTION
• Algorithms for the upper bound mean waiting time in the \(\mathrm{GI}/\mathrm{GI}/1\) queue
• Applied Probability and Queues
• Bounds and Asymptotics for Planning Critical Safety Stocks
• Bounds for cumulants of waiting-times in gi/gi/1 queues
• Convex optimal uncertainty quantification
• Lectures on Stochastic Programming
• Managing Capacity and Inventory Jointly in Manufacturing Systems
• Moments of non-negative mass
• More bounds on the expectation of a convex function of a random variable
• Novel heavy-traffic regimes for large-scale service systems
• On Approximations for Queues, I: Extremal Distributions
• On the heavy-tail behavior of the distributionally robust newsvendor
• Regret in the Newsvendor Model with Partial Information
• Robust optimization with ambiguous stochastic constraints under mean and dispersion information
• Sharp Bounds on Laplace-Stieltjes Transforms, with Applications to Various Queueing Problems
• Some inequalities for the queue GI/G/1
• Stochastic convexity and its applications
• Time (in)consistency of multistage distributionally robust inventory models with moment constraints

Cited in

(1)

• Distributionally robust views on extremal queues

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)