France Telecom workforce scheduling problem: a challenge

Sebastian Pokutta; Gautier Stauffer

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 4, page 375-386
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Pokutta, Sebastian, and Stauffer, Gautier. "France Telecom workforce scheduling problem: a challenge." RAIRO - Operations Research 43.4 (2009): 375-386. <http://eudml.org/doc/250548>.

@article{Pokutta2009,
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. },
author = {Pokutta, Sebastian, Stauffer, Gautier},
journal = {RAIRO - Operations Research},
keywords = {Workforce scheduling; schedule generation scheme; roadef challenge.; workforce scheduling; roadef challenge},
language = {eng},
month = {10},
number = {4},
pages = {375-386},
publisher = {EDP Sciences},
title = {France Telecom workforce scheduling problem: a challenge},
url = {http://eudml.org/doc/250548},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Pokutta, Sebastian
AU - Stauffer, Gautier
TI - France Telecom workforce scheduling problem: a challenge
JO - RAIRO - Operations Research
DA - 2009/10//
PB - EDP Sciences
VL - 43
IS - 4
SP - 375
EP - 386
AB - 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.
LA - eng
KW - Workforce scheduling; schedule generation scheme; roadef challenge.; workforce scheduling; roadef challenge
UR - http://eudml.org/doc/250548
ER -

References

top
  1. K.R. Baker, Workforce allocation in cyclical scheduling problems: a survey. Oper. Res. Q.27 (1976) 155–167.  
  2. Boost-Library Team, The Boost C++ libraries. (2006).  URIhttp://www.boost.org/
  3. J. Bedaux, C++ Mersenne Twister pseudo-random number generator, (2006).  URIhttp://www.bedaux.net/mtrand/
  4. P.-F. Dutot, A. Laugier and A.-M. Bustos, Technicians and interventions scheduling for telecommunications. (2006).  URIhttp://www.g-scop.inpg.fr/ChallengeROADEF2007/en/sujet/sujet2.pdf
  5. C. Hurkens, Incorporating the strength of MIP modeling in Schedule construction. (2007).  URIhttp://www.g-scop.inpg.fr/ChallengeROADEF2007/TEAMS/roadef28/abstract_roadef28.pdf
  6. ILOG Inc., CPLEX Solver. (2006).  URIhttp://www.ilog.com
  7. R. Kolisch and S. Hartmann, Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res.127 (2000) 394–407.  
  8. R. Kolisch and S. Hartmann, Experimental investigations of heuristics for resource-constrained project scheduling: an update. Eur. J. Oper. Res.174 (2006) 23–37.  
  9. H. Mahmoud, Pólya Urn Models. Taylor & Francis Group LLC – CRC Press (2008).  
  10. D. Merkle, M. Middendorf and H. Schmeck, Ant colony optimization for resource-constrained project-scheduling, IEEE Trans. Evol. Comput.6 (2002) 333–346.  
  11.  URIhttp://www.g-scop.inpg.fr/ChallengeROADEF2007/
  12. E. Tsang and C. Voudouris, 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).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.