Past Awards
The award recognizes seminal research contributions that Marty Reiman and Ruth Williams have made, over the past several decades, to the theory and applications of “stochastic networks/systems” and their “heavy traffic approximations.” These profound contributions have been and have further led to breakthroughs in stochastic operations research in general, and queueing theory in particular. Their analysis of complex stochastic networks under conditions of heavy traffic, has not only led to the discovery and rigorous articulations of properties of the networks, and penetrating insights into the operational laws of real-world systems they model, but also led to deep theoretical developments in the study of reflected diffusions.
Starting with his Ph.D. thesis, Marty Reiman has had a lasting impact on the heavy traffic analysis of queueing systems. In it, he identified and characterized the diffusion limit of a generalized Jackson queueing network in heavy traffic. Specifically, this limit is a reflected Brownian motion (RBM) in the non-negative orthant, namely a multi-dimensional Brownian motion restricted to the non-negative orthant by oblique reflection at the orthant’s boundary. In companion and subsequent works, Reiman enunciated two heavy-traffic principles that rank among the most important and elegant contributions of heavy traffic theory: the snapshot principle, which relates waiting- and sojourn-times processes to queue-lengths, and the phenomenon of state-space collapse, that is, dimensionality reduction in the effective descriptions of the evolution of a stochastic system in heavy traffic.
Reiman’s research is characterized by deep intuition and penetrating understanding of the physical and mathematical laws that govern the systems that he studies. These virtues are clearly manifested in the following illustrative examples: the averaging principle for polling systems, jointly with Coffman and Puhalskii; the interpolation approximation, with Simon, that combines their light-traffic and the familiar heavy-traffic viewpoints; the study, motivated by call centers, of operational regimes (efficiency-driven, quality-driven and their balancing QED, namely, quality-and-efficiency driven) in many-server queueing models with abandoning customers (with Garnett and Mandelbaum); asymptotically optimal staffing of many-server queues (with Borst and Mandelbaum), e.g., square-root staffing in the Halfin-Whitt (QED) regime; the analysis in the latter regime, with Puhalskii, of the multiclass queue with phase-type service-times and static-priorities; the constant-order policy in lost-sales inventory systems with long lead times; and, jointly with Wang, his analysis of certainty equivalent control for network revenue management.
In Reiman’s work, one sees real inventiveness combined with strong mathematical and expository skills, supported by a solid command of several distinct application domains. His research has influenced and inspired work by the very best people in stochastic OR, including several previous winners of the von Neumann Theory Prize.
Ruth Williams has also had a deep and lasting impact on the study of heavy traffic analysis. This started with her PhD thesis and further work on RBM in a wedge, establishing semimartingale, local time, excursion and recurrence properties. It continued with her establishing a multidimensional generalization that identified necessary and sufficient conditions for weak existence and uniqueness in law of RBMs in the nonnegative orthant, which provides an alternative to the pathwise theory of Harrison and Reiman; and it culminated in the development of invariance principles (analogous to the Donsker-Varadhan invariance principle for the classical (unreflected) Brownian motion). This enabled the identification and verification of diffusion approximations, for multiclass queueing networks under certain state-space collapse conditions.
The above research provided the foundations for subsequent significant research, by Williams and others. One example is queues operating under a processor-sharing service discipline. Jointly, first with Gromoll and Puha and later with Puha and Stolyar, Williams described the evolution of such systems by a measure-valued process that keeps track of the residual service times of all jobs. Another example is asymptotically optimal control of parallel-server systems in heavy-traffic, first under complete resource pooling (with Bell) and recently under partial pooling (with Pesic); further examples include applications, with Kelly, to the analysis of a controlled motorway in heavy traffic; and, with Kang, Lee and Kelly and later with Gromoll, to bandwidth sharing networks that model congestion of data on the internet. For the latter, Williams established fluid limits and subsequently discovered that networks with proportional fairness admit a product-form (and hence tractable) stationary distribution in heavy traffic.
Williams’ research is characterized by its mathematical depth and elegance. She has greatly influenced researchers in operations research, stochastic processes and mathematics, doing so through survey lectures and articles that are exemplary in clarity and insight. Her expositions have introduced the field to researchers and described challenging open problems and directions, which have spurred further research.
In summary, Reiman and Williams have carried out pioneering research over the past several decades. This has led to fundamental breakthroughs in stochastic operations research in general, and queueing theory in particular, with a focus on stochastic networks and their behavior under heavy-traffic conditions. Their research, in which they have both influenced and built upon each other’s work, has had a lasting theoretical and practical impact that stands the test of time.
- "Papers on A Heavy Traffic Averaging Principle for Polling Systems," Annals of Applied Probability 5: 681-719, 1995 and Mathematics of Operations Research 23: 257-304, 1998.
Polling systems are prototypical queueing models that have applications in computer, communications, manufacturing and traffic flow systems. While simple to describe, these models are difficult to analyze, and steady-state distributions typically require numerically solving a system of equations. For exhaustive polling in the presence of setup costs or setup times, the authors show that in the time scale of the diffusion process limit for the total unfinished work, the individual queue lengths change at an infinite rate. The proof of the resulting averaging principle employs a clever construction of an associated threshold queue. The Bessel process limit for the total workload leads to an explicit steady-state distribution for the waiting time in the presence of setup times. This work provides the basis for a tractable approach to the optimal control of polling systems, a problem which has long resisted analysis by standard techniques. These breakthrough results will profoundly impact research on polling systems and heavy traffic theory for years to come.
Lawrence M. Wein, Chair
Richard R. Weber
Ward Whitt