×

France telecom workforce scheduling problem: a challenge. (English) Zbl 1173.90410

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90B50 Management decision making, including multiple objectives
90B70 Theory of organizations, manpower planning in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[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 · Zbl 1173.90405
[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. · Zbl 0985.90036 · doi:10.1016/S0377-2217(99)00485-3
[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. Zbl1116.90047 · Zbl 1116.90047 · doi:10.1016/j.ejor.2005.01.065
[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. · Zbl 1044.68784
[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). · Zbl 0882.90102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.