Whittle index aids scheduling with impatient customers and delays
Whittle index approach to multi-server scheduling with convex delay costs and impatient customers
Performance
Summary
Scheduling server tasks is complicated when customers may leave if kept waiting too long. The authors tackle this by applying a mathematical tool called the Whittle index to manage multiple servers with different customer types who have exponential patience. They prove that this method is applicable and provide explicit formulas to help decide which customers to serve first. This helps create efficient scheduling policies when delays cause costs and customers might abandon the queue.
What this means in practice
- •For call center managers: Schedule diverse customer calls on multiple servers while balancing wait times and dropouts using the Whittle index policy.
- •For cloud service operators: Manage task queues with impatient users on cloud servers by prioritizing jobs with the Whittle index derived policy to reduce delay costs.
A theory result. No direct application yet.
Authors
Samuli Aalto
Abstract
We consider the dynamic scheduling problem in a multi-class M/G/N + M queue with convex delay costs and impatient customers that have exponential abandonment times. We apply the Whittle index approach to find a reasonable heuristic solution for this tricky problem. By assuming exponential abandonment times, we are able to make a very straightforward use of the results of the corresponding problem with patient customers presented in Queueing Systems, Vol. 110, Article no. 2, 2026. Our main theoretical achievements are proving that the closed version of the corresponding discrete-time problem is indexable and deriving an explicit expression for the Whittle index. The discrete-time results are utilized to develop the Whittle index policy for the original continuous-time scheduling problem.