France Telecom workforce scheduling problem: a challenge

¹ Operations Research Center, MIT, 77 Massachusetts Avenue, Cambridge, MA 02139, USA; pokutta@mit.edu
² IBM Zurich Research Lab, Säumerstrasse 4, 8803 Rüschlikon, Switzerland; gst@zurich.ibm.com

Received: 8 June 2007
Accepted: 18 June 2009

Abstract

In this paper, we describe the methodology used to tackle France Telecom workforce scheduling problem (the subject of the Roadef Challenge 2007) and we report the results obtained on the different data sets provided for the competition. Since the problem at hand appears to be NP-hard and due to the high dimensions of the instance sets, we use a two-step heuristical approach. We first devise a problem-tailored heuristic that provides good feasible solutions and then we use a meta-heuristic scheme to improve the current results. The tailored heuristic makes use of sophisticated integer programming models and the corresponding sub-problems are solved using CPLEX while the meta-heuristic framework is a randomized local search algorithm. The approach herein described allowed us to rank 5th in this challenge.