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

Guardado en:
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:
Ciencias Informáticas
Heurísticas
Algoritmo
Asignación de aulas
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
id I19-R120-10915-141764
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Heurísticas
Algoritmo
Asignación de aulas
spellingShingle Ciencias Informáticas
Heurísticas
Algoritmo
Asignación de aulas
Tacchini, Lautaro D.
Martínez-Viademonte, Javier
Braga, Mónica A.
Evaluación de heurísticas para el problema de asignación de aulas
topic_facet Ciencias Informáticas
Heurísticas
Algoritmo
Asignación de aulas
description 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.
format Objeto de conferencia
Resumen
author Tacchini, Lautaro D.
Martínez-Viademonte, Javier
Braga, Mónica A.
author_facet Tacchini, Lautaro D.
Martínez-Viademonte, Javier
Braga, Mónica A.
author_sort Tacchini, Lautaro D.
title Evaluación de heurísticas para el problema de asignación de aulas
title_short Evaluación de heurísticas para el problema de asignación de aulas
title_full Evaluación de heurísticas para el problema de asignación de aulas
title_fullStr Evaluación de heurísticas para el problema de asignación de aulas
title_full_unstemmed Evaluación de heurísticas para el problema de asignación de aulas
title_sort evaluación de heurísticas para el problema de asignación de aulas
publishDate 2021
url http://sedici.unlp.edu.ar/handle/10915/141764
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-14.pdf
work_keys_str_mv AT tacchinilautarod evaluaciondeheuristicasparaelproblemadeasignaciondeaulas
AT martinezviademontejavier evaluaciondeheuristicasparaelproblemadeasignaciondeaulas
AT bragamonicaa evaluaciondeheuristicasparaelproblemadeasignaciondeaulas
bdutipo_str Repositorios
_version_ 1764820459729190914

Ejemplares similares