Dynamic Scheduling of a Parallel-Server Queueing System: A Computational Method for High-Dimensional Problems
For operations managers of large call centers, this provides a scalable solution to a computationally intractable dynamic scheduling problem.
The paper develops a computational method for skill-based routing in large call centers with many customer classes, using a diffusion approximation and deep neural networks. The method scales to 100+ customer classes and outperforms benchmark policies on realistic test instances.
A key operational challenge for call centers is to decide, in real time, which waiting customer should be served by which available agent. This is known as skill-based routing, and the decision becomes especially difficult in large systems with many customer classes, where standard dynamic programming methods can be computationally intractable. Focusing on the Halfin-Whitt heavy-traffic regime and an infinite-horizon discounted cost criterion, we develop a computational method that scales to high-dimensional settings with many customer classes. Our approach begins by deriving an approximating diffusion control problem in the heavy traffic limiting regime. Building on earlier work by Han et al. (2018), we develop a simulation-based method to solve this problem, relying heavily on deep neural network techniques. Using this framework, we construct a policy for the original (prelimit) call center scheduling problem. To evaluate performance, we adopt a data-driven approach. Using call center data from a large U.S. bank, we calibrate the model and construct realistic test instances. We then compare the resulting policy with benchmark policies drawn from the literature. Across all test problems considered so far, our policy performs at least as well as or better than the best benchmark identified. Moreover, the method remains computationally feasible in dimensions up to 100, corresponding to call centers with 100 or more distinct customer classes.