TEMA Tend. Mat. Apl. Comput., 12, No. 2 (2011), 135-144. doi: 10.5540/tema.2011.012.02.0135 c Uma Publicao da Sociedade Brasileira de Matemtica Aplicada e Computacional.

Aplicao de Programao Inteira na Distribuio de Encargos Didticos em Instituies de Ensino1P.S. FERREIRA2 E.W. KARAS3 F.L. PALUCOSKI4 A.A. RIBEIRO5 Depar, , , , tamento de Matemtica, UFPR - Universidade Federal do Paran, Cx.P. 19081, 81531-980, Curitiba, PR, Brasil. A.L. SILVA6 Departamento de Engenharia de Produo, UFPR - Universi, dade Federal do Paran, 81531-980 Curitiba, PR, Brasil.

Resumo. Este trabalho prope uma formulao matemtica de programao linear binria para distribuio dos encargos didticos em uma instituio de ensino que procura maximizar a satisfao dos professores. A formulao, em duas variantes, implementada na designao de professores s turmas ofertadas pelo Departamento de Matemtica da Universidade Federal do Paran - UFPR. Foi desenvolvido um sistema que permite que os professores preencham on-line um questionrio com suas restries de horrios e preferncias por turmas. Aps a coleta das informaes o sistema gera as matrizes necessrias para implementar o modelo matemtico. Para analisar os resultados, dene-se um ndice mdio de satisfao dos professores. Palavras-chave. Modelagem matemtica, programao linear inteira, distribuio de encargos didticos.

1.

Introduo

As instituies de ensino precisam a cada perodo letivo estabelecer os horrios das aulas e designar um professor para cada turma, procurando satisfazer as necessidades pedaggicas e as preferncias individuais dos professores. Esta rdua tarefa, realizada, na maioria das instituies, manualmente, insere-se no contexto de problemas de designao [11]. O problema no novo, mas devido s particularidades de cada instituio, assume nuances diferentes. Em [18], os autores apresentam os principais tipos de problemas de programao de horrios em instituies de ensino. Em escolas de ensino fundamental e mdio, normalmente, necessrio elaborar a1 Edital 2 pri.savulski@hotmail.com.

Universal CNPq 476043/2009-3 Bolsista CNPq pelo Programa de Ps-Graduao em Matemtica

Aplicada 3 ewkaras@ufpr.br. Bolsista Produtividade CNPq 4 felipe.palucoski@gmail.com. Especializao para Professores de Matemtica da UFPR 5 ademir.ribeiro@ufpr.br 6 arinei@ufpr.br

Recebido em 14 Junho 2010; Aceito em 23 Outubro 2010.

136

Ferreira et al.

grade horria de disciplinas de cada turma levando em considerao a disponibilidade de horrio dos professores. Neste contexto, [5, 10, 20, 21] sugerem uma formulao matemtica com variveis binrias que prioriza a satisfao dos professores. As principais diculdades esto relacionadas com o tratamento das informaes a serem consideradas na formulao e com o tempo computacional, o que motiva o uso de heursticas. Em [3], os autores comparam solues fornecidas atravs de mtodos heursticos: Simulated Annealing, Busca Tabu [17, 19, 22] e Algoritmos Genticos, enquanto em [24, 25], o problema resolvido atravs do procedimento GRASP (Greedy Randomized Adaptive Search Procedures) com renamento atravs de Busca Tabu. Uma heurstica de busca local baseada em caminhos mnimos desenvolvida em [23]. Mtodo exato e heursticos so comparados em [7] e a sinergia entre eles explorada em [16]. Um ambiente de apoio construo de horrio escolar pela internet apresentado em [14]. Em instituies de ensino superior h o problema de programao de horrios de cursos (course timetabling) que envolve tanto a denio do horrio das aulas quanto das salas em que essas aulas sero ministradas [4, 9, 15]. Fixados os horrios das aulas, precisa-se, ento, designar professores para cada turma atendendo restries de carter pedaggico e de preferncia dos professores [2, 12]. Em [8], o autor aborda o problema por Algoritmo Gentico e elabora uma interface para que a modelagem possa ser aplicada em outras instituies. Este trabalho [6] prope uma formulao matemtica de programao linear binria para designao de professores s turmas em instituies em que os horrios das turmas so preestabelecidos, como o caso do Departamento de Matemtica da Universidade Federal do Paran - UFPR. Cabe observar que uma mesma disciplina pode ser ofertada em diferentes horrios para diferentes cursos. Cada horrio semanal xado para cada disciplina ofertada pelo Departamento caracteriza uma turma. possvel adaptar a formulao proposta para outros departamentos e instituies. Na Seo 2. apresenta-se a formulao bsica. O sistema para coleta e gerenciamento das informaes discutido na Seo 3.. Discute-se na Seo 4. uma variante da formulao bsica que resolve o problema em duas fases. Na primeira, procura-se minimizar o nmero de turmas atribudas a professores que no tinham preferncia por elas. Na segunda fase, xa-se esse nmero e maximiza-se a satisfao geral dos professores. Para facilitar a comparao dos resultados dene-se um ndice mdio de satisfao. A formulao, em suas duas variantes implementada e testada. Os resultados so discutidos na Seo 5..

2.

Formulao Bsica

Considere que T turmas devem ser distribudas para P professores em H horrios ao longo de D dias semanais. A varivel de deciso binria x(p, t) representa a atribuio professor - turma, ou seja, para todo p = 1, . . . , P e t = 1, . . . , T , denese: 1, se o professor p assume a turma t, x(p, t) = 0, caso contrrio. A carga horria de cada professor p deve estar compreendida entre um valor

Distribuio de Encargos Didticos

137

mnimo Hmin (p) e um valor mximo Hmax (p) denidos pela instituio. Note que se a carga horria semanal de um professor xa, os valores mnimo e mximo coincidem. Os horrios de cada turma so xados e armazenados da seguinte forma: HT (t, h, d) = 1, se a turma t tem aula no horrio h do dia d, 0, caso contrrio.

Cada professor p atribui um peso e(p, t) pela preferncia em assumir a turma t. Para turmas que o professor no gostaria de lecionar, considera-se peso nulo. O objetivo do modelo maximizar a satisfao total dos professores dada porP T

S=p=1 t=1

e(p, t) x(p, t).

(2.1)

A formulao bsica considerada descrita abaixo:P T

maximizarp=1 t=1 T

e(p, t) x(p, t)

(2.2)

sujeito at=1

HT (t, h, d) x(p, t) 1,P

para todo p, d, h, (2.3) para todo t, (2.4)

x(p, t) = 1,p=1 T H D

HT (t, h, d) x(p, t) Hmin (p),t=1 h=1 d=1 T H D

para todo p,

(2.5) (2.6) (2.7)

HT (t, h, d) x(p, t) Hmax (p), para todo p,t=1 h=1 d=1

x(p, t) = {0, 1},

para todo p, t.

As restries (2.3) exigem que cada professor no pode assumir mais do que uma turma num mesmo horrio de um determinado dia. As restries (2.4) garantem que nenhuma turma car sem professor. O conjunto de restries (2.5) e (2.6) impem, como j dito anteriormente, que a carga horria semanal de cada professor deve estar compreendida entre valores mnimos e mximos. Finalmente, (2.7) denem as variveis como binrias. A formulao matemtica proposta de programao linear inteira binria [1, 11] pode ser resolvida com o auxlio do software LINGO.

3.

Coleta dos Dados

O armazenamento das informaes para alimentar o modelo foi feito de forma computacional. As informaes dos horrios das turmas vm do prprio sistema de

138

Ferreira et al.

abertura de turmas pela instituio. Foi desenvolvido um sistema [13] que disponibiliza os horrios das turmas e possibilita aos professores preencher um formulrio on line com suas preferncias. Tal sistema foi implementado em PHP - Hipertext Preprocessor que uma linguagem de programao para criao e gerenciamento de pginas dinmicas na Web. Inicialmente, o professor indica os horrios semanais em que no pode assumir aulas. Assim, automaticamente o sistema zera as variveis de deciso x(p, t) para toda turma t em horrio incompatvel com o horrio do professor. Com isto, a quantidade de variveis do problema reduz signicativamente e no h risco de atribuir ao professor uma turma que ele no possa assumir. Em seguida, o sistema apresenta ao professor p apenas as turmas compatveis com sua disponibilidade de horrio para este marcar suas turmas preferidas. O professor deve, ento, atribuir um peso a cada turma, de forma a reetir sua preferncia em ministrar aula para aquela turma. O peso e(p, t) varia do valor 0, situao em que o professor p no tem interesse algum em ministrar aula para a turma t, at o valor 5, caso que indica a maior preferncia. Destaca-se que um professor pode atribuir uma mesma preferncia para vrias turmas. O fato de o professor no ter interesse em ministrar uma turma no indica que ele no pode assum-la. Aps o preenchimento dos formulrios, o sistema gera automaticamente as matrizes para alimentar o modelo. Ou seja, o sistema xa em zero a varivel x(p, t) para toda turma t em horrio que o professor p, por razes particulares, no pode assumir aula e gera as seguintes matrizes: HT de dimenso T H D, cujo elemento HT (t, h, d) 1 se a turma t tem aula no horrio h do dia d; caso contrrio, HT (t, h, d) = 0. Hmin e Hmax de dimenses P 1, cujos elementos Hmin (p) e Hmax (p) representam a carga horria semanal mnima e mxima, respectivamente, do professor p. e de dimenso P T , cujo elemento e(p, t) {5, 4, 3, 2, 1, 0} representa o peso de preferncia que o professor p tem pela turma t.

4.

Discusso sobre a Formulao

Discute-se nesta seo algumas particularidades na resoluo da formulao bsica e uma forma de analisar o resultado obtido.

4.1.

Formulao em duas fases

Algumas turmas podem no ter sido escolhidas por nenhum professor, ou seja, pode existir alguma turma t para a qual e(p, t) nula para todo professor p. Embora ningum tenha interesse em assum-la, ela precisa ser ofertada e consequentemente, atribuda a algum professor. Mesmo que no haja turmas nesta situao, ao procurar atender as restries do problema, algumas turmas devero ser designadas a professores que no tm qualquer preferncia por elas. Alm disso, maximizar a satisfao total pode fazer com que, em favor da coletividade, o nmero de turmas

Distribuio de Encargos Didticos

139

nesta situao aumente. A m de minimizar este nmero, foram consideradas duas fases na resoluo do problema. Na primeira, considera-se as restries da formulao bsica com o objetivo de minimizar o nmero de turmas atribudas com satisfao nula, o que resulta em um certo nmero N . Na segunda fase, resolve-se o modelo bsico com a restrio adicional de que o total de turmas atribudas a professores com preferncia nula seja N . Com essa estratgia consegue-se maximizar a satisfao global dos professores para todos os possveis conjuntos de N turmas advindas da primeira fase. Primeira fase. O objetivo da primeira fase minimizar a quantidade de turmas designadas a professores sem que eles as tenham escolhido. Para tanto consideramse variveis auxiliares r(p, t) denidas por r(p, t) = x(p, t) 1 min{1, e(p, t)} . (4.1)

Note que r(p, t) = 1 quando a turma t atribuda a um professor p que no tem interesse em assum-la e vale zero nos demais casos. O ideal que r(p, t) seja sempre nula, o que nem sempre possvel. A soma destas variveis quantica o nmero de turmas que so atribudas a um professor que no a tinha escolhido. esta soma que deseja-se minimizar. Assim, na primeira fase resolvemos o problema de minimizarP T

r(p, t)p=1 t=1

com as restries da formulao bsica discutida na Seo 2.. A resoluo deste problema fornece um nmero mnimo N de turmas que tero que ser atribudas a professores que no tem qualquer preferncia em assum-las. Segunda fase. Na segunda fase, procura-se maximizar a satisfao dos professores tendo em vista que N turmas tero que ser assumidas por professores que no as solicitaram. Resolve-se ento o problema de maximizar a satisfao dos professores (2.1) com as restries da formulao bsica e a restrio adicional de que a quantidade de turmas atribudas a professores que no tem qualquer preferncia em assum-las seja N , ou seja,P T

r(p, t) = N.p=1 t=1

Resolvendo-se o problema nestas duas fases, maximiza-se a satisfao global dos professores tomando-se o cuidado de minimizar o nmero de professores insatisfeitos por assumir turmas que no haviam solicitado.

4.2.

Disciplinas especcas

Em cada instituio existem, normalmente, disciplinas do ciclo bsico que podem ser ministradas por qualquer professor e disciplinas do ciclo especco que devem ser ministradas por especialistas da rea. Turmas correspondentes a disciplinas do

140

Ferreira et al.

ciclo especco devem ser atribudas a professores que se sintam confortveis em ministr-las e portanto as tenham colocado entre suas preferncias. Assim, para toda turma t que a critrio da instituio seja considerada do ciclo especco e que tenha sido escolhida por algum professor, ou seja, tenha e(p, t) = 0 para algum p, acrescentamos formulao bsica a restrioP

r(p, t) = 0,p=1 e(p,t)=0

para toda turma t tal que esp(t) = 1

onde r(p, t) denido em (4.1) e esp(t) = 1, se a turma t do ciclo especco, 0, caso contrrio.

Estas restries impem que toda turma t do ciclo especco deve ser atribuda a algum que tenha interesse em ministr-la. As restries de disciplinas especcas podem ser acrescentadas na formulao bsica independentemente se o problema resolvido em uma ou duas fases.

4.3.

ndice de satisfao

Para facilitar a anlise dos resultados obtidos, considera-se um ndice de satisfao mdio dos professores. Suponha que ao professor p foram atribudas q(p) turmas no necessariamente as de sua mxima preferncia. Por outro lado, considere que as q(p) turmas de sua mxima preferncia sejam t1 , t2 , . . . , tq(p) . O ndice individual de satisfao do professor p dado por:T

e(p, t)x(p, t) I(p) =t=1 q(p)

. e(p, tj )

(4.2)

j=1

Note que I(p) a razo entre a soma dos pesos das q(p) turmas designadas ao professor p, e o peso mximo se as q(p) turmas designadas a ele fossem as de sua maior preferncia. Este ndice est entre 0 e 1. ndice unitrio signica que as turmas atribudas ao professor so as de sua preferncia. O ndice nulo no caso extremo em que so atribudas ao professor apenas aulas que ele no havia escolhido, mas que se encaixam no seu horrio. A mdia dos ndices I(p) fornece o ndice de satisfao mdio dos professores, ou seja, I= 1 PP

I(p).p=1

(4.3)

Distribuio de Encargos Didticos

141

5.

Aplicao

No Departamento de Matemtica da UFPR, a cada semestre so distribudas a cerca de 50 professores em torno de 100 turmas, com carga horria semanal de 3, 4 ou 6 horas. O rduo trabalho de distribuio das turmas era feito, at ento, de forma manual por uma comisso que analisava a preferncia e disponibilidade de horrio de cada professor. A formulao sugerida neste trabalho foi aplicada na distribuio dos encargos didticos do primeiro e do segundo semestre de 2010 do Departamento de Matemtica da UFPR, onde foram distribudas T = 103 turmas de graduao no primeiro semestre e T = 94 no segundo semestre para P = 44 professores em H = 15 horrios em cada um dos D = 5 dias semanais. Os problemas foram resolvidos em um computador Core 2 duo 8500, 2.27 GHz com 4Gb de memria RAM e Windows XP, com o auxlio do software LINGO 9. Anlise dos resultados. Os problemas foram resolvidos de duas formas. Primeiro, atravs da formulao bsica descrita na Seo 2.. Em seguida, pela decomposio em duas fases descrita na Seo 4.. A tabela a seguir sintetiza os resultados obtidos. A coluna S fornece a satisfao global dos professores dada por (2.1), enquanto a coluna seguinte apresenta o ndice de satisfao mdio dado por (4.3). Por outro lado, a penltima coluna fornece o nmero N de turmas designadas a professores que no as solicitaram. Finalmente, a ltima coluna d o tempo computacional, em segundos, gasto para resolver cada um dos problemas. Tabela 1: Resultados Semestre Primeiro Primeiro Segundo Segundo Formulao Bsica Duas fases Bsica Duas fases S 394 363 373 368 I 0,8252 0,7477 0,8155 0,8064 N 13 7 12 8 CPU 8 16 8 22

A satisfao global e o ndice de satisfao mdio so maiores quando o problema resolvido atravs da formulao bsica em uma nica fase. Por outro lado, em favor da coletividade, mais turmas so atribudas a professores que no as solicitaram. Note que, embora os problemas sejam resolvidos por mtodo exato, o tempo computacional baixo. Foi feita tambm uma interface grca com o auxlio do software Visual Basic, que transforma a resposta fornecida das turmas atribudas a cada professor em planilhas e tabelas que podem ser facilmente analisadas pela instituio. Aps a anlise dos resultados, adotou-se a soluo fornecida pela resoluo em duas fases que se preocupa em reduzir o nmero de professores insatisfeitos. Uma crtica ao resultado de que alguns professores caram com turmas espalhadas pela semana com grandes janelas durante o dia. Deve-se, num prximo trabalho, melhorar a formulao de modo a reduzir tais situaes, procurando con-

142

Ferreira et al.

centrar os horrios de aulas de cada professor. Alm disso, pretende-se equilibrar os ndices de satisfao individual.Abstract. We propose a binary linear programming model to distribute the classes to the instructors maximizing their satisfaction. The model was implemented for distributing the classes to the professors of Department of Mathematics at Federal University of Paran. We also developed an on-line system where the professors inform their unavailable work time and their preferred classes. After having all information the system generates the matrices to implement the model. In order to analyze the results we dene a mean satisfaction index.

Referncias[1] D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientic, USA, 1997. [2] E.K. Burke, S. Petrovic, Recent research directions in automated timetabling, European Journal of Operational Research - EJOR, 140, No. 2 (2002), 266280. [3] A. Colorni, M. Dorigo, V. Maniezzo, Metaheuristics for high school timetabling, Computational Optimization and Applications, 9 (1998), 275298. [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. 152166, 2010. [5] D.M.B. Costa, Distribuio das Cargas Horrias de Professores em uma Instituio de Ensino, Monograa do Curso de Especializao em Matemtica Aplicada, UFPR, 1994. [6] P.S. Ferreira, E.W. Karas, F.L. Palucoski, A.A. Ribeiro, A.L. Silva, Aplicao de programao inteira na distribuio de encargos didticos em instituies de ensino, Anais do XXXIII CNMAC - Congresso Nacional de Matemtica Aplicada e Computacional, guas de Lindia, SP, Setembro 2010. [7] A.R.T. Ges, Otimizao na Distribuio da Carga Horria de Professores: mtodo exato, mtodo heurstico, mtodo misto e interface, Dissertao de Mestrado, UFPR, 2005. [8] O.O. Braz Jr, Otimizao de Horrios em Instituies de Ensino Superior atravs de Algoritmos Genticos, Dissertao 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. 251266, 2004. [10] E.G.S. Kotsko, Otimizao na Construo da Grade Horria Escolar: uma aplicao, Dissertao de Mestrado, UFPR, 2003.

Distribuio de Encargos Didticos

143

[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. 323. Springer-Verlag Lecture Notes in Computer Science, 2006. [13] F.L. Palucoski, Um Sistema para Coleta e Processamento de Dados para a Distribuio de Encargos Didticos, Monograa do curso de Especializao para Professores de Matemtica, UFPR, 2009. [14] P.R. Pinheiro, J.A. Oliveira, Um ambiente de apoio a construo de horrio escolar na WEB: modelagem, implementao e aplicao nas escolas de ensino mdio, In XXXIII Simpsio Brasileiro de Pesquisa Operacional, Campos do Jordo, SP, 2001. [15] H. Rudov, T. Mller, K. Murray, Complex university course timetabling, Journal of Scheduling, 2010. DOI: 10.1007/s10951-010-0171-3. [16] H.G. Santos, Formulaes e Algoritmos para o Problema de Programao de Horrios em Escolas, Tese de Doutorado, UFF, 2007. [17] H.G. Santos, L.S. Ochi, M.J.F. Souza, A Tabu Search heuristic with ecient diversication 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, Programao de horrios em instituies educacionais: formulaes e algoritmos, In XXXIX SBPO - Simpsio Brasileiro de Pesquisa Operacional, No. 1, p. 28272882, Fortaleza, 2007. [19] H.G. Santos, M.J.F. Souza, L.S. Ochi, An ecient Tabu Search heuristic for the school timetabling problem, Lecture Notes on Computer Science - LNCS, 3059 (2004), 468482. [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, Programao da grade de horrio em escolas de ensino fundamental e mdio, Pesquisa Operacional, 28, No. 3, (2008), 399421. [23] M.J.F. Souza, Programao de Horrio em Escolas: uma aproximao por metaheursticas, Tese de Doutorado, UFRJ, 2000.

144

Ferreira et al.

[24] M.J.F. Souza, N. Maculan, L.S. Ochi, Uma heurstica para a programao de horrios em escolas, TEMA - Tend. Mat. Apl. Comput., 2, No. 1 (2001), 213222. [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.