Fluid Models for Overloaded Multiclass Many-Server Queueing Systems with First-Come, First-Served Routing

Abstract

Motivated by models of tenant assignment in public housing, we study approximating deterministic fluid models for overloaded queueing systems having multiple customer classes (classes of tenants) and multiple service pools (housing authorities), each with many servers (housing units). Customer abandonment acts to keep the system stable, yielding a proper steady-state description. Motivated by fairness considerations, we assume that customers are selected for service by newly available servers on a first-come, first-served (FCFS) basis from all classes the corresponding service pools are allowed to serve. In this context, it is challenging to determine stationary routing flow rates between customer classes and service pools. Given those routing flow rates, each single fluid queue can be analyzed separately using previously established methods. Our ability to determine the routing flow rates depends on the structure of the network routing graph. We obtain the desired routing flow rates in three cases: when the routing graph is (i) a tree (sparsely connected), (ii) complete bipartite (fully connected), and (iii) an appropriate combination of the previous two cases. Other cases remain unsolved. In the last two solved cases, the routing flow rates are actually not uniquely determined by the fluid model, but become so once we make stochastic assumptions about the queueing models that the fluid model approximates.