Learning to Schedule in Multiclass Many-Server Queues with Abandonment

How to Learn Which Customer Class to Serve Next?

In “Learning to Schedule in Multiclass Many-Server Queues with Abandonment”, Zhong, Birge, and Ward tackle the challenge of scheduling (that is, how to choose the customer that a newly available server will serve) in a multiclass many-server queueing system where customers may abandon the queue. The goal is to develop a scheduling policy that performs nearly as well as a benchmark policy under full knowledge of the model primitives despite these primitives being unknown and needing to be learned. They propose a Learn-then-Schedule policy that first estimates the unknown model primitives empirically and then schedules according to the benchmark policy structure using these estimates. Such a policy achieves an optimal regret rate of order logT (where T is the system time), meaning that the performance gap between the proposed policy and the benchmark policy grows logarithmically over time.