El presente trabajo expone una metaheurística híbrida que permite encontrar buenas soluciones para un problema de horarios con restricciones especiales, el cual se modela como un Problema de Coloración Robusta Generalizado (PCRG). El algoritmo híbrido (Algoritmo genético y Búsqueda de vecindad variable reducida) desarrollado para el Problema de Coloración Robusta Generalizado halla mejores soluciones para algunos casos reportados en Lara 2010 [2] y como el algoritmo genético y caso reportados en Ramírez 2001 [1] encuentra la solución óptima. Además se presentan casos de mayor tamaño siguiendo la metodología en Lara 2010 [2] y sus soluciones.