Free time post enrolment course timetabling problem

Abstract

En este trabajo se estudia una variante multiobjetivo del Post Enrolment Course Timetabling Problem (PECTP), un problema NP-duro que consiste en calendarizar las actividades académicas de una institución de educación superior en un conjunto de salones y bloques horarios, considerando que los estudiantes realizan una preinscripción de los cursos a los que desean asistir. A esta formulación se añade que cada estudiante declara además un conjunto de bloques horarios que preferiría tener libres, por lo que el problema exige optimizar simultáneamente dos objetivos en conflicto: la cobertura de los cursos preinscritos y la satisfacción de las preferencias de tiempo libre. Su alta complejidad combinatoria –derivada de las restricciones institucionales y de los topes de horario de cada estudiante– vuelve impracticable la resolución exacta en casos de tamaño realista. Para abordarlo se propone un algoritmo NSGA-II especializado. Se implementa un generador de instancias que simula casos de la Universidad Técnica Federico Santa María con distintos tamaños, niveles de ocupación del horario y distribuciones de la demanda. Los frentes obtenidos se contrastan con los de un método exacto que resuelve el mismo modelo mediante AMPL y el solver Gurobi, midiendo la calidad con el indicador de hipervolumen y un test de Wilcoxon. Los resultados evidencian un claro compromiso entre calidad y costo computacional: el método exacto alcanza un hipervolumen superior de forma estadísticamente significativa, pero NSGA-II obtiene sus soluciones en un tiempo órdenes de magnitud menor y con una brecha de calidad que se reduce al aumentar el tamaño del problema, llegando a un 92–94 % del hipervolumen del método exacto en las instancias grandes, donde este último degrada la diversidad de su frente. Esto posiciona al algoritmo propuesto como una alternativa práctica para una calendarización centrada en el estudiante a escalas realistas.

This work studies a multiobjective variant of the Post Enrolment Course Timetabling Problem (PECTP), an NP-hard problem that consists of scheduling the academic activities of a higher education institution across a set of rooms and time blocks, given that students pre-enrol in the courses they wish to attend. This formulation is extended by letting each student declare a set of time blocks they would prefer to keep free, so that the problem requires the simultaneous optimization of two conflicting objectives: the coverage of the pre-enrolled courses and the satisfaction of the free-time preferences. Its high combinatorial complexity –arising from the institutional constraints and the schedule clashes of each student– makes exact resolution impractical for realistically sized cases. To address it, a specialized NSGA-II algorithm is proposed. An instance generator is implemented to simulate cases of the Universidad Técnica Federico Santa María with varying sizes, timetable occupancy levels and demand distributions. The resulting fronts are contrasted with those of an exact method that solves the same model through AMPL and the Gurobi solver, measuring quality with the hypervolume indicator and a Wilcoxon test. The results reveal a clear trade-off between quality and computational cost: the exact method attains a statistically significantly higher hypervolume, but NSGA-II obtains its solutions in orders of magnitude less time and with a quality gap that narrows as the problem size grows, reaching 92–94 % of the exact method’s hypervolume on the large instances, where the latter degrades the diversity of its front. This positions the proposed algorithm as a practical alternative for student-centered timetabling at realistic scales.