Description:

Yunana Liu

North Carolina State University

Title: Optimal Routing to Remote Queues

Abstract:
We develop optimal routing policies for remote queueing systems, in which each arrival, after being routed to join one of several single-server queues in parallel, will experience a pre-arrival delay. Motivated by service systems in which system state (e.g., queue length and waiting time) is available for routing decisions, we intend to use pre-arrival delays to model commute times of arrivals, such as patients’ transportation times before arriving at clinics and data packets’ transmission times to web servers. For parallel queues with no pre-arrival delays, it is well known that the join-the-shortest queue (JSQ) routing policy is asymptotically optimal in minimizing the total queue length and in-queue waiting time. In addition, under JSQ the performance of the parallel system with no pre-arrival delays is asymptotically equivalent to the pooled system in heavy traffic. In the presence of pre-arrival delays, unfortunately, JSQ can be disastrous for the system performance, causing excessively large in-queue waiting time and an undesired bouncing effect (having negatively correlated queue performance). In order to reduce the waiting time and to minimize the total queue length, we propose a new state-dependent probabilistic routing policy, named JSQ with a root-excess bias (JSQ-REB). Specifically, JSQ-REB means that we route a customer to the shortest queue with a slight bias that is proportional to the square root of the fraction of idleness (i.e., one minus the traffic intensity). We prove a heavy-traffic limit theorem by showing that, under the proposed JSQ-REB policy, the parallel system is asymptotically equivalent to the pooled system as the traffic intensity approaches one, so that both the waiting time and total queue length are minimized, and the excessive congestion caused by pre-arrival delays is eliminated.

Mini-bio:
Yunan Liu is an assistant professor at the Industrial and Systems Engineering Department and an associate faculty member of the Operations Research Center of North Carolina State University. His research interests include queueing theory, stochastic modeling, applied probability, simulation, and their applications in service systems including call centers, healthcare, and manufacturing systems. He received his M.S. and Ph.D. in Operations Research from Columbia University and B.S. in Electrical Engineering from Tsinghua University.