Evaluación de heurísticas para el problema de asignación de aulas

Dada una lista de materias, con sus respectivos horarios e inscriptos, el problema de asignación de aulas consiste en asignar aulas a materias de forma tal que a materias con superposición horaria no se les asigne la misma aula. Existe un interés particular en resolver el caso en el que los distinto...

Descripción completa

Detalles Bibliográficos
Autores principales: Tacchini, Lautaro D., Martínez-Viademonte, Javier, Braga, Mónica A.
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2021
Materias:
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/141764
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-14.pdf
Aporte de:SEDICI (UNLP) de Universidad Nacional de La Plata Ver origen
Descripción
Sumario:Dada una lista de materias, con sus respectivos horarios e inscriptos, el problema de asignación de aulas consiste en asignar aulas a materias de forma tal que a materias con superposición horaria no se les asigne la misma aula. Existe un interés particular en resolver el caso en el que los distintos días en los cuales se cursa una materia sean asignados, preferentemente, a una misma aula. Dicha variación del problema pertenece a la familia de problemas NP-hard. Actualmente se cuenta con una herramienta, que resuelve el problema y es utilizada en distintas instituciones, demorando algunos minutos en conseguir una solución inicial, para luego alcanzar una solución óptima. El algoritmo exacto formula un programa lineal entero en el cual se estipula una penalidad por cada materia sin aula, o con distintas aulas en diferentes horarios. El objetivo del programa es minimizar la penalidad total, respetando las restricciones de capacidad y no superposición. A la vez, el algoritmo exacto establece un valor de gap basado en la teoría de dualidad para indicar la calidad de la mejor solución factible encontrada. En este trabajo se desarrolló una heurística con el fin de mejorar la solución existente. Posteriormente, se efectuaron diversos experimentos para evaluar el desempeño conjunto de la heurística y el algoritmo exacto en base a la calidad de las soluciones y al tiempo de ejecución. Por último, se hizo una selección entre las técnicas para ser integradas en futuras versiones de la herramienta.