2019 TutORial: Scheduling An Overloaded Multiclass Queue With Impatient Customers

Given by Amy Ward at the 2019 INFORMS Annual Meeting in Seattle, WA.

We describe a fluid model with time-varying input that approximates a multiclass many-server queue with time-varying arrivals (specifically, the multiclass G/GI/N +GI queue). We show how to use the restricted fluid model with constant input rate to approximately solve scheduling control problems for a queue with constant arrival rate.

The key is to characterize the invariant states of the fluid model, because they typically provide an approximation to the mean steady-state behavior of the queue under a wide range of scheduling policies.

The resulting fluid control problem motivates using a static priority scheduling policy when the objective is to minimize the long run average abandonment rate, but may motivate a different class of scheduling policies when there are also holding costs. We end by discussing several open problems.