Ergodic Control of Multiclass Multi-Pool Parallel Server Systems in the Halfin-Whitt Regime

Ari Arapostathis, Guodong Pang

Published 2015-05-16Version 1

We consider Markovian multiclass multi-pool networks with heterogeneous server pools, each consisting of many statistically identical parallel servers, where the bipartite graph of customer classes and server pools forms a tree. Customers form their own queue and are served in the FCFS discipline, and can abandon while waiting in queue. Service rates are both class and pool dependent. The objective is to study the scheduling and routing control under the long run average (ergodic) cost criteria in the Halfin-Whitt regime, where the arrival rates of each class and the numbers of servers in each pool grow to infinity appropriately such that the system becomes critically loaded while service and abandonment rates are fixed. Two formulations of ergodic control problems are considered: (i) both queueing and idleness costs are minimized, and (ii) only the queueing cost is minimized while a constraint is imposed upon the idleness of all server pools. We consider admissible controls in the class of preemptive control policies. These problems are solved via the corresponding ergodic control problems for the limiting diffusion. For that, we first develop a recursive leaf elimination algorithm and obtain an explicit representation of the drift for the controlled diffusions. Moreover, we show that, for the limiting controlled diffusion of any such Markovian network in the Halfin-Whitt regime, there exists a stationary Markov control under which the diffusion process is geometrically ergodic, and its invariant probability distribution has all moments finite. The optimal solutions of the constrained and unconstrained problems are characterized via the associated HJB equations. Asymptotic optimality results are also established.