MAD dispersion measure makes extremal queue analysis simple

Research paper by Dick den Hertog, Johan S. H. van Leeuwaarden

Indexed on: 29 Jun '20Published on: 30 Jul '19Published in: arXiv - Mathematics - Probability


A notorious problem in queueing theory is to identify 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 the extremal interarrival time and service time distributions, and hence the best possible upper bounds, on all moments of the waiting time. We also employ DRO techniques to obtain lower bounds and to solve queueing related optimization problems. We leverage the novel DRO-MAD perspective to sketch several extensions and describe now-opened research directions in queueing theory, scheduling and inventory theory.