Development of a linear programming model for the University Course Timetabling Problem

Desarrollo de un modelo de programación lineal para el problema del horario de los cursos universitarios

La creación de horarios para los cursos es un problema al que se enfrentan las universidades al principio de cada semestre. Esta actividad representa una importante tarea administrativa porque consume una cantidad significativa de recursos. En términos de complejidad computacional, se clasifica como NP-difícil, ya que exige una enorme capacidad de procesamiento. La programación de horarios se modela de diferentes maneras, con el objetivo de adaptarse al contexto educativo del país, cumplir con las normas específicas de las instituciones de educación superior o los objetivos específicos de los administradores, entre otros. En este artículo, proponemos un modelo matemático para resolver el problema del horario de los cursos universitarios y optimizar la utilización de las aulas. Para resolver el modelo propuesto, se desarrolló un algoritmo que divide el problema, resolviéndolo con herramientas de programación lineal entera mixta. Experimentos computacionales aplicados a una base de datos real de una universidad pública brasileña confirmaron el buen desempeño del enfoque propuesto, que reduce considerablemente la cantidad de aulas asignadas.

1. INTRODUCCIÓN

La creación de horarios para sus cursos es un problema al que deben enfrentarse las universidades al principio de cada semestre y, dado que consume una cantidad significativa de recursos, representa una importante tarea administrativa. Este problema consiste en asignar determinados recursos, de manera que se respeten algunas restricciones materiales y pedagógicas. Las restricciones más comunes son físicas (aulas, laboratorios, auditorios, gimnasios), relacionadas con las personas (profesores, alumnos), intangibles (días, períodos, semestres, cursos, conferencias), entre otras.

Los casos reales pueden contener cientos, o miles, de estos tipos de recursos. Además, cualquier solución factible debe respetar una cantidad igualmente grande de restricciones, y debe cumplir, de la mejor manera posible, ciertas exigencias (relativas a los profesores, a la institución educativa, a la reducción de costes, entre otras). Así pues, construir un buen horario es una tarea muy difícil.

Conocido en la literatura como University Course Timetable Problem (UCTP), según Schaerf (1999), este problema se refiere a la programación del conjunto de clases de un curso en una cantidad limitada de aulas y períodos. El autor señala también que la principal diferencia con el problema del horario escolar es que, en las universidades, diferentes cursos pueden tener alumnos en común.

Las soluciones a este problema suelen obtenerse mediante la implicación de muchas personas durante varios días. Además, algunas de esas soluciones podrían no ser satisfactorias en algunos aspectos, por ejemplo, un estudiante que desee matricularse en dos cursos programados en el mismo periodo (Schaerf, 1999).