Scheduling parallel servers in the nondegenerate slowdown diffusion regime: asymptotic optimality results (Q2448695)

This paper presents an analysis of the minimization of queue-length costs in a system with heterogeneous parallel servers under heavy traffic regime with renewal arrival processes and exponential service times, operating in a non-degenerate slowdown (NDS) diffusion. It is indicated that the many-server with heavy traffic regime is distinct from the well-studied heavy traffic diffusion regimes, namely, the single server conventional regime and the many-server Halfin-Whitt regime, in which the service time is inconsiderable in comparison to the waiting time. The latter can be used in the modelling of large-scale service systems, such as some call centers, certain health-care systems, etc. Moreover, the presented queue-length problem can also be used to analyze the sojourn time problem in the system with parallel servers. The paper provides a formulation and solution of the underlying Brownian control problem (BCP) for the parallel server model as the basis for constructing asymptotically optimal policies for the queueing model. The first main result of the paper indicates that the BCP problem, which describes the asymptotics for the studied system, constitutes an asymptotic lower bound on the cost under any sequence of policies. The second main result is that this lower bound is tight. This can be proved by constructing a sequence of policies that asymptotically achieve the bound.