Aplicação de Programação Inteira na Distribuição de Encargos Didáticos em Instituições de Ensino

Authors

  • Priscila Savulski Ferreira
  • Elizabeth Wegner Karas
  • F. L. Polucoski
  • Ademir Alves Ribeiro
  • Arinei L. Silva

DOI:

https://doi.org/10.5540/tema.2011.012.02.0135

Abstract

Este trabalho propõe uma formulação matemática de programação linear binária para distribuição dos encargos didáticos em uma instituição de ensino que procura maximizar a satisfação dos professores. A formulação, em duas variantes, é implementada na designação de professores às turmas ofertadas pelo Departamento de Matemática da Universidade Federal do Paraná - UFPR. Foi desenvolvido um sistema que permite que os professores preencham on-line um questionário com suas restrições de horários e preferências por turmas. Após a coleta das informações o sistema gera as matrizes necessárias para implementar o modelo matemático. Para analisar os resultados, define-se um índice médio de satisfação dos professores.

References

[1] D. Bertsimas, J.N. Tsitsiklis, “Introduction to Linear Optimization”, Athena Scientific, USA, 1997.

[2] E.K. Burke, S. Petrovic, Recent research directions in automated timetabling, European Journal of Operational Research - EJOR, 140, No. 2 (2002), 266–280.

[3] A. Colorni, M. Dorigo, V.Maniezzo, Metaheuristics for high school timetabling, Computational Optimization and Applications, 9 (1998), 275–298.

[4] A.A. Constantino, W. Marcondes Filho, D. Landa-Silva, Iterated heuristic algorithms for the classroom assignment problem, In “Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling - PATAT”, p. 152–166, 2010.

[5] D.M.B. Costa, “Distribuição das Cargas Horárias de Professores em uma Instituição de Ensino”, Monografia do Curso de Especialização em Matemática Aplicada, UFPR, 1994.

[6] P.S. Ferreira, E.W. Karas, F.L. Palucoski, A.A. Ribeiro, A.L. Silva, Aplicação de programação inteira na distribuição de encargos didáticos em instituições de ensino, Anais do XXXIII CNMAC - Congresso Nacional de Matemática Aplicada e Computacional, Águas de Lindóia, SP, Setembro 2010.

[7] A.R.T. Góes, “Otimização na Distribuição da Carga Horária de Professores: método exato, método heurístico, método misto e interface”, Dissertação de Mestrado, UFPR, 2005.

[8] O.O. Braz Jr, “Otimização de Horários em Instituições de Ensino Superior através de Algoritmos Genéticos”, Dissertação de Mestrado, UFSC, 2000.

[9] P. Kostuch, The university course timetabling problem with a 3-phase approach, In “Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling - PATAT”, p. 251–266, 2004.

[10] E.G.S. Kotsko, “Otimização na Construção da Grade Horária Escolar: uma aplicação”, Dissertação de Mestrado, UFPR, 2003.

[11] L.L. Lapin, “Quantitative Methods for Business Decisions”, Wadsworth Publishing Company, USA, sixth edition, 1996.

[12] B. McCollum, A perspective on bridging the gap between theory and practice in university timetabling, In “Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling - PATAT”, vol. 3867, p. 3–23. Springer-Verlag Lecture Notes in Computer Science, 2006.

[13] F.L. Palucoski, “Um Sistema para Coleta e Processamento de Dados para a Distribuição de Encargos Didáticos”, Monografia do curso de Especialização para Professores de Matemática, UFPR, 2009.

[14] P.R. Pinheiro, J.A. Oliveira, Um ambiente de apoio a construção de horário escolar na WEB: modelagem, implementação e aplicação nas escolas de ensino médio, In “XXXIII Simpósio Brasileiro de Pesquisa Operacional”, Campos do Jordão, SP, 2001.

[15] H. Rudová, T.Müller, K.Murray, Complex university course timetabling, Journal of Scheduling, 2010. DOI: 10.1007/s10951-010-0171-3.

[16] H.G. Santos, “Formulações e Algoritmos para o Problema de Programação de Horários em Escolas”, Tese de Doutorado, UFF, 2007.

[17] H.G. Santos, L.S. Ochi, M.J.F. Souza, A Tabu Search heuristic with efficient diversification strategies for the class/teacher timetabling problem, ACM Journal of Experimental Algorithmics - JEA, 10, No. 2 (2006).

[18] H.G. Santos, M.J.F. Souza, Programação de horários em instituições educacionais:

formulações e algoritmos, In “XXXIX SBPO - Simpósio Brasileiro de Pesquisa Operacional”, No. 1, p. 2827–2882, Fortaleza, 2007.

[19] H.G. Santos, M.J.F. Souza, L.S. Ochi, An efficient Tabu Search heuristic for the school timetabling problem, Lecture Notes on Computer Science - LNCS, 3059 (2004), 468–482.

[20] H.G. Santos, E. Uchoa, L.S. Ochi, N. Maculan, Strong bounds with cuts and column generation for class-teacher timetabling, In “Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling - PATAT”, 2008. DOI 10.1007/s10479-010-0709-y.

[21] H.G. Santos, E. Uchoa, L.S. Ochi, N. Maculan, Strong bounds with cut and column generation for class-teacher timetabling, Annals of Operations Research, to appear.

[22] V.N. Sousa, A.C. Moretti, V.A. Podestá, Programação da grade de horário em escolas de ensino fundamental e médio, Pesquisa Operacional, 28, No. 3, (2008), 399–421.

[23] M.J.F. Souza, “Programação de Horário em Escolas: uma aproximação por metaheurísticas”, Tese de Doutorado, UFRJ, 2000.

[24] M.J.F. Souza, N. Maculan, L.S. Ochi, Uma heurística para a programação de horários em escolas, TEMA - Tend. Mat. Apl. Comput., 2, No. 1 (2001), 213–222.

[25] M.J.F. Souza, N. Maculan, L.S. Ochi, A GRASP - TABU SEARCH algorithm for solving school timetabling problems, volume 15, chapter 31, pages 659 – 672. Combinatorial Optimization Book Series, Metaheuristics: Computer Decision - Making, 2003.

Published

2011-06-01

How to Cite

Ferreira, P. S., Karas, E. W., Polucoski, F. L., Ribeiro, A. A., & Silva, A. L. (2011). Aplicação de Programação Inteira na Distribuição de Encargos Didáticos em Instituições de Ensino. Trends in Computational and Applied Mathematics, 12(2), 135–144. https://doi.org/10.5540/tema.2011.012.02.0135

Issue

Section

Original Article