Ingeniare: Revista Chilena de Ingeniería (Dec 2007)
MODELOS DE PROGRAMACIÓN ENTERA PARA UN PROBLEMA DE PROGRAMACIÓN DE HORARIOS PARA UNIVERSIDADES MODELS OF INTEGER PROGRAMMING FOR AN UNIVERSITY TIMETABLING PROBLEM
Abstract
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.In this research, two models of Integer Programming for a University Timetabling Problem are formulated and two solution strategies for each model are presented. The problem consists of programming the courses to be taught, considering teaching faculty, days, periods, classrooms and requirements for courses that are taught in consecutive periods. The objective is to minimize the allocation of undesired time slots as well as balancing the daily workload for each group of students. The solution strategies are based on either combining models of direct allocation to classrooms or types of classrooms. The solution strategies that include reducing constraints, allow solving big problems with reasonable levels of efficiency, using the computer system for a short time. The approaches were used with real data obtained from the Facultad de ingeniería of the Universidad de Concepción, Chile. The models used in this research can be used in more general University Timetabling Problems, providing a great flexibility of resolution.
