Transitory Queueing Models and Optimal Scheduling

We present an introduction to the theory of transitory queueing systems, where a finite number of jobs apply for service. We will first focus on the $\Delta_{(i)}/GI/1$ queue, developing fluid and diffusion approximations to the queue length and workload performance metrics in a novel large population scale (called `population acceleration'). In particular, we show that the diffusion approximation to the queue length process is a diffusion reflected through the directional derivative of the Skorokhod reflection regulator. Next, using this theory, we study the classic problem of optimally scheduling patients at an outpatient clinic over a finite horizon. Our objective is to simultaneously minimize the waiting time for each patient and the `overage' time. We show that in the fluid limit, the optimal schedule, that minimizes the objective, matches the service process implying that heavy-traffic emerges as a consequence of optimization. On the other hand we solve the diffusion scale problem through a receding horizon approximation, and prove the large population asymptotic optimality of a corresponding stationary solution.

Harsha Honnappa is an Assistant Professor in the School of Industrial Engineering at Purdue University. His research interests are in applied probability and stochastic networks. He received his Ph.D. from the University of Southern California in Electrical Engineering, where he was a Ming Hsieh Scholar. He is also the recipient of the 2016 Lajos Takacs award for outstanding Ph.D. thesis on Queueing Theory and its Applications, "for the introduction and analysis of transitory queueing models, using an impressive range of analytic techniques." His research is supported by the National Science Foundation and the Purdue Research Foundation.