Scheduling technicians and tasks in a telecommunications company. (English) Zbl 1231.90258
Summary: This paper proposes a construction heuristic and an adaptive large neighborhood search heuristic for the technician and task scheduling problem arising in a large telecommunications company. This problem was solved within the framework of the 2007 challenge set up by the French Operational Research Society (ROADEF). The paper describes the authors’ entry in the competition which tied for second place.
MSC:
| 90B70 | Theory of organizations, manpower planning in operations research |
| 90B90 | Case-oriented studies in operations research |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Ahuja, R. K., Ergun, Ö., Ergun, J. B., & Punnen, A. P. (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123, 75–102. · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9 |
| [2] | Begur, S. V., Miller, D. M., & Weaver, J. R. (1997). An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces, 27(4), 35–48. · doi:10.1287/inte.27.4.35 |
| [3] | Bellenguez, O., & Néron, E. (2005). Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In E. K. Burke & M. Trick (Eds.), Lecture notes in computer science : Vol. 3616. Practice and theory of automated timetabling V: 5th international conference, PATAT 2004 (pp. 229–243). Berlin: Springer. |
| [4] | Bellenguez-Morineau, O., & Néron, E. (2007). A branch-and-bound method for solving multi-skill project scheduling problem. RAIRO–Operations Research, 41, 155–170. · Zbl 1154.90413 · doi:10.1051/ro:2007015 |
| [5] | Bertels, S., & Fahle, T. (2006). A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Computers & Operations Research, 33, 2866–2890. · Zbl 1086.90533 · doi:10.1016/j.cor.2005.01.015 |
| [6] | Caramia, M., & Giordani, S. (2009). A new approach for scheduling independent tasks with multiple modes. Journal of Heuristics, 15, 313–329. · Zbl 1180.90116 · doi:10.1007/s10732-007-9062-y |
| [7] | Caseau, T., & Koppstein, P. (1992). A cooperative-architecture expert system for solving large time/travel assignment problems. In International conference on databases and expert systems applications (pp. 197–202). |
| [8] | Danna, E., & Perron, L. (2003). Structured vs. unstructured large neighborhood search: a case study on job-shop scheduling problems with earliness and tardiness costs. In Lecture notes in computer science (Vol. 2833, pp. 817–821). Berlin: Springer. |
| [9] | Dutot, P.-F., Laugier, A., & Bustos, A.-M. (2006). Technicians and interventions scheduling for telecommunications. France Telecom R&D, August 2006. |
| [10] | Estellon, B., Gardi, F., & Nouioua, K. (2008). Recherche locale haute performance pour la planification des interventions à France Télécom. In JFPC 2008–Quatrièmes Journées Francophones de Programmation par Contraintes. Nantes, France. |
| [11] | Eveborn, P., Flisberg, P., & Rönnqvist, M. (2006). Laps care–an operational system for staff planning of home care. European Journal of Operational Research, 171, 962–976. · Zbl 1116.90373 · doi:10.1016/j.ejor.2005.01.011 |
| [12] | Hurkens, C. A. J. (2007). Incorporating the strength of MIP modeling in schedule construction. In G. Finke (Ed.), ROADEF 2007, le 8ème Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision. Grenoble, France. |
| [13] | Kirkpatrick, S., Gelatt, C. D. Jr., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [14] | Laborie, P., & Godard, D. (2007). Self-adapting large neighborhood search: application to single-mode scheduling problems. In Proceedings of MISTA-07, Paris, France. |
| [15] | Meyers, C., & Orlin, J. B. (2007). Very large-scale neighborhood search techniques in timetabling problems. In Lecture notes in computer science (Vol. 3867, pp. 24–39). Berlin: Springer. |
| [16] | Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097–1100. · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2 |
| [17] | Palpant, M., Artigues, C. C., & Michelon, P. (2004). LSSPER: solving the resource-constrained project scheduling problem with large neighbourhood search. Annals of Operations Research, 131, 237–257. · Zbl 1066.90037 · doi:10.1023/B:ANOR.0000039521.26237.62 |
| [18] | Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34, 2403–2435. · Zbl 1144.90318 · doi:10.1016/j.cor.2005.09.012 |
| [19] | Rios-Solis, Y. A., & Sourd, F. (2008). Exponential neighborhood search for a parallel machine scheduling problem. Computers & Operations Research, 35, 1697–1712. · Zbl 1211.68038 · doi:10.1016/j.cor.2006.10.008 |
| [20] | Ropke, S., & Pisinger, D. (2006a). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40, 455–472. · doi:10.1287/trsc.1050.0135 |
| [21] | Ropke, S., & Pisinger, D. (2006b). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171, 750–775. · Zbl 1116.90019 · doi:10.1016/j.ejor.2004.09.004 |
| [22] | Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., & Dueck, G. (2000). Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics, 159, 139–171. · Zbl 0997.90105 · doi:10.1006/jcph.1999.6413 |
| [23] | Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In Lecture notes in computer science : Vol. 1520. CP-98, fourth international conference on principles and practice of constraint programming (pp. 417–431). Berlin: Springer. |
| [24] | Tsang, E., & Voudouris, C. (1997). Fast local search and guided local search and their application to British telecom’s workforce scheduling problem. Operations Research Letters, 20, 119–127. · Zbl 0882.90102 · doi:10.1016/S0167-6377(96)00042-9 |
| [25] | Weigel, D., & Cao, B. (1999). Applying GIS and OR techniques to solve Sears technician-dispatching and home-delivery problems. Interfaces, 29(1), 112–130. · doi:10.1287/inte.29.1.112 |
| [26] | Xu, J., & Chiu, S. Y. (2001). Effective heuristic procedures for a field technician scheduling problem. Journal of Heuristics, 7, 495–509. · Zbl 1013.90061 · doi:10.1023/A:1011377929184 |
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.
