Implementación de un algoritmo GRASP para el problema de coloración de grafos aplicado a la calendarización de exámenes en una institución educativa

Resumen

Una de las tareas que enfrentan las instituciones educativas cada año, es la planificación de los horarios de clases y exámenes. Su dificultad  radica  en  que  diversas  restricciones  operativas  surgen en  el  momento  de  la  planificación.  Dada  la  naturaleza  del  problema descrito  anteriormente,  la  calendarización  de  exámenes  pertenece  al  conjunto  de  problemas  de  optimización  combinatoria  categorizado NP-Duro  por  lo  que  resulta  complejo  resolverlo  por  métodos  exactos.  La  ventaja  es  que  la  calendarización  de  exámenes  es  un  problema operativo por lo que bastaría con obtener  soluciones factibles de gran calidad, no necesariamente la óptima, en tiempos computacionalesrazonables. Una de las herramientas utilizadas para el efecto, es la construcción de heurísticas basadas en metaheurísticas por la fortaleza en  la  exploración  inteligente  en  el  espacio  de  soluciones.  Con  base  en  lo  anterior,  en  el  presente  trabajo  se  desarrollará  un  algoritmo  heurístico basado en la metodología GRASP el mismo que se lo aplicará en la confección de horarios de exámenes sujetos a un conjunto de restricciones de diversas índoles.