Scheduling to Differentiate Service in a Multiclass Service System

Motivated by large-scale service systems, we study a multiclass queueing system having class-dependent service rates and heterogeneous abandonment distributions. Our objective is to devise proper staffing and scheduling schemes to achieve differentiated services for each class. Formally, for a class-specific delay target w i > 0 and threshold α i ∈ ( 0,1 ) , we concurrently determine an appropriate staffing level (number of servers) and a server-assignment rule (assigning newly idle servers to a waiting customer from one of the classes), under which the percentage of class- i customers waiting more than w i does not exceed α i . We tackle the problem under the efficiency-driven many-server heavy-traffic limiting regime, where both the demand volume and the number of servers grow proportionally to infinity. Our main findings are as follows: (a) class-level service differentiation is obtained by using a delay-based dynamic prioritization scheme; (b) the proposed scheduling rule achieves an important state-space collapse, in which all waiting time processes evolve as fixed proportions of a one-dimensional state-descriptor called the frontier process ; (c) the frontier process solves a stochastic Volterra equation and is thus a non-Markovian process; (d) the proposed staffing-and-scheduling solution can be readily extended to time-varying settings. In this paper, we establish heavy-traffic limit theorems to show that our solution is asymptotically correct for large systems, and we numerically demonstrate that it performs reasonably well even for relatively small systems.