Ph.D. dissertation

Optimisation des horaires des agents et du routage des appels dans les centres d’appels

(Translation: Agent scheduling and call routing optimization for call centers)


We study the management of multi-skill call centers, with multiple call types and agent groups. A call center is a very complex queueing system, and we generally need to use simulation in order to evaluate its performances.

First, we develop a call center simulator based on the simulation of a continuous-time Markov chain (CTMC) that is faster than traditional discrete-event simulation. Using an uniformization method, this simulator simulates the embedded discrete-time Markov chain of the CTMC. We propose strategies to use this simulator efficiently within a staffing optimization algorithm. In particular, we study the use of common random numbers.

Secondly, we propose an algorithm, based on subgradient cuts and simulation, to optimize the shift scheduling problem. Since this problem is usually too big to be solved as an integer programming problem, we relax the integer variables and we propose methods to round the solutions. We also present a local search to improve the final solution.

Next, we study the call routing optimization problem. We propose a new routing policy based on weights, call waiting times, and agent idle times or the number of idle agents. We develop a modified genetic algorithm to optimize all the routing parameters. Instead of doing mutations and crossovers, this algorithm refines the parametric distributions used to generate the population of solutions.

We also develop a staffing algorithm based on aggregation, queueing theory and delay probability. This heuristic algorithm is fast, because it does not use simulation. The service level constraint is converted into a delay probability constraint. Moreover, we propose a variant of a CTMC model based on the waiting time of the customer at the head of the queue. Finally, we design an extension of a cutting-plane algorithm to optimize the stochastic version with recourse of the staffing problem for multi-skill call centers.

Keywords: contact center, stochastic optimization, staffing, scheduling, work shift, heuristic, Markov chain, simulation.

pdf icon Download the dissertation (written in French)

Back to previous page