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.
Mots clés : workforce scheduling, schedule generation scheme, roadef challenge
@article{RO_2009__43_4_375_0,
author = {Pokutta, Sebastian and Stauffer, Gautier},
title = {France {Telecom} workforce scheduling problem : a challenge},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {375--386},
publisher = {EDP-Sciences},
volume = {43},
number = {4},
year = {2009},
doi = {10.1051/ro/2009025},
zbl = {1173.90410},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2009025/}
}
TY - JOUR AU - Pokutta, Sebastian AU - Stauffer, Gautier TI - France Telecom workforce scheduling problem : a challenge JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2009 SP - 375 EP - 386 VL - 43 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2009025/ DO - 10.1051/ro/2009025 LA - en ID - RO_2009__43_4_375_0 ER -
%0 Journal Article %A Pokutta, Sebastian %A Stauffer, Gautier %T France Telecom workforce scheduling problem : a challenge %J RAIRO - Operations Research - Recherche Opérationnelle %D 2009 %P 375-386 %V 43 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2009025/ %R 10.1051/ro/2009025 %G en %F RO_2009__43_4_375_0
Pokutta, Sebastian; Stauffer, Gautier. France Telecom workforce scheduling problem : a challenge. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 375-386. doi : 10.1051/ro/2009025. http://archive.numdam.org/articles/10.1051/ro/2009025/
[1] , Workforce allocation in cyclical scheduling problems: a survey. Oper. Res. Q. 27 (1976) 155-167.
[2] Boost-Library Team, The Boost C++ libraries. http://www.boost.org/ (2006).
[3] , C++ Mersenne Twister pseudo-random number generator, http://www.bedaux.net/mtrand/ (2006).
[4] , and , Technicians and interventions scheduling for telecommunications. http://www.g-scop.inpg.fr/ChallengeROADEF2007/en/sujet/sujet2.pdf (2006).
[5] , Incorporating the strength of MIP modeling in Schedule construction. http://www.g-scop.inpg.fr/ChallengeROADEF2007/TEAMS/roadef28/abstract_roadef28.pdf (2007).
[6] ILOG Inc., CPLEX Solver. http://www.ilog.com (2006).
[7] and , Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127 (2000) 394-407. | Zbl
[8] and , Experimental investigations of heuristics for resource-constrained project scheduling: an update. Eur. J. Oper. Res. 174 (2006) 23-37. | Zbl
[9] , Pólya Urn Models. Taylor & Francis Group LLC - CRC Press (2008). | Zbl
[10] , and , Ant colony optimization for resource-constrained project-scheduling, IEEE Trans. Evol. Comput. 6 (2002) 333-346.
[11] http://www.g-scop.inpg.fr/ChallengeROADEF2007/
[12] and , Fast local search and guided local search and their application to British Telecom's workforce scheduling problem. Technical Report CSM-246, Department of Computer Science, University of Essex, UK (1995). | Zbl
Cité par Sources :
