Fair Dynamic Routing in Large-Scale Heterogeneous-Server Systems

In a call center, there is a natural trade-off between minimizing customer wait time and fairly dividing the workload among agents of different skill levels. The relevant control is the routing policy, that is, the decision concerning which agent should handle an arriving call when more than one agent is available. We formulate an optimization problem for a call center with heterogeneous agent pools, in which each pool is distinguished by the speed at which agents in that pool handle calls. The objective is to minimize steady-state expected customer wait time subject to a "fairness" constraint on the workload division. We first solve the optimization problem by formulating it as a Markov decision process (MDP), and solving, a related linear program. We note that this approach does not in general lead to an optimal policy that has a simple structure. Fortunately, the optimal policy does appear to have a simple structure as the system size grows large, in the Halfin-Whitt many-server heavy-traffic limit regime. Therefore, we solve the diffusion control problem that arises in this regime and interpret its solution as a policy for the original system. The resulting routing policy is a threshold policy that determines server pool priorities based on the total number of customers in the system. We prove that a continuous modification of our proposed threshold routing policy is asymptotically optimal in the Halfin-Whitt limit regime. We furthermore present simulation results to illustrate that our proposed threshold routing policy outperforms a common routing policy used in call centers (that routes to the agent that has been idle the longest).