Modelo de programación entera para la asignación de materias a las aulas de la USFQ

Abstract

En la actualidad, la creación de horarios en la universidad es una tarea bastante compleja y que consume mucho tiempo. Se crea un modelo de programación entera para la asignación de horarios a las aulas de la USFQ, el cual es un problema que cae dentro de la categoría de NP-hard y NP-complete, lo cual significa que el tiempo de resolución crece exponencialmente conforme se incrementa el número de variables. El modelo permite asignar clases teóricas, laboratorios, ejercicios y clases de computación. Además, evita todo tipo de conflictos de horario entre clases, profesores, aulas, y entre cursos que deben ser tomados por los mismos estudiantes. También se consideran los requerimientos de cada clase en cuanto a infraestructura y equipamiento. Se tiene la opción de que los profesores indiquen las horas en las que prefieren dictar clases, y se asegura que los profesores tengan un horario balanceado. Para resolver el modelo se crea una heurística que permite superar las limitaciones computacionales producidas por la complejidad del problema. El modelo fue validado con datos de dos colegios de la USFQ permitiendo crear horarios exitosamente, sin ningún tipo de conflictos y con las características señaladas. Finalmente, con los datos obtenidos se verifica que el problema es del tipo NP-Hard por lo que su tiempo de resolución crece exponencialmente conforme aumenta el número de variables.