Algoritmo genético distribuído para problema de timetabling

Abstract

Este artigo apresenta um algoritmo genético distribuído para resolução do problema de timetabling do Instituto Federal de Santa Catarina Campus Lages, que visa gerar um quadro de horários sem violar as restrições impostas pela instituição. Para tal, foi elaborado um algoritmo que pode ser executado em ambiente centralizado ou distribuído, que conta com um pré-processamento que é responsável por diminuir o espaço de busca, além de um algoritmo de árvore de busca em profundidade limitada para o ambiente distribuído, com o objetivo de resolver os conflitos restantes. Foi constatado que o algoritmo alcançou, em ambos os ambientes, a solução perfeita e, além disso, a solução em ambiente distribuído chegou nos resultados, em media, 26 segundos, enquanto a centralizada levou 70 segundos.

This paper presents a Distributed Genetic Algorithm for solving the Timetabling problem of the Federal Institute of Santa Catarina Campus Lages, which aims to build a timetable without violating the restrictions imposed by the institution. To this end, an algorithm that can be run in a centralized or distributed environment was developed. Such algorithm has a pre-processing step which is responsible for reducing the search space, in addition to a depth-first search for the distributed environment, aimming to solve the remaining conflicts. It was verified that the algorithm reached, in both environments, the perfect solution and, in addition, the solution in the distributed environment reached the results in 26 seconds on average, while the centralized solution took 70 seconds.