Un algoritmo genético para un problema de horarios con restricciones especiales

Resumen

En Ramírez (2001) se introdujo el problema de coloración robusta generalizado (PCRG), el cual resuelve problemas de horarios que consideran restricciones del tipo: dos eventos no pueden realizarse a la misma hora y debe haber al menos d días entre dos eventos. El PCRG es una coloración robusta, en que dada una gráfica y un número fijo de colores, no necesariamente el número cromático, considera la distancia entre colores como penalización de las aristas complementarias.Se demostró que el problema es NP-Completo, por lo que es necesario utilizar métodos aproximados para encontrar buenas soluciones en un tiempo razonable. En este trabajo se presenta un híbrido de un algoritmo genético con uno de búsqueda local para casos de 30 a 120 horas por semana, se demuestra que para algunos la solución es óptima y en otros se encuentran soluciones muy prometedoras.