Balanced Routing with Partial Information in a Distributed Parallel Many-Server Queueing System

We consider a queueing system that is comprised of multiple stations serving a single class of customers. Each station consists of many statistically identical servers, and has its own dedicated queue. In this paper, we propose a family of generalized load-balancing routing policies parameterized by vectors c and d with \xi-choice (abbreviated as LB(\xi; c; d)), that are suitable for dynamic routing with partial state information. Under the proposed policy, upon an arrival, a subset of \xi stations will be randomly collected, with their state information being retrieved, where \xi is a positive integer-valued random variable satisfying P(\xi > 1) > 0; then, this new customer will be routed to: (i) the station with minimum expected delay modified by c when all the collected stations are fully occupied; or otherwise (ii) the station with maximum idleness ratio modified by d among the collected stations with idle servers. Using asymptotic analysis, we derive diffusion limits of queue-length processes as well as their stationary distributions under the LB(xi; c; d) policy in the Halfin-Whitt regime. Based on these stationary diffusion limit results, we develop a solution procedure to determine policy parameters under different optimization criteria. Finally, we provide numerical experiments to validate the accuracy of our diffusion approximation, and compare the performances under the LB(\xi; c; d) policies with other routing policies