Prof. David Goldberg
Assistant Professor, Georgia Tech
Talk:
Simple and explicit bounds for multi-server queues with universal 1/(1 - rho) (and better) scaling
Abstract:
The First-Come-First-Serve multi-server queue is a fundamental building block of many models in operations management and operations research. In 1962, John Kingman proved a simple and explicit bound for the steady-state number of jobs waiting in queue in the special case when there is only one server. His now famous bound is a simple function of a few moments of the inter-arrival and service distributions, and scales like 1/(1 - rho) as the traffic intensity rho approaches 1. The existence of an equally simple, explicit, and general bound for the multi-server setting which similarly scales as 1/(1 - rho) has been an open question for over fifty years. In this talk, we answer this question affirmatively, proving the first multi-server analogue of Kingman's bound. Our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay, where the strength of our bounds (e.g. in the form of tail decay rate) is a function of how many moments of the inter-arrival and service distributions are assumed finite. Our simple and explicit bounds scale gracefully even when the number of servers grows large and the traffic intensity converges to one simultaneously, as in the Halfin-Whitt scaling regime, which is popular in the analysis of service systems. We will also discuss applications of our results to several operational problems which arise in that setting.
Biography:
David Goldberg is the A. Russell Chandler III Assistant Professor in the Stewart School of Industrial & Systems Engineering at Georgia Tech. Dr. Goldberg works in applied probability, interpreted broadly, on topics ranging from inventory control and queueing theory to distributionally robust and combinatorial optimization. Much of his work focuses on using ideas from probability theory to prove that highdimensional complex systems can be well-approximated by much simpler systems, and using these insights to devise novel algorithms with provable performance guarantees. He has received several honors for his work, including an NSF CAREER award, first place in the 2015 George Nicholson Student Paper Competition, second place in the 2015 JFIG Paper Competition, as well as finalist in the 2014 MSOM Student Paper Competition and 2010 George Nicholson Student Paper Competition.Dr. Goldberg received his undergraduate degree in computer science at Columbia University, minoring in both industrial engineering/operations research and applied math. He completed his Ph.D. at the MIT Operations Research Center. He is a member of INFORMS.
