Algoritmo genético distribuído para problema de Timetabling / Distributed genetic algorithm for the Timetabling problem

Iago Rosa Bianquini, Osmar José Hofman da Silva, Wilson Castello Branco Neto

Abstract


Este artigo apresenta um Algoritmo Genético Distribuído para resolução do problema de Timetabling do Instituto Federal de Santa Catarina Câmpus 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 média, 26 segundos, enquanto a centralizada levou 70 segundos.


Keywords


timetabling, algoritmo genético, inteligência artificial, sistema distribuído, busca em profundidade.

References


A. Schaerf, “A survey of automated timetabling,” Artificial Intelligence Review, vol. 13, pp. 87–127, 01 1999.

R. F. Cruz, G. P. dos Santos Júnior, L. B. Fontes, M. dos Anjos Santos, and B. L. C. da Silva, “Geração automática de horário escolar com algoritmo genético,” Eixo, vol. 8, no. 2, pp. 230–241, 2019. [Online]. Available: http://revistaeixo.ifb.edu.br/index.php/RevistaEixo/article/view/565

A. Colorni, M. Dorigo, and V. Maniezzo, “Metaheuristics for high-school timetabling,” Computational Optimization and Applications, vol. 9, 04 1999.

R. Concilio, “Contribuições à solução de problemas de escalonamento pela aplicação conjunta de computação evolutiva e otimização com restrições,” Campinas, 2000.

R. Linden, Algoritmos Genéticos, 3rd ed. Rio de Janeiro: Ciência Moderna, 2012.

A. Wren, “Scheduling, timetabling and rostering—a special relationship?” in International conference on the practice and theory of automated timetabling. Springer, 1995, pp. 46–75.

E. Burke, B. Mccollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” European Journal of Operational Research, vol. 176, pp. 177–192, 01 2007.

S. Daskalaki and T. Birbas, “Efficient solutions for a university timetabling problem through integer programming,” European Journal of Operational Research, vol. 160, pp. 106–120, 01 2005.

E. K. Burke, R. Qu, and A. Soghier, “Adaptive selection of heuristics within a grasp for exam timetabling problems,” Proceedings of the 4th Multidis ciplinary International Scheduling: Theory and Applications, pp. 10–12, 2009.

A. L. Bolaji, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah, “University course timetabling using hybridized artificial bee colony with hill climbing optimizer,” Journal of Computational Science, vol. 5, no. 5, pp. 809–818, 2014.

K. Socha, J. Knowles, and M. Sampels, “A max-min ant system for the university course timetabling problem,” in International Workshop on Ant Algorithms. Springer, 2002, pp. 1–13.

S. Edelkamp and S. Schr¨odl, Heuristic Search - Theory and Applications., 1st ed. Morgan Kaufmann, 01 2012.

D. J. Montana, M. Brinn, S. Moore, and G. Bidwell, “Genetic algorithms for complex, real-time scheduling,” SMC’98 Conference Proceedings. 1998 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.98CH36218), vol. 3, pp. 2213–2218 vol.3, 1998.

S. R. Sutar and R. S. Bichkar, “High school timetabling using tabu search and partial feasibility preserving genetic algorithm,” International Journal of Advances in Engineering & Technology, vol. 10, no. 3, p. 421, 2017.

S. S. A. Alves, S. A. F. Oliveira, and R. N. A. R., A Recursive Genetic Algorithm-Based Approach for Educational Timetabling Problems. Cham: Springer International Publishing, 2017.

C. P. Borges, “Aperfeiçoamento de um algoritmo genético para elaboração de quadros de horários em instituições de ensino,” Lages, 2007, trabalho de conclusão de curso em Sistemas de Informação. Universidade do Planalto Catarinense - SC.

P. d. S. R. Ramos, “Sistema automático de geração de horários para a ufla utilizando algoritmos genéticos,” 2002, trabalho de conclusão de curso em Ciência da Computação. Universidade Federal de Lavras - MG.

P. Salza and F. Ferrucci, “Speed up genetic algorithms in the cloud using software containers,” Future Generation Computer Systems, vol. 92, 10 2018.

E. M. da Silva, “Algoritmos genéticos para geração de quadros de horários,” Lages, 2010, trabalho de conclusão de curso em Sistemas de Informação. Universidade do Planalto Catarinense - SC.

G. Luger, Inteligência artificial, 6th ed. São Paulo: Pearson Education do Brasil, 2013.




DOI: https://doi.org/10.34117/bjdv8n5-245