Learning to Schedule in Multiclass Many-Server Queues with Abandonment
Yueyang Zhong, John R. Birge, Amy R. Ward
Operations Research · 2025 · Volume 73 · Issue 6
Abstract
The multiclass many-server queue with abandonment (specifically, the multiclass GI / GI / N + GI queue) is a canonical model for service systems. One key operational question is how to schedule; that is, how to choose the customer that a newly available server will serve. The scheduling question is of fundamental importance because scheduling determines which customer classes have more abandonments. However, even though there is much work on scheduling in queueing systems, there is comparatively less work on scheduling in queueing systems when the model primitives (that is, distributional and parameter information regarding the interarrival, service, and patience times) are unknown and may be learned. Our objective is to determine a scheduling policy that minimizes regret, which is the difference in expected abandonment cost between a proposed policy, which does not have knowledge of model primitives, and a benchmark policy, which has full knowledge of model primitives. The difficulty is that the state space is very complex, because in order for the system to be Markovian, we must track (i) the time elapsed since the last arrival for each class, (ii) the amount of time each customer in service has been in service, and (iii) the amount of time each customer in queue has spent waiting. We propose a policy that uses a Learn-then-Schedule (LTS) algorithm that we develop. We analyze the performance of the LTS policy against the benchmark 𝑎 𝜇 a μ -rule (that prioritizes classes for service in accordance with their cost of abandonment times service rate). The algorithm is composed of a learning phase, during which empirical estimates of the service and abandonment rates and their associated abandonment costs are formed, and an exploitation phase, during which an empirical 𝑎 𝜇 a μ -rule based on those estimates is applied. We show that the LTS policy has regret of order l o g 𝑇 log T (where T is the system run-time), which is the smallest order achievable. Funding: This work is supported by the Charles M. Harper Faculty Fellowship at the University of Chicago Booth School of Business. The authors gratefully acknowledge financial support from the University of Chicago Booth School of Business. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0197 .
Keywords
Stochastic Models, Multiclass GI/GI/N+GI queue, scheduling, unknown parameters, regret
Enable JavaScript for citation tools and additional paper interactions.