SIAM News Blog
SIAM News
Print

Oscillating Wait Times and Queues with Information Updates

By Paul Davis

Murphy’s Law—the idea that anything that can go wrong will go wrong—seems especially relevant when picking a waiting line. No matter how reliable your information, you inevitably end up in the longer queue. The supposedly quicker route recommended at the highway rest area resembles a parking lot by the time you arrive. The emergency room wait time that you verified on your phone before driving across town to the allegedly deserted location? Standing room only upon arrival (see Figure 1). And the phone app at Disneyland promising a much shorter queue for a ride just a few steps away? It outsmarts you every time (see Figure 2).

Figure 1. Public posting of the wait time at an emergency room. Is this information old enough to trigger oscillations via Hopf bifurcation? Image courtesy of [1].
Jamol Pender of Cornell University blamed Hopf bifurcation, not Murphy’s Law, for fluctuating wait times when he spoke during a minisymposium at the 2019 SIAM Conference on Computational Science and Engineering (CSE19), held in Spokane, Wash., earlier this year. His model shows that the technological blessing of posting nearly up-to-date queue lengths can incur the curse of large variations in those lengths if the associated information is a bit too old.

Oscillations induced by dated information are much more than simple irritations when they affect access to critical services like an emergency room. Pender’s conclusion that the oscillations arise as a Hopf bifurcation points to a clear fix — estimates of queue lengths have a predictable shelf life. Exceed that shelf life and queue lengths begin to oscillate.

Pender formulated a stochastic queuing model that updates at fixed time intervals the wait times for each of two queues. The simplest version updates just once at each time step. His key analytic move is a clever continuum approximation of the initial time series formulation. Pender asked his audience to imagine the arriving customers as “droplets merging into a stream flowing out of a bathtub spout.” He then derived the limiting continuum model by scaling both the queuing process and the arrival rate by the number of droplets.

Figure 2. Wait times on the Disneyland Park app. Image courtesy of [1].
The resulting functional differential equation does indeed display a Hopf bifurcation if the information delay is too long, i.e., if the scaled information delay parameter is too large. One can explicitly calculate the critical value. Comparing discrete computational simulations of the oscillations in queue length with the continuum model’s predicted oscillations indicates good agreement, even with a modest population of 100.

Having constructed a breakthrough model that reliably captures the effects of information delay on queue length, Pender and his team are now exploring that rich lode for additional insights into these behaviors. Does the oscillatory performance change significantly if queue lengths are updated several times per time step, rather than just once? Roughly, no. Hopf bifurcation still yields disruptive oscillations in queue lengths. The bifurcation parameter’s critical value—now the root of a higher-order polynomial—is simply harder to calculate. But what if arrival rates vary with time? Or information about a queue’s length and velocity is accessible? Answers and yet more questions are available in Pender’s original paper [1] and his subsequent publications.

Pender’s presentation took place during a minisymposium entitled “Exciting Work by Early Career Underrepresented Minority Researchers,” part of the SIAM Workshop Celebrating Diversity. He also contributed to a fruitful panel discussion at CSE19 that addressed “Strategies for Promoting Diversity and Inclusion within our Profession,” organized and moderated by SIAM President Lisa Fauci.


References
[1] Pender, J., Rand, R.H., & Wesson, E. (2017). Queues with Choice via Delay Differential Equations. Int. J. Bifur. Chaos, 27(4), 1730016.

Paul Davis is professor emeritus of mathematical sciences at Worcester Polytechnic Institute.

blog comments powered by Disqus