Keywords
timetabling problems
heuristics
coloración robusta
problemas de horarios
heurísticas
How to Cite
Abstract
El problema de coloración robusta generalizado (PCRG) resuelve problemas de horarios que consideran restricciones especiales. Al ser una generalización del problema de coloración robusta, que es a su vez una generalización del problema de coloración, el PCRG es entonces un problema NP-Completo, por lo que es necesario utilizar métodos aproximados para encontrar buenas soluciones en un tiempo de cómputo razonable. En este trabajo se presenta un algoritmo de búsqueda tabú para programar casos de 30 a 180 horas por semana, para algunos de ellos encuentra la solución óptima, en otros casos, la solución obtenida supera a la mejor solución conocida. También se presentan ejemplos de mayor tamaño a los conocidos, obteniendo resultados muy competitivos, lo que se puede verificar por la ausencia de conflicto entre clases.
References
Alvarez Valdéz, R.; Crespo, E.; Tamarit, J.M. (1997) “A tabu search algorithm to schedule university examinations”, Qüestioó 21(1 & 2): 201–215.
de Werra, D. (1995) “Some combinatorial models for course scheduling”, PATAT’95: 296–308.
de Werra, D. (1996) “An introduction to timetabling”, Lecture Notes in Computer Science 1153, Springer: 296–308.
Glover, F. (1989) “Tabu search - Part I”, INFORMS Journal on Computing 1: 190–206.
Glover, F.; Laguna, M. (1997) Tabu search. Kluwer Academic Publishers, Norwell MA, U.S.A.
Glover, F.; Melián-Batista, B. (2003) “Búsqueda tabú”, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial 7(19): 29–48.
Lara Velázquez, P.; López Bracho, R.; Ramı́rez Rodríguez, J.; Yáñez, J. (2011) “A model for timetabling problems with period spread constraints”, JORS 62(1): 217–222.
Pérez de la Cruz, C.; Ramı́rez Rodríguez, J. (2011) “Un algoritmo genético para un problema de horarios con restricciones especiales”, Rev. Mat. Teor. Aplic. 18(2): 215–229.
Ramı́rez Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis Doctoral, Universidad Complutense de Madrid, Madrid, España.
Schaerf, A. (1996) “Tabu search techniques for large high-school timetabling problems”, IEEE Transactions on Systems, Man, and Cybernetics: 363–368.
Yañez, J.; Ramı́rez, J. (2003) “The robust coloring problem”, European Journal of Operational Research 148: 546–558.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2013 Revista de Matemática: Teoría y Aplicaciones