SISTEMA GERADOR DE HORÁRIOS UTILIZANDO ALGORITMOS GENÉTICOS PARALELOS

Daniela Saccol Peranconi, Osmar Eduardo Nothaft, Jacques Nelson Schreiber

Resumo


 

A elaboração de grades de horários em instituições de ensino demanda considerável tempo para ser concluída. Além disso, na maioria dos casos, a elaboração é feita manualmente, o que pode gerar soluções não muito boas. O grande tempo empregado e a complexidade do problema levam a necessidade de resolvê-lo de forma computacional, tanto em busca de maior eficiência na resolução quanto da melhor solução possível. Na literatura, esse problema recebe o nome de timetabling problem, que trata da alocação de horários para todas as aulas de uma determinada instituição de ensino, considerando-se um conjunto restrito de horários, professores e satisfazendo um conjunto de restrições. Conforme aumentam as restrições, a solução do problema não é possível de ser encontrada em tempo hábil pelos métodos convencionais de programação, surgindo a necessidade de se utilizar metaheurísticas, como os Algoritmos Genéticos (AGs). Estes representam uma forma de se partir de um número limitado de possíveis soluções e, através de transformações sucessivas em seus valores, chegar a uma solução considerada ótima. Tais algoritmos reproduzem, de forma computacional, um processo baseado na evolução natural das espécies. Porém, quando o número de restrições do problema é elevado, a utilização do AG pode demorar a encontrar boas soluções. Vários esforços para a otimização da velocidade dos AGs têm sido realizados por diversos pesquisadores, sendo que o método mais promissor para o efetivo alcance de melhorias do algoritmo são as implementações paralelas. Nesse sentido, este trabalho propõe a implementação de uma solução paralela, empregando AGs, para o problema de geração de horários do Departamento de Informática (DI) da Universidade de Santa Cruz do Sul (UNISC). Esse departamento possui 24 professores, que atendem três cursos de graduação: Ciência da Computação (com três currículos diferentes: uma turma pela manhã, outra à noite e turmas com aula pela manhã até o quarto semestre e depois com aula à noite), Engenharia de Computação e Licenciatura em Computação. Optou-se por implementar o gerador de horários utilizando-se Algoritmos Genéticos Paralelos (AGPs), com a exploração de arquiteturas com memória distribuída, como os aglomerados de computadores. Para auxiliar na implementação do software, foram pesquisadas bibliotecas que atendessem tanto os AGPs quanto a necessidade de distribuição das tarefas em um aglomerado. Dentre as encontradas, GAUL mostrou-se como a mais adequada. A opção por ela deu-se, principalmente, pela quantidade de funcionalidades disponíveis e pela utilização de MPI (Message Passing Interface) para auxílio à distribuição das tarefas. O gerador de horários encontra-se em fase de implementação, de onde resultarão uma versão sequencial e outra paralela para a solução. Os testes serão conduzidos de maneira a se avaliar os tempos de execução de cada uma das versões mediante a variação da quantidade de restrições ao problema. O objetivo é que o gerador resultante, embora tenha como estudo de caso o DI, seja o mais genérico possível para atender a outros casos de geração de horários da universidade ou de qualquer outra instituição de ensino, sendo necessário, apenas, alterar as informações de entrada para o software. E, com a versão paralela da aplicação, as diferentes restrições inseridas por cada uma das instituições deverão ser atendidas sem impedir que o software seja executado em tempo hábil.

 


Apontamentos

  • Não há apontamentos.