APLICAÇÃO DE ALGORITMOS GENÉTICOS E MÉTODOS EVOLUCIONÁRIOS NA RESOLUÇÃO DO PROBLEMA DE ALOCAÇÃO DE TURMAS: CASO UFPR.

APLICAÇÃO DE ALGORITMOS GENÉTICOS E MÉTODOS EVOLUCIONÁRIOS NA RESOLUÇÃO DO PROBLEMA DE ALOCAÇÃO DE TURMAS: CASO UFPR.

Souza, Pablo Leonn Baptistello de; Scarpin, Cassius Tadeu

Artigo:

Esse artigo apresenta uma adaptação do algoritmo genético na resolução do problema de alocação de turmas no campus Politécnico da Universidade Federal do Paraná. Para tanto, foram analisados diversos métodos, sendo o escolhido, devido sua eficiência e adaptabilidade, o algoritmo genético. O algoritmo desenvolvido, além de ser testado com dados reais e atuais da instituição, foi comparado com o processo atual aplicado no campus, obtendo resultados mais satisfatórios em relação ao mesmo. O sistema criado conseguiu alocar, através da inserção de novos conceitos e adaptações nos operadores genéticos do algoritmo genético clássico, 1348 turmas em 58 salas em diversos períodos e dias da semana de forma rápida e eficiente em função das restrições e particularidades do problema.

This paper presents an adaptation of genetic algorithm in solving the problem of allocating classes at the Polytechnic campus of the Federal University of Paraná. Therefore, several methods were analyzed, wherein the chosen was, because of their efficiency and adaptability, the genetic algorithm. The developed algorithm, in addition to being tested with real and current data of the institution, was compared with the current process applied on the campus, obtaining more satisfactory results compared to the same. The created system managed to allocate, by the insertion of new concepts and adaptations of the genetic operators of the classic genetic algorithm, 1348 classes in 58 rooms at different times and days of the week quickly and efficiently in function of the restrictions and particularities of the problem.

Palavras-chave:

DOI: 10.5151/marine-spolm2014-126518

Referências bibliográficas

• [1] ABRAMSON, D. Constructing School timetables using simulated annealing: sequential and parallel algorithms. Management Science, vol.37, pp. 98–113. 1991.
• [2] BATTERSBY, A.; EL-MIHOUB, T. A.; HOPGOOD, A. A.; NOLLE, L. Hybrid Genetic Algorithms: A Review. 2006. http://www.engineeringletters.com/issues_v13/issue_2/EL_13_2_11.pdf. Acessado em 15/04/2014 21:59.
• [3] BELIGIANNIS, G. N.; MOSCHOPOULOS, C. N.; KAPERONIS G. P.; LIKOTHANASSIS S. D. Applying evolutionary computation to the school timetabling problem: The Greek case. Computers Andamp; Operations Research, vol. 35, no. 4, pg. 1265-1280, 2008.
• [4] BLAS, L. E. A.; SANZ, S. S.; GARCÍA, E. G. O.; FIGUERAS, A. P.; BELLIDO, Á. M. P. A hybrid grouping genetic algorithm for assigning students to preferred laboratory groups. Expert Systems with Applications, vol. 36, no. 3, pg. 7234 -7241, 2009.
• [5] COLORNI, A; IRIDA, M; MANIEZZO V. Metaheuristics for High School Timetabling. Computational Optimization and Applications, vol. 9, no. 3, pg.275-298, 1998.
• [6] COSTA, D. A tabu search algorithm for computing an operational timetable. European Journal of Operational Research, vol. 76, no. 1, pg. 98–110. 1994.
• [7] DUAN, Y.; ZHONG, Y.; LI, Y. Application Research on FSDM-based GA in Optimizing Curriculum Schedule Model in Universities. Information and Engineering, vol.4, no.2, pg.217-228, 2012.
• [8] GOLDBERG, D. E. Genetic algorithms in search, optimization and machine learning. Massachusetts: Addison-Wesley; 1989. 412 páginas.
• [9] MELANIE, M. An Introduction to Genetic Algorithms. MA: A Bradford Book The MIT Press; 1999, 158 páginas. https://svn-d1.mpi-inf.mpg.de/AG1/MultiCoreLab/papers/ebook-fuzzy-mitchell-99.pdf. Acessado em 15/04/2014 21:59.
• [10] MOZOS, R. S.; SANZ, S. S.; CUMPLIDO, M. D.; CALZON, C. B. A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university. Computers and Operations Research, vol. 32, no. 7, pg.1761-1776. 2005.
• [11] SCHAERF, A. A survey of automated. Artificial Intelligence Review, vol.13, no.2, pg.87-127. 1999.
• [12] STEINER, M. T. A. Meta-Heurísticas em Pesquisa Operacional. 1 ed. Curitiba - PR: Omnipax Editora Ltda, v. 1, p. 21-31. 2013.
• [13] VALOUXIS, C.; HOUSOS, E. Constraint programming approach for school timetabling. Computers Andamp; Operations Research, vol.30, no.10, pg. 1555–1572. 2003.

Como citar:

Souza, Pablo Leonn Baptistello de; Scarpin, Cassius Tadeu; "APLICAÇÃO DE ALGORITMOS GENÉTICOS E MÉTODOS EVOLUCIONÁRIOS NA RESOLUÇÃO DO PROBLEMA DE ALOCAÇÃO DE TURMAS: CASO UFPR.", p-625-636. In: Anais do XVII Simpósio de Pesquisa Operacional e Logística da Marinha - SPOLM 2014. São Paulo: Blucher, 2014.
ISSN 21756295, DOI 10.5151/marine-spolm2014-126518