Modelado y optimización de los horarios de un centro universitario con Programación Matemática

Abstract

En este trabajo se presenta un modelo de programación lineal entera para la obtención del horario del primer cuatrimestre del Grado en Matemáticas de la Facultad de Matemáticas de Sevilla, para el curso 2019/2020. Se ha dividido en cuatro capítulos. En el primero de ellos, se introduce el problema de horarios y asignación de aulas, exponiendo asimismo los antecedentes bibliográficos que abordan la resolución de este tipo de problemas mediante el uso de la programación lineal, y se enumeran los objetivos que se han planteado en este trabajo. En el segundo capítulo, se exponen las nociones y resultados básicos de programación lineal y programación lineal entera necesarios para la comprensión y desarrollo del modelo formulado. Además, se explican las principales características del programa informático AMPL. En el tercer capítulo, se describen, de manera general, las características y requerimientos que debe de verificar un problema de horarios desde el punto de vista de la programación lineal. También se exponen las características propias de la Facultad de Matemáticas de Sevilla que influyen en la formulación del modelo buscado. Asimismo, se aporta la formulación del modelo y la explicación de las respectivas restricciones que aparecen en ella, junto con el código de dicha formulación escrito en lenguaje AMPL y algunas tablas con los datos del problema necesarios para su resolución. En el cuarto y último capítulo, se presentan los horarios obtenidos, se realiza un análisis de sensibilidad del modelo creado y se explican las conclusiones sobre el trabajo realizado, comparando los resultados con el horario real del curso 2019/2020 para comprobar la eficacia del modelo desarrollado. Finalmente, se incluye un apéndice en el cual se expone la formulación del modelo para obtener el horario correspondiente al segundo cuatrimestre, dando los datos necesarios para la resolución del modelo para este período académico, así como los horarios obtenidos.

This document presents an interger programming problem to design the timetable for the first four-month period of Degree in Maths at University of Seville. This document has been divided in four chapters. In Chapter 1, the problem is introduced and some reports which use linear programming to create models for the problem of scheduling courses at universities are quoted. In addition, the objectives of this work are enumerated too. In Chapter 2, a list of mathematical definitions and theorems are given to understand the formulation of the model; furthermore, principals characteristics of the program AMPL are explained. In Chapter 3, the requeiremets of Faculty of Maths at Seville that are necessary to the timetable to be valid are discribed. Also, the formulation of the model is given as well as the explanation of the constraints, the datums of the problem and the AMPL code for the problem. In Chapter 4, the timetables obtained are presented and the conclusions of this work are exposed. Sensivity analysis is performed in order to investigate how the solution is affected when some conditions are changed. Finally, the formulation of the model for the second four-month period is described in Appendix A as well as the results obtained by this model.