X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
ALOCAÇÃO DE PROFESSORES EM INSTITUIÇÕES DE ENSINO
SUPERIOR: UM MODELO MATEMÁTICO PARA O PROBLEMA DE
ÚNICO CAMPUS E PARA O MULTICAMPI
Braulio Lara
Universidade Federal de Minas Gerais
[email protected]
RESUMO
Esse artigo descreve dois modelos otimização para a resolução do problema de
alocação de professores em instituições de ensino superior brasileiras. Diversos trabalhos sobre
timetabling ou criação de quadros de horários são encontrados na literatura. A característica
principal dessa abordagem é que baseado em parâmetros definidos na legislação brasileira e em
aspectos de gestão administrativo-financeira define-se um modelo capaz de indicar uma alocação
eficiente e eficaz, respeitando as exigências legais e critérios de qualidade, tornando-se uma
ferramenta útil, principalmente para instituições privadas, as quais se sustentam com recursos
próprios, para definição do quadro de horários. O modelo é estruturado a partir de um processo
pré-definido para a construção de quadro de horários, atuando na última fase para realizar a
alocação de professores. Ao final são apresentados testes de instâncias reais em softwares de
otimização comerciais.
Palavras Chave: quadros de horários, alocação de professores, gestão educacional.
Área: Otimização Combinatória.
ABSTRACT
This paper describes two optimization models to solve the problem of teacher allocation
in brazilian institutions of superior education. A wide variety of works on timetabling are found
in the literature. The main characteristic of this work is that it is based in parameters defined in
the brazilian legislation and in aspects of administrative and financial management. The model is
capable to indicate an efficient allocation, respecting the legal requirements and quality
parameters, becoming a useful tool, mainly for private institutions, who has to support with its
own resources, to define the timetable. The model is structured based on a process for
constructing timetables, running in the final stage to get the teacher allocation. At the end, results
of tests with real instances in commercial optimization softwares are showed.
Key Words: timetabling, teacher allocation, educational management.
XXXIX SBPO
[1783]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
1 – Introdução
O problema de alocação de professores é um dos tipos de problema de timetabling.
Diversos tipos são abordados na literatura, bem como as estratégias para sua solução [16][18]. Os
problemas de timetabling possuem uma estrutura básica que tem como característica evitar
colisões nos horários e nas disponibilidades dos recursos envolvidos no escalonamento. Essas
restrições, conhecidas como restrições difíceis, são aquelas que não permitem que um mesmo
professor seja designado a lecionar em duas turmas ao mesmo tempo, que uma turma não tenha
duas ou mais aulas ao mesmo tempo ou que uma sala não seja alocada para duas ou mais turmas
ao mesmo tempo. Os problemas de timetabling possuem um aspecto combinatório e pertencem à
classe NP[9][11]. Outros tipos de restrição, denominadas restrições desejáveis, são evitar
deslocamentos de estudantes de uma sala, atender preferências docentes, etc.
Devido a grande número de instituições de ensino e as diversas peculiaridades de cada
uma, é impossível estabelecer um modelo único capaz de atender todos os casos. Visto isso,
existe uma grande variedade de modelos de timetabling que trabalham situações específicas para
cenários distintos, mesmo porque, os objetivos a serem otimizados são de difícil mensuração
[7][17]. São objetivos comuns a maximização do atendimento de preferências docentes e a
minimização de conflitos nos horários desejados pelos alunos e janelas de tempo.
O objetivo desse trabalho é apresentar dois modelos de otimização para o problema de
alocação de professores, sendo um aplicável para o cenário com um único campus e o outro para
o cenário multicampi. A utilidade dos modelos tem um foco direcionado para as instituições de
ensino superior privadas brasileiras visto que toda a fundamentação é balizada na legislação
brasileira vigente [2][3][4][5] e os aspectos econômicos da gestão de instituições particulares
passam pelas questões de eficiência operacional da alocação dos seus recursos.
Na seção 2, é feita uma definição do problema. Na seção 3, é feita uma explanação
sintética da legislação específica que deverá ser utilizada na formulação. Já na seção 4, é proposta
a modelagem matemática do problema para um único campus. Na seção 5 é definido o modelo
multicampi e na seção 6 são reportados alguns testes realizados. Por fim, na seção 7 é apresentada
a conclusão sobre o trabalho.
2 – Definição do Problema
O processo de elaboração de um quadro de horários em uma instituição de ensino é uma
atividade estrutural. Essa atividade pode ser organizada em fases tal que ao final, tem-se como
resultado o quadro de horários construído.
Para o caso das instituições de ensino superior particulares, as quais adotam normalmente
currículos rígidos, ou seja, o aluno é obrigado a seguir uma seqüência de disciplinas obrigatórias,
com pré-requisitos e pouca flexibilidade para disciplinas do tipo optativas ou eletivas, até sua
formação, o processo para elaboração de um quadro de horários pode ser estruturado como um
processo que ocorre em 3 (três) fases [14].
Na primeira fase do processo, denominada Elaboração do Plano de Oferta, está o
gerenciamento das grades curriculares que definem, temporalmente, o conjunto de disciplinas
que deverão ser ofertadas no período letivo seguinte, de acordo com as turmas de alunos
ingressantes em cada processo seletivo realizado e seu respectivo currículo.
Na segunda fase, denominada Elaboração do Quadro de Oferta, de acordo com o
conjunto de disciplinas que deverão ser ofertadas obtidas na fase anterior, deve-se definir o
posicionamento de cada uma das disciplinas na grade de horários semanal considerando também
as questões de turmas especiais e disciplinas optativas. Segundo Lara (2006), “essa abordagem
permite que as informações sobre a oferta já sejam divulgadas sem mesmo haver a designação
dos professores às disciplinas”. Diversos benefícios dessa estratégia são apontados como, por
exemplo, a possibilidade do planejamento prévio dos alunos para a matrícula, a possibilidade das
alocações prévias de sala de aula para as turmas e segurança do corpo docente de saber que seus
XXXIX SBPO
[1784]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
horários estão pré-definidos, tal que não ocorram surpresas pouco antes do início das aulas de que
seus horários estão sendo trocados. Essa fase pode ser auxiliada por modelos matemáticos que
busquem, por exemplo, a minimização de janelas, a otimização de uso de recursos especiais
(laboratórios, multimeios, etc.) e a adequação de critérios didático-pedagógicos. Alguns
softwares de apoio são apresentados na literatura como por exemplo os apresentados em
[8][15][19].
Por fim, a terceira fase consiste na elaboração final do quadro de horários, ou seja,
acoplar ao quadro de oferta os recursos docentes para a realização das atividades. Após realizar a
alocação de professores as ofertas de disciplinas, já definidas na fase anterior, tem-se o quadro de
horários final solução.
O objetivo desse trabalho é propor um modelo para resolver o problema de alocação de
professores, que atue na terceira fase, e que seja aplicável aos cenários de instituições de um
único campus e multicampi, sendo que o quadro de horários solução seja eficiente no ponto de
vista do custo operacional e garantindo os critérios de qualidade definidos pela legislação
educacional.
3 – Legislação Especifica
Observando a legislação educacional brasileira, foram definidas restrições adicionais às
clássicas dos problemas de timetabling tal que a solução final do quadro de horários garantisse o
cumprimento de todas as exigências legais com excelência. As principais bases para elaboração
do modelo matemático foram obtidas em [2][5][3] e [4]. Entre diversos itens abordados pela
legislação, apenas alguns aspectos, trabalhados quantitativamente, devem ser contemplados no
modelo matemático. Sua incorporação no modelo se deve ao fato de que os mesmos possuem
grande relevância na avaliação [3] realizada pelo INEP/MEC. Entre eles estão o indicador
Regime de Trabalho, o indicador Titulação, o indicador Publicações e Produções.
O indicador Regime de Trabalho (RT) é calculado da seguinte forma:
RT =
( PI × N I + PP × N P + PH × N H )
D
onde:
PI = Peso do Regime Integral = 60 de acordo com [3].
NI = Número de docentes em Regime Tempo Integral
PP = Peso do Regime Parcial = 30 de acordo com [3].
NP = Número de docentes em Regime Tempo Parcial
PH = Peso do Regime Horista = 10 de acordo com [3].
NH = Número de docentes Horistas
D = Número total de docentes
Docentes em Regime de Trabalho Integral são docentes contratados com 40 horas
semanais de trabalho, sendo que no mínimo 50% do tempo deve ser destinado para atividades
complementares. Docentes Regime de Trabalho Parcial são docentes contratados com 12 ou mais
horas semanais de trabalho, sendo que pelo menos 25% do tempo deve ser destinado para
atividades complementares. Os docentes horistas são docentes contratados pela instituição
exclusivamente para ministrar horas-aula, independentemente da carga horária contratada, ou que
não se enquadrem nos outros regimes de trabalho anteriormente definidos.
Dependendo do valor de RT, o indicador Regime de Trabalho irá obter um conceito. O
quadro 1 exibe as faixas de conceitos para cada tipo de IES.
XXXIX SBPO
[1785]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
QUADRO 1
Tabela de Conceitos do Indicador Regime de Trabalho (RT)
Conceito do
Indicador Regime
de Trabalho (RT)
1
Universidades
Centros Universitários
Faculdades
0 ≤ RT < 17,5
0 ≤ RT < 15
0 ≤ RT < 12,5
2
17,5 ≤ RT < 26,5
15 ≤ RT < 20
12,5 ≤ RT < 15
3
26,5 ≤ RT < 35
20 ≤ RT < 25
15 ≤ RT < 17,5
4
35 ≤ RT < 40
25 ≤ RT < 30
17,5 ≤ RT < 22,5
5
40 ≤ RT
30 ≤ RT
22,5 ≤ RT
O indicador Titulação (MT) é calculado da seguinte forma:
MT =
( PE × N E + PM × N M + PD × N D )
D
onde:
PE = Peso da Especialização = 10 de acordo com [3].
NE = Número de docentes com Especialização
PM = Peso do Mestrado = 30 de acordo com [3].
NM = Número de docentes com Mestrado
PD = Peso do Doutorado = 60 de acordo com [3].
ND = Número de docentes com Doutorado
D = Número total de docentes
Dependendo do valor de MT, o indicador Titulação irá obter um conceito. O quadro 2
exibe as faixas de conceitos para cada tipo de IES.
QUADRO 2
Tabela de Conceitos do Indicador Titulação (MT)
Conceito do
Indicador
Titulação (MT)
1
Universidades
Centros Universitários
Faculdades
0 ≤ MT < 13
0 ≤ MT < 12
0 ≤ MT < 11
2
13 ≤ MT < 16,6
12 ≤ MT < 14
11 ≤ MT < 12
3
16,6 ≤ MT < 20
14 ≤ MT < 16,6
12 ≤ MT < 14
4
20 ≤ MT < 25
16,6 ≤ MT < 20
14 ≤ MT < 16
5
25 ≤ MT
20 ≤ MT
16 ≤ MT
O indicador Publicações e Produções (N) é calculado da seguinte forma:
N=
( PA × na + PL × nl + PT × nt + PR × nr + PPI × n pi + PPT × n pt + PDP × ndp )
( PA + PL + PT + PR + PPI + PPT + PDP ) × D
Onde,
PA = Peso atribuído aos artigos publicados em periódicos científicos indexados = 30 de
acordo com [3].
na = Número de artigos publicados em periódicos científicos indexados, pelo corpo
docente da instituição, nos últimos três anos
PL = Peso atribuído aos livros ou capítulos de livros publicados =20 de acordo com [3].
XXXIX SBPO
[1786]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
nl = Número de livros ou capítulos de livros publicados, pelo corpo docente da
instituição, nos últimos três anos
PT = Peso atribuído aos trabalhos publicados em anais = 10 de acordo com [3].
nt = Número de trabalhos completos publicados em anais, pelo corpo docente da
instituição, nos últimos três anos
PR = Peso atribuído aos resumos publicados em anais = 05 de acordo com [3].
nr = Número de resumos publicados em anais, pelo corpo docente da instituição, nos
últimos três anos
PPI = Peso atribuído às propriedades intelectuais depositadas ou registradas = 15 de
acordo com [3].
npi = Número de propriedades intelectuais depositadas ou registradas, do corpo docente
da instituição, nos últimos três anos
PPT = Peso atribuído aos projetos e/ou produções artísticas, técnicas, culturais e
científicos = 10 de acordo com [3].
npt = Número de projetos e/ou produções artísticas, técnicas, culturais e científicos, do
corpo docente da instituição nos últimos três anos
PDP = Peso atribuído às produções didático-pedagógicas relevantes = 10 de acordo com
[3].
ndp = Número de produções didático-pedagógicas relevantes, do corpo docente da
instituição, nos últimos três anos;
D = Total de Docentes
De acordo com o tipo de instituição, as metas de qualidade para o conceito variam, de
acordo com o Quadro 3.
QUADRO 3
Tabela de Conceitos do Indicador Publicações e Produções (N)
Conceito do
Indicador
Publicações e
Produções (N)
1
Universidades
Centros Universitários
Faculdades
0 ≤ N < 0,007145
0 ≤ N < 0,004287
0 ≤ N < 0,0021435
2
0,007145 ≤ N < 0,012861
0,004287 ≤ N < 0,007145
0,0021435 ≤ N < 0,004287
3
0,012861 ≤ N < 0,1429
0,007145 ≤ N < 0,07145
0,004287 ≤ N < 0,04287
4
0,1429 ≤ N < 0,2858
0,07145 ≤ N < 0,1429
0,04287 ≤ N < 0,08574
5
0,2858 ≤ N
0,1429 ≤ N
0,08574 ≤ N
Outra restrição importante estabelecida na legislação, no art. 52, § 3º, da Lei 9.394 de
1996, a LDB, e no art. 1º do Decreto 5.786 de 2006, é que há um limite mínimo para o número de
docentes atuantes em regime de trabalho Tempo Integral. No caso das universidades o mínimo é
33% enquanto nos centros universitários o mínimo é 20%.
4 – Modelagem
O objetivo do modelo a ser proposto é alocar os professores de forma eficiente. Para isso,
aspectos sobre o corpo docente, sobre os custos de alocação e sobre as informações para a
alocação de custo mínimo são consideradas. Para uma determinada instância, deve-se decidir:
− Se o docente deverá ou não ser alocado no quadro de horários;
− Se for alocado, em qual regime de trabalho o docente deverá atuar;
− Se for alocado, em quais unidades de oferta o docente deverá lecionar.
XXXIX SBPO
[1787]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Como resultado final do processo, tem-se um quadro de horário de custo mínimo com os
níveis de qualidade máximos. Parte-se do pressuposto que o quadro de ofertas de disciplinas já
exista (fase 2). Logo, a atividade está em alocar o corpo docente para executar tal oferta. O
modelo de Alocação de Professores para um Único Campus (APU) proposto é descrito da
seguinte forma:
Seja,
I = conjunto de docentes.
J = conjunto de regimes de trabalho. (Tipicamente: RI – Regime Integral -, RP –
Regime Parcial –, e RH – Regime Horista).
K = conjunto de unidades de oferta de disciplinas. (Obs: uma disciplina pode
estar sendo ofertada várias vezes).
H = conjunto de horários de um turno. (Tipicamente: 1 a 4).
T = conjunto de turnos. (Tipicamente: Manhã, Tarde e Noite).
D = conjunto de dias da semana (Tipicamente: Segunda a Sexta).
Deve-se considerar como dados de entrada do modelo as seguintes informações:
Fij = custo de ativação de um docente i ao regime de trabalho j.
Cik = custo de alocação de um professor i a uma oferta de disciplina k. Pode
representar preferências docentes a designação do conjunto de oferta de
disciplinas.
Tamk = tamanho, em horas, de uma oferta de disciplina k.
THj = total de horas do regime de trabalho j.
Ej = disponibilidade de horas do regime de trabalho j para alocação em atividades
de ensino, ou seja, atividades que vão atender a oferta de disciplinas.
Emj = limite inferior de horas do regime de trabalho j para alocação em
atividades de ensino, ou seja, atividades que vão atender a oferta de disciplinas.
Qdkhtd = quadro de oferta das disciplinas, especificando que a oferta de disciplina
k ocorrerá no horário h, do turno t, do dia d, sendo Qdkhtd igual a 1 quando existe
a oferta e 0 caso contrário.
PRTj = peso do regime de trabalho na avaliação institucional do MEC.
MRT = Meta do Indicador Regime de Trabalho na Avaliação Institucional.
RTIj = Igual a 1 caso o regime de trabalho seja do tipo tempo integral.
MTI = Meta de docentes em regime de trabalho tempo integral de acordo com o
tipo de organização acadêmica.
Dispihtd = quadro de disponibilidade do docente i, sendo 1 caso o docente i tem
disponibilidade para ser alocado no horário h, do turno t, do dia d, sendo 0 caso
contrário.
Compli = Carga horária pré-alocada para o docente i em atividades
complementares.
As variáveis de decisão do modelo são:
Yij = 0 ou 1, sendo 1 caso o docente i seja atribuído ao regime de trabalho j e 0
caso contrário.
Xik = 0 ou 1, sendo 1 caso o docente i seja designado a atender a oferta de
disciplina k.
O objetivo do modelo é alocar os docentes tal que todas as unidades de oferta sejam
atendidas com o mínimo custo operacional, atendendo também aos requisitos de qualidade da
avaliação institucional e demais restrições de um quadro de horários. A definição dos coeficientes
F e C devem ser balizadas nos aspectos relativos ao corpo docente: status da alocação,
disponibilidade de tempo, formação acadêmica e área de atuação, disponibilidade nos horários,
titulação, publicações e produções acadêmicas, experiência profissional e carreira institucional.
XXXIX SBPO
[1788]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
O coeficiente F está relacionado à ativação do professor em um regime de trabalho. Para
cada professor é associada uma penalidade de acordo com a ponderação dos aspectos
considerados bem como os custos marginais associados ao regime de trabalho junto ao modelo
APRAC[13]. Os docentes com menor penalidade terão preferência na alocação.
De forma análoga, o coeficiente C está relacionado à designação do professor para
atender uma determinada oferta de disciplina, observando sua preferência pela disciplina, o
histórico da alocação, a adequação de sua formação e o status da sua contratação.
Logo, quanto menor forem os coeficientes F e C, mais propenso um docente i está para
ser alocado em um regime de trabalho j e em uma oferta de disciplina k. As restrições serão
explicadas a partir da formulação matemática do modelo descrita abaixo:
min ∑∑ Fij Yij + ∑ ∑ C ik X ik
i∈I j∈J
i∈I k∈K
sujeito a:
∑Y
j∈J
≤1
ij
∀ i ∈I
(1)
∑X
ik
∑X
ik
Tamk ≤ ∑ Yij E j
∑X
ik
Tam k ≥ ∑ Yij Em j
∑X
ik
Tamk ≤ ∑ Yij TH j − Compli
i∈I
k∈K
k∈K
k∈K
=1
j
ij
ik
(4)
ij
(5)
X ik ∈ {0,1}
∀ i ∈I
(6)
≥ MRT ∑∑ Yij
(7)
j
≥ MTI ∑∑ Yij
(8)
Qd khtd ≤ 1
Yij ∈ {0,1}
∀ i ∈I
j
X ik Qd khtd ≤ Dispihtd
∑X
∀ i ∈I
− E j ) ≥ Compl i
∑∑ Y RTI
k∈K
(3)
j∈J
∑∑ Y PRT
i∈I j∈J
∀ i ∈I
j∈J
ij
i∈I j∈J
(2)
j∈J
∑ Y (TH
j∈J
∀ k ∈K
i∈I j∈J
i∈I j∈J
∀ i ∈I, k ∈K, h ∈H, t ∈T, d ∈D
(9)
∀ i ∈I, h ∈H, t ∈T, d ∈D
(10)
∀ i ∈I, k ∈K
(11)
∀ i ∈I, j ∈J
(12)
As restrições (1) garantem que um docente i estará alocado em apenas um regime de
trabalho j. Caso não esteja associado a nenhum significa que ele não está alocado no quadro de
horários final. Já as restrições (2) garantem que toda a oferta de disciplina k será exclusivamente
atendida por um docente i.
As restrições (3), (4), (5) e (6) servem para limitar a quantidade de carga horária alocada
a um docente de acordo com seu regime de trabalho. As restrições (3) garantem que a quantidade
de horas alocadas a um docente i para atender ofertas de disciplinas não é superior a quantidade
de horas disponíveis para atividades de ensino de acordo com o regime de trabalho j. Da mesma
forma, as restrições (4) definem um limite inferior para o número de horas de ensino do regime
de trabalho j. As restrições (5) garantem que a quantidade de horas alocadas a um docente i para
atender ofertas de disciplinas não sobreponha à carga horária complementar (Compli) pré-alocada
ao docente i. Já as restrições (6) garantem que o total de carga horária complementar pré-alocado
seja sempre enquadrado no montante destinado a esse tipo de atividade para cada regime de
trabalho j, ou seja, no saldo de THj - Ej .
XXXIX SBPO
[1789]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
A restrição (7) garante que o conceito do indicador regime de trabalho da avaliação
institucional seja atendido no nível máximo, enquanto a restrição (8) garante o atendimento do
percentual de professores em regime de trabalho tempo integral, de acordo com o estabelecido na
legislação.
As restrições (9) garantem que nenhum docente será alocado caso esteja indisponível em
um determinado horário. As restrições (10) garantem que um docente i nunca está alocado mais
de uma vez em um mesmo horário. Por fim, as restrições (11) e (12) definem os domínios das
variáveis de decisão X e Y, respectivamente.
A fim de incrementar o modelo, podem ser adicionadas duas outras restrições, apesar de
que seu atendimento está embutido na função objetivo.
Yij PTITi ≥ MTIT
Yij
(13)
∑∑
∑∑
i∈I j∈J
∑∑ Y PPUB
i∈I j∈J
ij
i
i∈I j∈J
≥ MPUB∑∑ Yij
(14)
i∈I j∈J
PTITi corresponde ao peso da titulação e PPUBi corresponde ao peso da publicação do
professor i de acordo com o Manual de Avaliação Externa[3]. MTIT e MPUB são as metas para o
indicador Titulação e Publicação/Produção respectivamente, de acordo com o tipo de IES. A
restrição (13) garante o atendimento do indicador titulação e a restrição (14) garante o
atendimento do indicador Publicação/Produção. Como o atendimento dessas restrições está
embutido na função objetivo, essas restrições podem ser consideradas desejáveis e por isso não
serem utilizadas.
Outra observação importante é que as restrições de indisponibilidade dos professores
também podem ser relaxadas visto que como o quadro de ofertas está pré-definido, caso um
professor esteja indisponível durante o horário de determinada oferta, pode-se simplesmente
desabilitá-lo a atender tal oferta. Essa situação corresponde à associar um custo elevado ao
coeficiente Cik sempre que o professor estiver indisponível no horário de realização da oferta de
disciplina. Nesse caso, as restrições (9) seriam desconsideradas do modelo.
Por fim, com o intuito de evitar a criação de variáveis que jamais serão solução do
problema, ou seja, aquelas que possuem um custo muito elevado (infinito), pode-se incrementar o
modelo tal que apenas as variáveis que podem vir a participar da solução sejam instanciadas e
que variáveis de folga sejam inseridas para evitar a inviabilidade na resolução do modelo. Dessa
forma é possível trabalhar com instâncias maiores.
5 – Modelagem Multicampi
O modelo anteriormente proposto não é aplicável em instituições que trabalham com seus
cursos distribuídos em mais de um campus. Isso porque o modelo permite que em um mesmo
turno t, de um mesmo dia d, o professor seja alocado em ofertas de disciplinas que ocorrerão em
campus diferentes. Normalmente, devido à necessidade de um deslocamento significativo entre
essas unidades, torna-se inviável permitir que um professor seja designado a atender a demanda
em campus diferentes, no mesmo turno, no mesmo dia.
A fim de comportar o problema multicampi, o modelo anteriormente proposto necessita
de restrições e variáveis adicionais. Então, seja:
L = conjunto de campus ou locais que exigem deslocamento significativo do docente.
NH = número de horários de um turno.
Qdkhtdl = quadro de oferta das disciplinas, especificando que a oferta de disciplina k será
dada no horário h, do turno t, do dia d, no campus l, sendo Qdkhtdl igual a 1 quando existe
a oferta e 0 caso contrário.
Dispihtdl = quadro de disponibilidade do docente i, sendo 1 caso o docente i tem
disponibilidade para ser alocado no horário h, do turno t, do dia d, no campus l, sendo 0
caso contrário.
XXXIX SBPO
[1790]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Vitdl = variável auxiliar que representa que um docente i foi alocado para lecionar no
turno t do dia d no campus l, sendo 1 quando o docente foi alocado e 0 caso contrário.
Reescrevendo as restrições (9) e (10) e adicionando quatro novos conjuntos de restrições,
temos o modelo de Alocação de Professores Multicampi (APM):
X ik Qd khtdl ≤ Dispihtdl
∑X
k∈K
ik
∑V
l∈L
itdl
Qd khtdl ≤ 1
≤1
∀ i ∈I, k ∈K, h ∈H, t ∈T, d ∈D, l ∈L
(15)
∀ i ∈I, h ∈H, t ∈T, d ∈D, l ∈L
(16)
∀ i ∈I, t ∈T, d ∈D
(17)
1
1
∀ i ∈I, t ∈T, d ∈D, l ∈L
X ik Qd khtdl − Vitdl ≥
−1
∑
∑
NH k∈K h∈H
NH
1
∀ i ∈I, t ∈T, d ∈D, l ∈L
∑ ∑ X ik Qd khtdl − Vitdl ≤ 0
NH k∈K h∈H
∀ i ∈I, t ∈T, d ∈D, l ∈L
Vitdl ∈ {0,1}
(18)
(19)
(20)
As restrições (17) garantem que um professor nunca é alocado dentro de um mesmo
turno em dois campi diferentes. As restrições (18) e (19) são responsáveis por atribuir 0 ou 1 à
variável Vitdl., que de acordo com as restrições (20), é binária. Quando um docente i foi alocado
em um turno t do dia d no campus l, a variável Vitdl assume 1. As restrições (15) e (16)
correspondem às restrições (9) e (10) do modelo para um único campus. Da mesma forma, no
caso de não se utilizar as restrições de disponibilidade de professores, conforme explicado na
seção anterior, as restrições (15) seriam desconsideradas do modelo.
6 – Testes Realizados
Foram realizados testes em instâncias de diversos tamanhos. Foram utilizados
computadores Pentium IV com 1 Gb de memória RAM, rodando o AMPL [10] e o CPLEX A
partir de observações realizadas durante a execução do branch-and-bound do CPLEX, pode-se
constatar que o problema tende a convergir para o valor mínimo da função objetivo com uma
certa rapidez, mas o gap, que é a distância da melhor solução obtida para o limite inferior
computado pelo algoritmo, converge lentamente a partir de um certo ponto.
TABELA 1
Instâncias dos Testes
Instância
1.01
1.02
1.03
1.04
1.05
1.06
1.07
1.08
1.09
1.10
1.11
XXXIX SBPO
C
1
2
3
4
5
6
7
8
9
10
11
P
68
225
291
330
358
404
421
456
463
473
507
O
20
128
188
457
614
697
830
912
981
1.010
1.082
NV
2.591
9.189
11.957
14.142
16.192
18.478
19.544
21.068
21.905
22.341
23.969
NR
2.402
8.005
10.375
12.009
13.146
14.839
15.567
16.874
17.188
17.567
18.829
NVP
537
3.958
5.156
7.603
9.754
11.398
12.695
13.630
14.557
14.682
16.299
NRP
303
1.289
1.640
2.133
2.790
3.173
3.499
3.731
4.072
4.116
4.504
[1791]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Legenda: C – Número de cursos abrangidos (referência)
P – Número de professores disponíveis para a alocação
O – Número de ofertas de disciplinas a serem alocadas
NV – Número de variáveis da instância
NR – Número de restrições da instância
NVP – Número de variáveis após pré-processamento
NRP – Número de restrições após pré-processamento
Para instâncias menores, o algoritmo encontra a solução ótima (gap igual a zero) em um
tempo baixo, com poucas iterações. Observando que instâncias do modelo APM são
relativamente maiores, o algoritmo precisa de mais iterações para computar a solução ótima. No
entanto, para os dois modelos, o comportamento do resolvedor é muito parecido.
Para os testes realizados foi considerado um gap de 0,01% para todas as simulações. A
TAB. 1 mostra as instâncias utilizadas e a TAB. 2 exibe os resultados computacionais.
TABELA 2
Resultados Computacionais
Instância
1.01
1.02
1.03
1.04
1.05
1.06
1.07
1.08
1.09
1.10
1.11
Solução
APU
APM
G
G
G
G
G
G
G
G
G
G
T
G
T
G
G
G
G
T
G
T
G
T
# Iterações MIP Simplex
APU
APM
70
89
2.486
2.956
1.319.957
5.265
9.553.020
7.332
254.136
966.872
25.194.943
27.377
25.833.540 12.831.563
11.686.462
70.770
412.895 22.055.477
316.156 14.232.067
703.010 22.718.477
# Nós B&B
APU
APM
10
142.375
180
490.218
160
16.960
36.000
692.070
960
756.171
592.941
661.875
4.000
21.000
295.427
9.000
212.952
38.000
316.168
Legenda: G – Processamento com solução ótima com gap de 0,01%
T – Processamento com solução inteira após tempo limite de 36.000 seg.
B&B – Branch-and-bound
Pode-se observar pelos testes que mesmo instâncias relativamente grandes, que
correspondem a problemas do mundo real, foi possível resolver com um gap pequeno em pacotes
de otimização comerciais.
7 – Conclusão
Os modelos propostos tratam o problema de alocação de professores pela visão da gestão
de custos e do atendimento das exigências de qualidade definidas na legislação educacional. A
definição de uma alocação docente eficiente tem grande valia para as instituições de ensino
superior, especialmente para as instituições privadas que precisam de se auto-sustentar. Dessa
forma, a gestão eficiente de custos pode viabilizar outras atividades e projetos, assim como a
competitividade da instituição.
Outro aspecto importante é que em diversas instituições, os quadros de horários ainda são
montados manualmente. Então, a utilização de um sistema especialista e que zela pela eficiência
operacional, tem uma relevância considerável. O fato de abordar parâmetros definidos na
legislação brasileira e prover uma modelagem para ambientes multicampi, comum nas
instituições universitárias, torna o uso do modelo abrangente. Além disso, visto que a estrutura do
processo para o qual o modelo foi desenvolvido permite flexibilidade e adaptações, o modelo
pode ser utilizado como um sistema especialista de apoio à decisão.
XXXIX SBPO
[1792]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
8 – Referências Bibliográficas
[1]
BAZARAA, M., JARVIS, J., SHERALI, H., Linear Programming and Network Flows,
2 ed. New York: Wiley, 1990.
[2]
BRASIL. Congresso Nacional. Lei n. 9.394 de 20 de dezembro de 1996. Estabelece as
diretrizes e bases da educação nacional. Diário Oficial da União, Poder Executivo,
Brasília, DF, 23 dez. 1996. Seção 1. p. 27833. Disponível em:
http://www.camara.gov.br. Acesso em: 25 mai. 2006.
[3]
BRASIL. Ministério da Educação. Manual de Avaliação Externa de Instituições de
Educação Superior: Diretrizes e Instrumento. Brasília, fev. 2006. Disponível em
http://www.inep.gov.br. Acesso em: 25 mai. 2006.
[4]
BRASIL. Presidência da República. Decreto n. 5.773 de 9 de maio de 2006. Dispõe
sobre o exercício das funções de regulação, supervisão e avaliação de instituições de
educação superior e cursos superiores de graduação e seqüenciais no sistema federal de
ensino. Diário Oficial da União, Poder Executivo, Brasília, DF, 10 mai. 2006. Seção 1.
p. 6. Disponível em: http://www.camara.gov.br. Acesso em: 25 mai. 2006.
[5]
BRASIL. Presidência da República. Decreto n. 5.786 de 24 de maio de 2006. Dispõe
sobre os centros universitários e dá outras providências. Diário Oficial da União, Poder
Executivo, Brasília, DF, 25 mai. 2006. Seção 1. p. 9. Disponível em:
http://www.camara.gov.br. Acesso em: 25 mai. 2006.
[6]
BURKE, E.; PETROVIC, S., Recent research directions in automated timetabling.
European Journal of Operational Research, 140, 2002, p. 266-280.
[7]
CARVALHO, M.T. Confecção de Horários de Aulas em Instituições de Ensino
Privadas de 3º Grau no Brasil, 2002. 101 f. Dissertação. Departamento de Engenharia
de Produção, Universidade Federal de Minas Gerais, Belo Horizonte, 2002.
[8]
CHAVES, T., Um Sistema de Apoio à Construção de Quadros de Horários, 2005. 77 f.
Dissertação. Departamento de Ciência da Computação, Universidade Federal de Minas
Gerais, Belo Horizonte, 2005.
[9]
COOPER, T.; KINGSTON, J., The Complexity of Timetable Construction Problems,
In: International Conference on the Practice and Theory of Automated Timetabling, 1.,
1995,
Edingburgh. [Procedings…] Edingburgh: ICPTAT, 1995. p. 511-522.
Disponível em: http://citeseer.ist.psu.edu/232089.html. Acesso em: Out/2005.
[10] FOURER, R, GAY, D., KERNIGHAN, B., AMPL: A Modeling Language for
Mathematical Programming, 2 ed. Toronto: Thomson, 2003.
[11] GAREY, M.; JOHNSON, D., Computers and Intractability: A Guide to the Theory of
NP-Completeness. Freeman, 1979.
[12] GOLDBARG, M., LUNA, H., Otimização Combinatória e Programação Linear:
Modelos e Algoritmos, Rio de Janeiro: Campus, 2000.
[13] LARA, B., Um Modelo de Programação Linear para Solução do Problema da
Aplicação de Recursos em Atividades Complementares em Instituições de Ensino
Superior, In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 36., 2004,
São João Del Rei. [Anais eletrônicos...] São João Del Rei: UFSJ, 2004. 1 CD-ROM. p.
381-387.
[14] LARA, B., Um Modelo de Redes Multifluxo para o Problema de Alocação de
Professores em Instituições de Ensino Superior, In: SIMPÓSIO BRASILEIRO DE
PESQUISA OPERACIONAL, 38., 2006, Goiânia. [Anais eletrônicos...] Goiânia:
PUC-GO, 2006. 1 CD-ROM. p. 1737-1748.
XXXIX SBPO
[1793]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
[15] SANDHU, K., Automating Class Schedule Generation in the Context of a University
Timetabling Information System, 2003. 200 f. Tese. School of Management, Griffith
University, Australia, 2003.
[16] SCHAERF, A., A Survey of Automated Timetabling, Artificial Intelligence Review,
Volume
13,
Issue
2,
Apr
1999,
Page
87,
URL
http://dx.doi.org/10.1023/A:1006576209967
[17] TERRA, I., Uma Solução para a Confecção do Horário Acadêmico, 2001. 59 f.
Dissertação. Departamento de Ciência da Computação, Universidade Federal de Minas
Gerais, Belo Horizonte, 2001.
[18] WERRA, D., An Introduction to Timetabling, European Journal of Operational
Research, 19, Amsterdam, 1985, p. 151-162.
[19] WONG, K., WHITE, G., Interactive Timetabling in Universities. Computers in
Education, 12:4, 1988, p.521-529
XXXIX SBPO
[1794]