Control of systems with flexible multi-server pools: a shadow routing approach (Q993482)

A general model with multiple customer classes and several flexible multi-server pools is considered. The paper proposes a robust, generic scheme for routing new arrivals, which optimally balances server pools' loads, without the knowledge of the flow input rates and without solving any optimization problem. The scheme is based on Shadow routing in a virtual queueing system. The behavior of our scheme in Halfin-Whitt (or, QED) asymptotic regime is studied, when server pool sizes and the input rates are scaled up simultaneously by a factor \(r\) growing to infinity, while keeping the system load within \(O(\sqrt{r})\) of its capacity. The main results of the paper are as follows. (i) It is shown that, in general, the system operating in stationary regime has at least \(O(\sqrt{r})\) queue-length in average, even if the so-called null-controllability [see \textit{R. Atar, A. Mandelbaum, G. Shaikhet}, Ann. Appl. Probab. 16, 1764-1804 (2006; Zbl 1121.60092)] on a finite time interval is possible; strategies achieving this \(O(\sqrt{r})\) growth rate we call order-optimal. (ii) It is shown that some natural algorithms, such as MaxWeight, that guarantee stability, are not order optimal. (iii) Under the concrete resource pooling condition, the diffusion limit of the arrival process into server pools is established, under the Shadow routing. (It is conjectured in the paper that result of (iii) leads to order optimality of the Shadow routing algorithm.) Simulation results demonstrated good performance and robustness.