An evolutionary algorithm with simulated annealing-based mutation for automated timetabling problem

Abstract

En la actualidad el poder resolver el problema de asignación de cursos en una Universidad se ha vuelto muy necesario para mejorar la eficiencia a la hora de asignar horarios y manejar grandes cantidades de datos sobre estudiantes, maestros, aulas, etc. En este trabajo se presentar un método para resolver este problema mediante el uso de un algoritmo evolutivo con una mutación basada en el algoritmo de recocido simulado. El problema consiste en asignar un conjunto de estudiantes y eventos (clases o laboratorios) en un horario tomando en cuenta las aulas disponibles, sujeto a restricciones obligatorias y restricciones no-obligatorias. El algoritmo desarrollado en este trabajo consta de dos fases. En la primera fase se intenta asignar la mayor cantidad de eventos que cumplan con las restricciones obligatorias mediante el uso de distintas heurísticas. Posteriormente en la segunda fase se implementó el algoritmo evolutivo con una mutación basada en el algoritmo de recocido simulado, cuya finalidad es intentar cumplir las restricciones obligatorias que no se hayan podido cumplir en la fase anterior y cumplir la mayor cantidad de restricciones no-obligatorias. Al final se espera tener un horario con todos los eventos asignados cumpliendo todas las restricciones obligatorias y la mayor cantidad de restricciones no-obligatorias posibles.