Modelos de programación entera para un problema de programación de horarios para universidades

Models of integer programming for an university timetabling problem

En esta investigación se formulan dos modelos de Programación Lineal Entera para un problema de Programación de Horarios para Universidades y se presentan dos estrategias de solución para cada uno de ellos. El problema consiste en programar las asignaturas a ser dictadas, considerando los profesores, días, horarios, aulas y la necesidad de dictar las asignaturas en periodos consecutivos determinados. El objetivo es minimizar la asignación en periodos no deseados,balanceando la carga de trabajo diaria para cada grupo de alumnos. Las estrategias de solución combinan modelos de asignación directa a aulas o asignación a tipos de aulas. Las estrategias de solución que consideran relajación de restricciones, permiten resolver problemas de gran tamaño, a niveles de calidad razonables y utilizando pequeños tiempos computacionales. Los enfoques fueron aplicados a instancias de la Facultad de Ingeniería de la Universidad de Concepción, Chile. Los modelos utilizados en esta investigación pueden ser aplicados a una gran cantidad de problemas de Programación de Horarios en Universidades, proporcionando una gran flexibilidad de resolución.

INTRODUCCIÓN

Los Problemas de Programación de Horarios consisten, básicamente, en generar horarios para tareas definidas, buscando cumplir de la mejor manera con condiciones y requerimientos específicos. Estos problemas son muy comunes y se encuentran en distintos tipos de actividades tales como: Actividades Educacionales, Universidades, Colegios, Institutos, Facultades, Departamentos, Actividades Deportivas, Actividades de Transporte y Actividades que involucren personaso equipos de trabajo.

El problema de Programación de Horarios en Universidades consiste en programar en un Horizonte de Planificación (generalmente una semana) las asignaturas que se dictan en un Periodo Académico determinado (año, trimestre o semestre), para las distintas asignaturas que las requieren, considerando los profesores necesarios en cada asignatura, los grupos de alumnos que toman un conjunto de asignaturas, los días o periodos disponibles, las aulas requeridas de tal manera de satisfacer un conjunto de restricciones relacionadas con la organización del sistema educacional.

No existe una sola clasificación para los Problemas de Timetabling Educacionales [4, 9 y 20]. En general, cada una de las clasificaciones propuestas define distintas decisiones que se deben tomar para generar una correcta gestión de la enseñanza dentro de una Unidad Académica.