Instability of natural load balancing in large-scale flexible-server systems

We consider large-scale service systems with several customer classes and several server pools. Mean service time of a customer depends both on the customer class and the server type. The routing is restricted to a fixed set of "activities," i.e. (customer-class, server-type) pairs. We assume that the bipartite graph with vertices being customer-classes and server-types, and edges being the activities, is a tree. The system behavior under a natural load balancing routing/scheduling rule, Longest-queue freest-server (LQFS-LB), is studied in both fluid-limit and Halfin-Whitt asymptotic regimes. We show that, quite surprizingly, LQFS-LB may render the system unstable in the vicinity of the equilibrium point. Such instability cannot occur in systems with "small" number of customer classes. We prove stability in one important special case.