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 ξ-choice (abbreviated as LB(ξ,c,d)), that are suitable for dynamic routing with partial state information. Under the proposed policy, upon an arrival, a subset of ξ stations will be randomly collected, with their state information being retrieved, where ξ is a positive integer-valued random variable satisfying P{ξ≥2}>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. The parameters c and d are employed to control the relative expected delay and utilization levels across stations. Using asymptotic analysis, we derive diffusion limits of queue-length processes as well as their stationary distributions under the LB(ξ,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(ξ,c,d) policies with other routing policies.