Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos

Abstract

En este estudio se presenta un modelo de programación no lineal en variables enteras para un problema de programación de horarios universitarios vespertinos y se propone un algoritmo para su solución. El problema consiste en programar asignaturas en un horizonte de planificación considerando profesores, aulas, alumnos, días y un conjunto de restricciones, buscando minimizar la penalidad de no satisfacer los requerimientos de profesores, el número de cambios de sala y el número de periodos libres entre cursos. Se propone un modelo matemático y una implementación de un algoritmo de tipo búsqueda tabú. Para evaluar la efectividad del algoritmo se utilizaron casos de prueba con datos reales del Instituto IPEGE (Chile), en los que el algoritmo es capaz de obtener soluciones factibles en un tiempo razonable. Los parámetros de dicho algoritmo fueron calibrados con los casos de prueba, para posteriormente evaluar su desempeño. Se muestra que este obtuvo mejores soluciones que el método manual.

This study presents a model of non-linear integer programming for an evening university timetabling problem and proposes an algorithm for its solution. The problem consists of programming subjects over a planning horizon considering teachers, classrooms, students, days and a set of constraints, trying to minimize the penalty of unsatisfied requirements of teachers, the number of changes of classrooms and the numbers of free periods between courses. A mathematical model is proposed beside the implementation of tabu search algorithm. Test cases are proposed to evaluate the effectiveness of the algorithm, which have real data obtained from IPEGE Institute (Chile), where the algorithm could obtain feasible solutions within a reasonable time. The parameters of the algorithm were calibrated with the test cases to later evaluate its performance, showing that it obtained better solutions than the manual method by an average of 66,5 % and it is about 62,7 % of lower bound calculated