Defensa síncrona de TFGs: un problema de planificació

Abstract

La finalitat d'aquest Treball és estudiar teòricament i construir una eina per resoldre un problema realista en l'àmbit de la gestió d'un sistema de planificació de defenses síncrones de Treballs de Final de Grau. Aquest problema és interessant en el context de la planificació de TFGs, però els resultats presentats són fàcilment extrapolables a altres àmbits de la planificació d'horaris. Per tal de dur a terme aquesta tasca, inicialment es realitza una descripció del problema a tractar i a partir d'aquesta descripció se'n fa un model teòric. Disposant del model teòric, s'analitza la complexitat computacional del problema com a informació fonamental per a desenvolupar una eina que el pugui resoldre eficientment. Un cop esclarida la complexitat computacional del problema es desenvolupa una eina per resoldre'l així com un generador d'instàncies aleatòries del problema per tal de dur a terme els jocs de proves escaients. Tot seguit es duen a terme els jocs de proves oportuns sobre l'eina desenvolupada i es comprova que l'eina és correcta en la resolució del problema. Finalment s'implementen les millores convenients sobre l'eina per millorar-ne el rendiment. Com a conclusions del Treball s'obté la NP-completesa del problema demostrada i la convicció que l'eina desenvolupada el resol correctament.

La finalidad de este trabajo es estudiar teóricamente y construir una herramienta para resolver un problema realista en el ámbito de la gestión de un sistema de planificación de defensas síncronas de Trabajos de Fin de Grado. Este problema es interesante en el contexto de la planificación de TFGs, pero los resultados presentados son fácilmente extrapolables a otros ámbitos de la planificación de horarios. Para llevar a cabo esta tarea, inicialmente se realiza una descripción del problema a tratar y a partir de esta descripción se hace un modelo teórico. Disponiendo del modelo teórico, se analiza la complejidad computacional del problema como información fundamental para desarrollar una herramienta que pueda resolver eficientemente. Una vez aclarada la complejidad computacional del problema se desarrolla una herramienta para resolverlo así como un generador de instancias aleatorias del problema para llevar a cabo los juegos de pruebas. A continuación se llevan a cabo los juegos de pruebas oportunos sobre la herramienta desarrollada y se comprueba que la herramienta es correcta en la resolución del problema. Finalmente se implementan las mejoras convenientes sobre la herramienta para mejorar el rendimiento. Como conclusiones del Trabajo, se obtiene la NP-completitud del problema demostrado y la convicción de que la herramienta desarrollada lo resuelve correctamente.

The goal for this TFG is to theoretical study and tool develop in order to solve a realistic problem in the scope of a scheduling system for the synchronous defense of TFGs. This problem is interesting in the ambit of TFGs scheduling, but the results shown are easily extrapolable to other scheduling problems. In other to achieve this goal in first place a description of the problem is shown and starting with this description a theoretical model is done. Based on this theoretical model the computational complexity of the problem is studied as a basic information in order to develop a tool for efficiently solve it. Once the computational complexity is clear a tool is developed for solving it, also a random instance generator is developed in order to test the tool. The next step is to test the tool and check that the tool solves the problem correctly. Finally some improvements are applied in order to improve the performing of the tool. The conclusions for this TFG are the fact that the problem is NP-Complete and that the tool solves the problem correctly.