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.

Downloads

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

Vol. 12 No. 2 (2011)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.