Scheduling to Differentiate Service in a Multiclass Service System

• 成果类型: Article
• 署名作者: Liu, Yunan; Sun, Xu; Hovey, Kyle
• 署名单位: North Carolina State University; State University System of Florida; University of Florida; United States Department of Defense
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2075
• 发表日期: 2022
• 页码: 527-544
• 关键词: many-server queues; convex delay costs; stabilizing performance; level differentiation; optimality

摘要

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 alpha(i) is an element of (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 wi does not exceed alpha(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.