Implementación del modelo de restricciones del problema de calendarización de horarios universitarios con PYTHON

Abstract

En este documento se describe el modelo de restricciones del problema de calendarización de horarios de clases de la Universidad Tecnológica de la Mixteca (UTM) que se ha desarrollado utilizando el lenguaje de programación Python, de tal manera que se pueda generar una función objetivo que permita medir la calidad de una solución del problema. Al proceso de seleccionar y asignar recursos y tiempo al conjunto de actividades de una planificación, y teniendo en cuenta que la asignación debe cumplir con un conjunto de restricciones que reflejan la relación temporal entre las actividades y la capacidad limitada de los recursos compartidos se le llama Problema de Programación o Problema de Calendarización [1]. Las restricciones son los requerimientos del problema que pueden ser cuantificados para generar una medida de calidad de la solución/horario propuesto, por ejemplo, si tenemos las restricciones siguientes: Un profesor no puede estar asignado a dos salones simultáneamente y Un lugar (salón de clases) no puede ser utilizado por dos grupos diferentes al mismo tiempo (a la misma hora, el mismo día). Entonces si no se cumple con alguna de las restricciones, se deberá considerar una penalización cuantificable por cada restricción no satisfecha. La función objetivo se utiliza en problemas de optimización. En este caso se utilizará en la implementación de meta-heurísticas, específicamente se implementarán cuatro, las cuales son: Algoritmo Genético, Algoritmo de Búsqueda Tabú, Algoritmo de Búsqueda Armónica y Algoritmo de Recocido Simulado. Todo esto para comparar el desempeño de cada una de éstas y encontrar una solución factible y buena en términos de tiempo y función objetivo al problema de calendarización de la UTM.