This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Atar, R. Articles by Shaikhet, G.

Simplified Control Problems for Multiclass Many-Server Queueing Systems

Department of Electrical Engineering, Technion–Israel Institute of Technology, Haifa 32000, Israel
Department of Industrial Engineering and Management, Technion–Israel Institute of Technology, Haifa 32000, Israel
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
atar{at}ee.technion.ac.il
avim{at}tx.technion.ac.il
shaikhet{at}cmu.edu

We consider scheduling and routing control problems for queueing models with I customer classes and J server pools, each consisting of many statistically identical, exponential servers. Customers require a single service that can be performed by a server from one of the pools; the service rate is µ_ij 0, which depends on the customer's class i and the server's pool j, and customers can abandon the system while waiting to be served. In the heavy traffic regime of Halfin and Whitt, these problems are formally equivalent to I-dimensional diffusion control problems. We analyze the diffusion control problems is two special cases. First, when the service rates depend only on the pool (µ_ij = µ_j), the diffusion control problem is shown to be similar to (but distinct from) the diffusion control problem for a single class model, which greatly reduces the complexity of the problem. Second, when the service rates depend only on the class (µ_ij = µ_i), the diffusion control problem is shown to be equivalent to a diffusion control problem for a single pool model, a problem that has previously been studied. In the first case, we also establish a rigorous relation between the queueing control problem and the diffusion control problem, showing that a policy for the queueing model, based on an ordinary differential equation of Hamilton-Jacobi-Bellman type, is asymptotically optimal.

Key Words: many-server queueing systems; Halfin-Whitt; QED regime; heavy traffic; scheduling and routing; skills-based routing; diffusion models; stochastic control; asymptotic optimality
History: Received: May 5, 2008; revision received: December 30, 2008;