Diseño e implementación de una herramienta de optimización para la programación de horarios académicos en la universidad: aplicación a la ETSII

Abstract

[ES] En el presente Trabajo de Fin de Grado se propone una herramienta matemática para facilitar la toma de decisiones y reducir el tiempo de gestión invertido en la programación de calendarios académicos de la Escuela Técnica Superior de Ingenieros Industriales (ETSII) de la Universidad Politécnica de Valencia (UPV), al tiempo que se obtienen mejores horarios para estudiantes y profesores con menores recursos. La propuesta surge a raíz de la detección de oportunidades de mejora respecto al método actual de asignación de horarios y se encuadra dentro de la problemática de asignación de recursos limitados a actividades, ligado al ámbito de Programación de Operaciones y Métodos Cuantitativos de la Organización Industrial. La problemática objeto de estudio se modelará a través de la programación lineal entera mixta y se implementará en Pyomo. El problema objeto de estudio presenta ciertas características que hacen novedoso los modelos obtenidos. Para justificar su novedad, en el capítulo de antecedentes se hará una revisión sistemática de trabajos sobre el tema. El problema se modelará en dos etapas, con un modelo cada una de ellas, de manera que se simplifica su posterior resolución manteniendo la calidad de las soluciones obtenidas. Cada parte contará con diferentes funciones objetivo y estará sujeta a diferentes restricciones. Algunas de las restricciones se formularán como ¿opcionales¿ pudiendo ser activadas o no a voluntad del decisor, de manera que se generan diversas variantes del modelo que mejor se ajustan a las políticas de cada Escuela. Además, lo anterior también permitirá al decisor, poder elegir entre las diversas soluciones obtenidas, aquella que se adapte mejor a las circunstancias o preferencias del momento. Una vez formulado, el modelo se implementará en Pyomo, una extensión de Python 6.4.1. y el solver utilizado para su resolución será Gurobi 9.5.1 con la interfaz de programación JupyterLab 3.4.2. A continuación, se procederá a su validación a través de la definición de diversos escenarios utilizando datos reales obtenidos de la ETSII-UPV. Posteriormente, se llevará a cabo un análisis de las diferentes soluciones obtenidas de cada variante del modelo, así como su eficiencia computacional.

[CAT] En aquest treball de fi de grau es proposa una eina d'optimització per facilitar la presa de decisions i reduir el temps de gestió invertit en la programació d'horaris universitaris per a escoles oferents de diversos títols, alhora que s'obtenen millors horaris per a estudiants i professors amb menors recursos. En aquest treball es valida l'eina a través d'aplicació a la programació d'horaris de l'Escola Tècnica Superior d'Enginyers Industrials (ETSII) de la Universitat Politècnica de València (UPV). La proposta sorgeix arran de la detecció d’oportunitats de millora respecte al mètode actual d’assignació d’horaris i s’enquadra dins de la problemàtica d’assignació de recursos limitats a activitats, lligat a l’àmbit de Programació d’Operacions i Mètodes Quantitatius de l’Organització Industrial. El problema objecte de estudi presenta certes característiques pròpies que converteixen en nous els models desenvolupats. Per justificar la novetat, al capítol d'antecedents es fa una revisió bibliogràfica sistemàtica de treballs sobre el tema. El problema es modela en dues etapes, a través d'un model de programació lineal sencera mixta cadascuna, de manera que se'n simplifica la resolució posterior mantenint la qualitat de les solucions obtingudes. Cada part compta amb diferents funcions objectiu i està subjecta a restriccions diferents. Algunes de les restriccions es formulen com a “opcionals” podent ser activades o no a voluntat del decisor, de manera que es generen diverses variants del model que millor s'ajusten a les polítiques de cada Escola. A més, això també permet al decisor poder escollir entre les diverses solucions obtingudes, aquella que s'adapti millor a les circumstàncies o preferències del moment. Un cop formulats els models es du a terme la seua implementació a Pyomo, una extensió de Python 6.4.1, i es resolen mitjançant Gurobi 9.5.1 amb la interfície de programació JupyterLab 3.4.2. La validació dels dos models es fa a través de la definició de diversos escenaris utilitzant dades reals obtingudes de l'ETSII-UPV. Posteriorment, es du a terme un anàlisi de les diferents solucions obtingudes de cada variant del model, així com la seua eficiència computacional.

[EN] In this Final Degree Project, a mathematical tool is proposed to facilitate decision-making and reduce the management time invested in the programming of academic calendars of the Higher Technical School of Industrial Engineers (ETSII) of the Polytechnic University of Valencia (UPV), while obtaining better schedules for students and teachers with fewer resources. The proposal arises as a result of the detection of opportunities for improvement with respect to the current method of assigning schedules and falls within the problem of allocation of limited resources to activities, linked to the scope of Operations Programming and Quantitative Methods of Industrial Organization. The problematic object of study will be modeled through mixed integer linear programming and implemented in Pyomo. The problem under study has certain characteristics that make the models obtained novel. To justify its novelty, a systematic review of works on the subject will be made in the background chapter. The problem will be modeled in two stages, with one model each, so that its subsequent resolution is simplified while maintaining the quality of the solutions obtained. Each part will have different objective functions and will be subject to different restrictions. Some of the restrictions will be formulated as "optional" and may or may not be activated at the will of the decision-maker, so that various variants of the model are generated that best fit the policies of each School. In addition, this will also allow the decision-maker to choose between the various solutions obtained, the one that best suits the circumstances or preferences of the moment. Once formulated, the model will be implemented in Pyomo, an extension of Python 6.4.1, the solver used for its resolution is Gurobi 9.5.1 with the JupyterLab 3.4.2 programming interface. Next, it will be validated through the definition of various scenarios using real data obtained from the ETSII-UPV. Subsequently, an analysis of the different solutions obtained from each variant of the model will be carried out, as well as their computational efficiency.