Vinícius Lima Silva*
João Bosco Ribeiro do Val*
e-mail: [email protected], [email protected]
*DEPARTAMENTO DE TELEMÁTICA, FACULDADE DE ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
Apoio: SAE – Serviço de Apoio ao Estudante
Palavras-chave: Alocação de Carga Didática – Otimização Combinatória – Algoritmo do Leilão
Introdução
A cada semestre a FEEC deve atender a uma média
de 71 turmas em nível de graduação, contando para isso
com cerca de 85 docentes. O processo de distribuir os
professores por essas turmas é regulamentado por uma
resolução interna da faculdade¹ e vem sendo feito
manualmente
pelo
coordenador
de
graduação,
responsável pela alocação de carga didática. Com o
objetivo de facilitar o trabalho da coordenadoria de
graduação da faculdade, passamos a estudar uma forma
de automatizar a distribuição semestral de disciplinas.
Metodologia
A FEEC já dispunha de um banco de dados, em
planilhas de formato Excel, referentes aos critérios
utilizados na distribuição de carga didática, como o perfil
didático dos professores e o histórico de disciplinas
lecionadas. Desse modo, apesar do maior custo
computacional envolvido, optamos por manter esse
formato de armazenamento, por ser de mais fácil
manipulação por parte dos funcionários da coordenadoria
de graduação.
O algoritmo foi desenvolvido em linguagem Matlab e
procurou-se criar uma interface de uso simples: para
distribuir as disciplinas, o operador deve apenas
certificar-se de que os dados estão adequadamente
formatados e inserir o semestre para o qual a alocação
será feita.
Primeiramente desenvolvemos um algoritmo capaz
de importar os dados da coordenadoria de graduação e
agregá-los em uma estrutura mais amigável à
manipulação no Matlab, como mostrado no bloco abaixo.
apelido: `joão'
nome: `JOÃO DA SILVA'
perfil didático: {{1x2 cell} ... {1x5 cell}}
disciplinas lecionadas: {`EAXXX' ... `EEXXX'}
contador disciplinas lecionadas: [4 ... 2]
cargas noturnas: 6
preferencias semestrais: {`EAXXX' ... `EAXXX'}
disciplina ultimo semestre: `EAXXX'
contador disciplina ultimo semestre: 2
Com as informações agregadas em um conjunto de
blocos como o indicado, podemos partir para a
modelagem dos critérios de alocação. Considerando a
resolução da FEEC, busca-se alocar cada professor na
disciplina em que ele possui maior prioridade e, caso o
professor tenha demonstrado interesse em lecionar uma
disciplina específica, naquela de seu interesse. Tais
informações são de posse da CG e são indicadas no bloco
acima por ‘perfil didático’ e ‘preferências semestrais’,
respectivamente. A esses critérios principais somam-se
outros, como a quantidade de disciplinas lecionadas em
período noturno e o histórico de disciplinas ministradas.
Com base nessas informações, podemos modelar a
alocação de cargas didáticas como um problema de
associação. A cada possível par (professor, disciplina),
podemos atribuir um índice de satisfação pessoal que
reflita o grau de satisfação do docente em lecionar aquela
disciplina e buscamos obter a alocação que ofereça o
melhor índice de satisfação total.
A satisfação de cada professor pode ser calculada,
para cada disciplina, como a soma dos pesos indicados na
tabela 1, que indica os principais critérios de alocação.
Posteriormente
são
calculados
eventuais
ajustes
baseados nas demais normas da Comissão de Graduação
da faculdade, como o critério de desempate para
disciplinas lecionadas em período noturno.
Após o cálculo e ajuste dos índices de satisfação, é
montada uma matriz contendo os professores aptos a
lecionar, as disciplinas a serem ofertadas no semestre
para o qual a carga será distribuída e os índices de
satisfação correspondentes a cada possível associação
(professor, disciplina), como indicado na Tabela 2.
Professores/Disciplinas
A
B
C
D
E
[...]
EAXXX EEXXX ETXXX EEXXX [...]
12
12
-100
-100
-100
-100
-100
-100
24
36
-100
-100
-100
40
-100
-100
-100
-100
-100
-100
Tabela 2: exemplo de matriz professores x disciplinas com índices de satisfação calculados.
A partir dos dados da Tabela 2, precisa-se
encontrar a associação que forneça a melhor satisfação
total dos docentes. Dentre os algoritmos para problemas
de associação existentes na literatura, optou-se por
trabalhar com o Algoritmo do Leilão², desenvolvido por
Dimitri P. Bertsekas.
Perfil
3 vezes
h0
Perfil 1
p1
Preferências
semestrais
Pref. 1
s1
2 vezes
1 vez
2h0/3
h0/3
Perfil 2
Perfil 3
p2
p3
Pref. 2
Pref. 3
s2
s3
Testamos ainda valores mais altos para a
diferença entre os pesos, como mostrado no Gráfico
3. Os resultados obtidos, entretanto, mantiveram-se
praticamente os mesmos. Optamos assim por adotar
a diferença entre os pesos igual a 12, o que leva a
resultados satisfatórios, como indicado nos Gráficos 1
e 2.
Resultados e Discussão
Para
avaliar
a
qualidade
do
algoritmo
desenvolvido, simulamos distribuições de cargas para
semestres anteriores e verificamos a quantidade de
professores alocados em cada nível de preferência e
perfil didático.
Para os pesos inicialmente adotados, obtivemos
resultados já satisfatórios, com cerca de 58% dos
professores alocados em disciplinas do seu primeiro
nível de desejo e cerca de 90% dos professores
alocados em disciplinas do primeiro nível do seu perfil
didático. Em seguida alteramos progressivamente o
valor dos pesos atribuídos às componentes dos índices
de satisfação e avaliamos a mudança na quantidade de
professores alocados em cada nível de perfil didático e
preferência semestral.
De modo geral, observamos que a quantidade de
professores alocados nos níveis mais altos da
preferências didáticas depende mais da diferença entre
os pesos do que dos valores absolutos. Dessa forma
nos focamos em alterar a diferença entre os pesos,
como indicado nos Gráficos 1 e 2.
Gráfico 3: Porcentagem de professores alocados nos primeiros
níveis de preferência semestral e perfil didático x diferença atribuída
aos diferentes níveis das componentes dos índices de satisfação mostradas
na Tabela 1
Conclusões
O programa desenvolvido ao longo desse projeto
apresentou resultados satisfatórios à problemática
proposta. As alocações de carga obtidas pelo algoritmo,
como discutido na seção anterior, obtiveram bons índices
de professores alocados às disciplinas pelas quais
demonstraram maior interesse e a automatização
oferecida pelo programa evita um trabalho exaustivo por
parte do coordenador de graduação.
Agradecimentos
Ao SAE – Unicamp e ao DT – FEEC.
Referências Bibliográficas
¹Resolução CG/FEEC 03: Alocação de Carga Didática
na FEEC. FEEC, Unicamp, 1993. Disponível em:
http://www.fee.unicamp.br/cg/.
² Bertsekas, Dimitri P. Auction Algorithms for Network
Flow Problems: A Tutorial Introduction. In: Bertsekas,
Dimitri
P.,
Computational
Optimization
and
Applications, Vol. 1, pp. 7-66, 1992.
Tabela 1: Resumo dos pesos
Histórico
Gráfico 2: Porcentagem de professores alocados nos diferentes
níveis de perfis didáticos x diferença atribuída aos diferentes níveis
das componentes dos índices de satisfação mostradas na Tabela 1..
Gráfico 1: Porcentagem de professores alocados nos diferentes níveis de
preferências semestrais (desejos) x diferença atribuída aos diferentes níveis
das componentes dos índices de satisfação mostradas na Tabela 1..