Heurísticas iniciales para el problema de asignación de aulas

Abstract

Dada una lista de materias, con sus respectivos horarios e inscriptos, el problema de asignación de aulas consiste en asignar un conjunto de aulas de manera tal que no se superponga en ningún momento más de una materia en cada aula. Existe un interés particular en resolver el caso en que los distintos días en que 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 utilizado 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 a la que no se le asigne siempre una misma aula en sus distintos horarios. El objetivo de este programa es minimizar la penalidad total, respetando las restricciones de capacidad y no superposición. Durante el presente trabajo se desarrollaron distintas heurísticas para generar soluciones iniciales al problema; posteriormente, se efectuó un análisis de los resultados obtenidos por la herramienta partiendo de distintas soluciones iniciales. Finalmente, se selecciona una heurística para ser integrada en versiones futuras de la herramienta.