Anatolii A. Puhalskii

Past Awards

Best Publication Award: First Place
  • "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