Estudo de Coloração Aplicado ao Problema de Alocação de
Horário de Professores
Fernanda Navarro1, Frederico Coelho (Orientador)1
1
Departamento de Ciência da Computação – Universidade Presidente Antônio Carlos
(UNIPAC)
Campus Magnus – Barbacena – MG – Brasil
[email protected], [email protected]
Resumo: Dado o grande problema de gerar a grade horária de docentes o
trabalho tem como objetivo geral o desenvolvimento de uma ferramenta capaz
de solucionar o problema de alocação de horários acadêmicos utilizando Teoria
dos Grafos, mais especificamente a parte de coloração. Apesar do problema se
mostrar ser da classe NP-difícil, a heurística permitiu a realização dos testes para
alocação de professores chegando a um resultado próximo ao ideal.
Palavras-chave: Alocação de horário; Coloração;
1. Introdução
As instituições educacionais se deparam com um grande problema que requer tempo e
paciência para resolver, a alocação de professores na grade horária. Esse problema é
sempre encontrado a cada período letivo e na maioria das instituições é resolvido
manualmente, o que torna a obtenção da melhor solução uma tarefa demorada.
Essa demora para obter o melhor resultado é devido a vários motivos, como a
disponibilidade dos professores, redução dos dias em que o professor estará na
instituição, e cada professor não pode estar alocado em duas turmas ao mesmo tempo,
entre outras. Estes motivos sempre geram conflitos e que tem que ser solucionados, nem
sempre agradando a todos, mas chegando a melhor forma possível.
O objetivo do desenvolvimento desse trabalho é diminuir o trabalho manual e o
tempo gasto pelos coordenadores, diretores e funcionários da secretaria de instituições
que sempre se deparam com os problemas no início do semestre de se conseguir alocar
todos os professores, atendendo as restrições que cada um possui, pois um professor
nem sempre é exclusivo da instituição, portanto não está disponível a todo o tempo para
atendê-la.
Este caso pode ser modelado e resolvido matematicamente como um problema
de otimização combinatória, na qual a complexidade aumenta exponencialmente em
função do número de disciplinas e de professores envolvidos. Existem várias técnicas
utilizadas para resolver a otimização combinatória, dentre elas, a teoria dos grafos, mais
especificamente a parte de coloração, que será abordado para a realização deste trabalho
de conclusão de curso.
A seguir, uma breve descrição das seções que compõem este trabalho.
A subseção um apresenta o problema de alocação do quadro de horários
descrevendo suas principais características. Na seção dois é feita uma revisão
bibliográfica onde são apresentadas algumas técnicas que podem ser utilizadas para
resolver problemas de otimização combinatória e também alguns trabalhos que já foram
realizados baseados no problema de alocação de horário. Já a seção três aborda a
solução proposta, com os conceitos de coloração de grafos e sua possível aplicação no
problema, também apresenta o sistema desenvolvido e descreve o processo de
realização de testes que tem por finalidade a formulação de considerações em relação à
aplicação desenvolvida. Por fim, a última seção tem como objetivo apresentar as
conclusões obtidas durante a realização deste trabalho de conclusão de curso, e
principalmente o de relatar as análises dos resultados obtidos através da realização de
testes.
1.2. O problema do School Timetabling
Problemas de alocação de horário também são conhecidos como School Timetabling,
são considerados uma aplicação da otimização combinatória da classe NP difícil, sendo
mais fácil analisar se o resultado está correto do que obter analiticamente tal solução em
tempo polinomial, não existindo um modelo solução universal. (Preis, 2007)
O tipo de restrições envolvidas no problema pode envolver a disponibilidade dos
recursos, preferências pessoais, cumprimento da grade curricular, conflito de horários,
janelas, a existência de mais de um professor designado para lecionar uma mesma
disciplina; e diversas outras restrições que dependem da instituição em questão.
A combinação dessas restrições, que podem ser cada vez maiores, torna o
problema cada vez mais complexo, mostrando que a utilização de algoritmos ótimos
normalmente torna-se inviável quando o tamanho da entrada para o problema é muito
grande ou quando as restrições são complicadas. Ao observar a bibliografia, a maioria
das abordagens é feita através de algoritmos heurísticos, que são métodos que
encontram uma solução aproximada com tempo computacional reduzido.
2. Revisão Bibliográfica
Será feita uma revisão bibliográfica de algumas técnicas e trabalhos relacionados ao
tema.
2.1. Técnicas
Várias técnicas podem ser utilizadas para resolver os problemas de otimização
combinatória, a seguir serão descritas algumas dessas técnicas que serão subdivididas
em algoritmos heurísticos, meta-heurísticas, algoritmos aproximados, teoria dos grafos,
programação por restrições, programação linear e programação inteira.
2.1.1. Algoritmos Heurísticos
São algoritmos que não garantem encontrar a solução ótima de um problema, mas são
capazes de retornar uma solução de qualidade em um tempo adequado para as
necessidades da aplicação. (Constantino, 2003)
Os métodos heurísticos procuram um grau tão grande quanto possível de uma
ação a uma situação. Assim ele engloba estratégias, procedimentos, métodos de
aproximação tentativa/erro, sempre na procura da melhor forma de chegar a um
determinado fim. Os processos heurísticos exigem muitas vezes menos tempo que os
processos algorítmicos, aproximando-se mais da forma como o ser humano raciocina e
chega às decisões acertadamente e garantem soluções eficientes. (Rodrigues, 2004)
2.1.2. Meta-heurísticas
“Uma meta-heurística é um conjunto de conceitos que podem ser utilizados para definir
métodos heurísticos aplicáveis a um extenso conjunto de problemas”. (Sucupira, 2004)
2.1.2.1. Algoritmos Genéticos, Scatter Search e Algoritmos Meméticos
Família de modelos computacionais, inspirados na evolução natural dos seres vivos.
(Constantino, 2003)
Os Algoritmos Genéticos (AG’s) proporcionam métodos de buscar todas as
combinações de dígitos para identificar uma série que represente a melhor solução para
o problema, simulando processos naturais de sobrevivência e reprodução das
populações, essenciais na evolução. (Maciel, 2004)
O Scatter Search opera sobre uma população de soluções, ao invés de uma única
solução em cada iteração, e emprega procedimentos para combinar essas soluções com
o intuito de gerar novas soluções. Por outro lado, diferentemente desses mesmos
métodos, viola a premissa de que as abordagens evolucionárias devam ser baseadas em
escolhas aleatórias, limitando o uso da randomização a procedimentos de diversificação.
(Oliveira, 2007)
Algoritmos Meméticos são os algoritmos genéticos que realizam otimização
local. (Sucupira, 2004)
2.1.2.2. Simulated Annealing
Baseada originalmente em conceitos de Mecânica Estatística considerando a analogia
entre o processo físico annealing de sólidos e a resolução de problemas de otimização
combinatorial. A Simulated Annealing (SA) simula um método natural, fundamentado
numa analogia com a termodinâmica ao simular o resfriamento de um conjunto de
átomos aquecidos, operação conhecida como Recozimento (annealing). (Silva, 2005)
2.1.3. Algoritmos Aproximados
Nos Métodos Heurísticos não há garantia alguma a respeito da solução encontrada. Isto
é, não há como saber se a solução obtida está "perto" ou "longe" da melhor solução
possível em termos de qualidade. Contudo, há ocasiões em que essa noção de
proximidade faz-se necessária. Por exemplo, eu posso estar interessado em uma solução
que não precisa ser a melhor, mas deve ser, no máximo, 10% pior que a melhor solução
possível. Nesses casos, entram em ação os Algoritmos Aproximados. (Constantino,
2003)
2.1.4. Teoria dos Grafos
Modelos baseados em grafos são imensamente utilizados em muitos problemas de
otimização combinatória. Grafo é uma forma de representar de um conjunto de
elementos e suas relações. Esse recurso é muito utilizado para modelar os problemas por
ser uma forma bastante intuitiva para representá-los. Além disso, na literatura podem ser
encontrados algoritmos para resolver diversos problemas em grafos. (Constantino,
2003)
2.1.5. Programação por Restrições
Esta técnica teve suas origens no campo da Inteligência Artificial, mais especificamente
no ramo da Programação Lógica. Simplificando, consiste em um mecanismo de
inferência lógica auxiliado por um resolvedor de restrições que são impostas sobre as
variáveis do problema em questão. A modelagem dos problemas é facilitada por se
tratar de uma linguagem declarativa baseada em implicações lógicas. Restrições
complexas podem ser escritas de forma clara e concisa. Tem obtido bastante sucesso em
problemas de porte industrial. (Constantino, 2003)
É uma tecnologia de programação cuja principal característica é permitir ao
programador uma dedicação total à modelagem, tornando oculto o processo de efetiva
resolução dos problemas. Como conseqüência, a programação de restrições tem a
capacidade de reduzir o esforço de programação e tornar mais natural a programação
modular. (Sucupira, 2003)
2.1.6. Programação Linear e Programação Inteira
A Programação Linear utiliza modelos matemáticos para expressar um problema em
termos de variáveis contínuas e um conjunto de restrições lineares sobre essas variáveis.
Dada uma função objetivo que descreve basicamente como é calculado o "custo" a ser
minimizado, aplica-se um algoritmo que resolve o problema de forma eficiente.
Entretanto, na vida real é muito comum que as variáveis precisem assumir valores
inteiros e não contínuos. Por incrível que pareça, quando se impõe a restrição de que as
variáveis assumam valores inteiros o problema pode ficar muito mais difícil. E a idéia
natural de simplesmente arredondar os valores nem sempre traz bons resultados. É, aí
que entra a Programação Inteira. (Constantino, 2003)
2.2. Trabalhos relacionados
Nesta seção são descritos os trabalho relacionados a alocação de horário, os trabalhos
escritos, como monografias, artigos, publicações e também alguns sites que se
relacionam com o tema.
2.2.1. Trabalhos teóricos
Como exemplo de trabalho teórico será citado o trabalho de conclusão de curso
apresentado por Daniela Fernanda da Silva Costa ao Departamento de Ciência da
Computação, com o tema Estudo e Implementação de Algoritmos Genéticos Aplicados
ao Problema de Alocação de Horário, onde foi apresentada a compreensão de definição,
funcionamento e implementação de Algoritmos Genéticos para solucionar o problema
de quadro de horários, o que proporcionou o armazenamento de dados de entrada e
saída, gerados durante a execução da aplicação. (Costa, 2004)
2.2.2. Trabalhos práticos
Foram encontrados dois sites como trabalhos relacionados ao tema alocação de horário,
utilizando dois sistemas distintos para gerar automaticamente a grade de horário.
O site www.horarioescolar.com utiliza o SACHE – Sistema Automatizado de
Criação de Horários Escolares, um programa de computador que monta
automaticamente a grade horária da escola em poucos minutos, e possibilita o reajuste
manual através de uma ferramenta “inteligente” para auxiliá-lo. (Technique)
O site www.horario.com.br utiliza o Urânia que é um sofisticado software
disponibilizado para compra que também gera automaticamente a grade horária escolar.
(Geha)
3. Solução Proposta
A solução proposta é utilizar a coloração de grafos, realizar a atribuição de cores aos
vértices, de modo que vértices adjacentes tenham cores distintas. Se G é um grafo
simples, então uma coloração para G é uma atribuição de cores para cada vértice de
forma que vértices adjacentes tenham diferentes cores. O problema de coloração de
grafos é NP-completo.
A aplicação nesse problema seria resolver: N disciplinas que devem ter seus
exames escalonados de forma a não haver conflitos entre eles, e usando-se o menor
número de períodos possível, associando à coloração de grafos onde cada disciplina será
representada por um vértice e se houver conflito entre duas disciplinas, como serem
lecionadas no mesmo horário e pelo mesmo professor, existirá uma aresta entre os dois
vértices. A solução seria obtida atribuindo o menor número possível de cores. Uma cor
seria associada a um vértice, representando uma célula de horário, onde os vértices de
mesma cor e sem aresta podem ser realizados no mesmo horário.
3.1. O Sistema
Para o desenvolvimento do sistema foi utilizado o Sistema Gerenciador de Banco de
Dados MySql Server 5.1 e a implementação feita na linguagem Java com a ferramenta
NetBeans IDE 6.1.
3.2. Aplicação desenvolvida
A aplicação desenvolvida será abordada através da exploração dos dados de entrada e
saída, com o objetivo de aplicar as características citadas sobre a coloração de grafos
para tratar as restrições.
A interface da aplicação visa a simplicidade, para facilitar a utilização da
aplicação, de modo que não sejam encontrados problemas na aprendizagem do
funcionamento da mesma, deve, portanto ser útil e prática.
Na aplicação desenvolvida foram utilizados os dados do Departamento de
Ciência da Computação da Universidade Presidente Antônio Carlos (DCC-UNIPAC)
como problema real para comparações futuras.
As restrições podem variar de acordo com as normas de funcionamento de cada
instituição, nesse caso foram consideradas as seguintes restrições:
 A confecção de um quadro de horários atende somente a um determinado
semestre;
 O quadro de horário deve satisfazer uma combinação possível entre
professores, número de aulas e disciplinas para atender a determinada
turma. Não é possível ocorrer a existência de uma disciplina que não seja
lecionada por um professor ou que não seja assistida por uma turma.
Assim como também é inaceitável que a disciplina não tenha um tempo
máximo definido.
 Nenhum professor pode lecionar em duas turmas diferentes ao mesmo
tempo;
 Nenhuma turma pode assistir a duas disciplinas diferentes ao mesmo
tempo;
 Existe um limite determinado de número de aulas para que sejam
atendidos pelas disciplinas;
Os dados de entrada são fornecidos pelo usuário e são extremamente necessários
para que a aplicação funcione de maneira correta.
A Figura 1 apresenta a janela principal onde se tem acesso a professor, posteriormente a
disciplina e a grade horária.
Figura 1: Janela Principal
A figura 2 exibe o formulário Professor que disponibiliza as funções de cadastro,
consulta, alteração e exclusão. Os dados necessários para o cadastro dos professores são
matrícula, nome, disponibilidade, e o peso dessa restrição. A consulta, as alterações e
exclusões são realizadas pelo nome informado.
Figura 2: Formulário Professor
A figura 3 exibe o formulário Disciplina que disponibiliza as funções de
cadastro, consulta, alteração e exclusão. Os dados necessários para o cadastro das
disciplinas são código, nome, período em que é lecionada, a carga horária e o professor
que leciona essa disciplina. A consulta, as alterações e exclusões são realizadas pelo
nome informado.
Figura 3: Formulário Disciplina
O sistema permite também como entrada de dados o número de períodos que o
curso mantém atualmente, esse número é multiplicado por 10 (dez) que corresponde ao
número de aulas ministradas semanalmente, conseqüentemente ao número de cores. O
resultado gera o número de vértices, onde, logo após havendo igualdade na coloração é
feita uma comparação para verificação das restrições, onde houver restrição é gerada
uma aresta onde automaticamente serão feitas as modificações necessárias para gerar a
melhor opção da grade horária.
Na execução do programa, a entrada foi a situação real do DCC em que existem
4 períodos distintos, o resultado satisfatório seria alocar 40 aulas. Foram realizados
testes e modificações foram feitas no código, dos resultados, o mais próximo foi com 29
alocações e o mais distante com 17 alocações. Abaixo pode ser visualizado um dos
testes realizados, onde é exibida a posição, local de alocação no vetor, matéria, código
da disciplina lecionada, professor, matrícula do professor e qual horário é lecionada a
disciplina.
Posição: 0
Matéria: 10
Professor: 5
1ºSeg
Posição: 1
Matéria: 13
Professor: 5
1ºQua
Posição: 2
Matéria: 13
Professor: 5
1ºSeg
Posição: 3
Matéria: 17
Professor: 5
1ºQua
Posição: 4
Matéria: 17
Professor: 5
1ºSeg
Posição: 5
Matéria: 19
Professor: 6
1ºTer
Posição: 6
Matéria: 20
Professor: 6
1ºTer
Posição: 7
Matéria: 21
Professor: 12
1ºSex
Posição: 8
Matéria: 6
Professor: 9
2ºSeg
Posição: 9
Matéria: 16
Professor: 9
2ºSeg
Posição: 10
Matéria: 18
Professor: 9
2ºSeg
Posição: 11
Matéria: 15
Professor: 8
2ºQua
Posição: 12
Matéria: 7
Professor: 4
1ºTer
Posição: 13
Matéria: 8
Professor: 4
1ºTer
Posição: 14
Matéria: 9
Professor: 2
1ºTer
Posição: 15
Matéria: 12
Professor: 2
1ºTer
Posição: 16
Matéria: 14
Professor: 10
1ºTer
Posição: 17
Matéria: 22
Professor: 10
1ºTer
Posição: 18
Matéria: 11
Professor: 3
1ºTer
Após serem inseridos os dados de entrada descritos anteriormente é possível a
visualização do grafo que corresponde a resolução do problema.
6. Conclusão
O resultado do trabalho pode ser considerado satisfatório tendo em vista que o que foi
inicialmente proposto foi concretizado através da abordagem feita de coloração de
grafos.
Podemos comprovar através dos grafos que quanto maior o número de restrições
maior a dificuldade de encontrar uma melhor solução.
A aplicação desenvolvida neste trabalho possibilita as modificações para que
possa ser utilizada em outros departamentos e cursos.
Apesar da junção do problema de alocação de horários e a coloração de grafos
por serem um problema exponencial não mostraram viável a utilização deste método, o
mesmo poderá ser utilizado para possíveis modificações em trabalhos futuros.
7. Bibliografia
CONSTANTINO, A. A. Otimização combinatória. Maringá, 2003. Disponível em:
<http://www.din.uem.br/~ademir/pg/otimizacao.html>. Acesso em: 17 de junho de
2009.
COSTA, Daniela Fernanda da Silva. Estudo e implementação de algoritmos
genéticos aplicados ao problema de alocação de horário. Barbacena: 2004. Trabalho
de Conclusão de Curso (Graduação em Ciência da Computação) – Universidade
Presidente Antônio Carlos.
COSTA, Felippe Pereira da; GUIMARÃES, Irce Fernandes Gomes. Um algoritmo
evolutivo híbrido para o problema de programação de horários em escolas.
Disponível em: <http://www.decom.ufop.br/prof/marcone/Publicacoes/ENEGEP-2002PHE.pdf> Acesso em: 14 de junho de 2009;
COSTA, Felippe Pereira da. Programação de horários em escolas via Grasp e Busca
Tabu. 2003. Disponível em:
<http://www.decom.ufop.br/prof/marcone/Orientacoes/PHEviaGRASPeBuscaTabu.pdf
> Acesso em: 14 de junho de 2009;
GEHA, Sistemas Especialistas, www.horario.com.br, disponível em:
<http://www.horario.com.br/> Acesso em: 17 de junho de 2009;
HAMAWAKI, Cristiane Divina Lemes. Geração automática de grade horária
usando algoritmos genéticos: o caso da faculdade de engenharia elétrica da UFU.
Disponível em: <http://www.bdtd.ufu.br//tde_busca/arquivo.php?codArquivo=230>
Acesso em: 14 de junho de 2009;
MACIEL, Emanuella da Silva. Aplicações de algoritmos genéticos para otimização
da logística dos correios na zona da mata mineira, utilizando o problema do
caixeiro viajante. Barbacena: 2004. Trabalho de Conclusão de Curso (Graduação em
Ciência da Computação) – Universidade Presidente Antônio Carlos.
OLIVEIRA, Eduardo Fonseca de; PAGOTO, Fábio Bozzi; SILVA, Flávia Torezani;
LORENZONI, Luciano Lessi. Scatter Search aplicado ao problema de otimização
da alocação de sondas de produção em poços de petróleo. Foz do Iguaçu: 2007.
Disponível em:
<http://www.abepro.org.br/biblioteca/ENEGEP2007_TR620461_9846.pdf> Acesso em:
31/10/2010;
PREIS, Thomás Augusto. Protótipo Gerador de Grades Horárias para Instituições
de Ensino. 2007. Disponível em: <
http://www.inf.furb.br/tcc/index.php?cd=6&tcc=1068> Acesso em: 17 de junho de
2009.
RODRIGUES, Gardênio Puiatti. Otimização de rotas através da aplicação de
algoritmos exatos e heurísticos. Barbacena: 2004. Trabalho de Conclusão de Curso
(Graduação em Ciência da Computação) – Universidade Presidente Antônio Carlos.
SILVA, Amanda Sávio Nascimento e; SAMPAIO, Rudini Menezes; ALVARENGA,
Guilherme Bastos. Uma Aplicação de Simulated Annealing para o Problema de
Alocação de Salas. 2005. Disponível em: <
http://www.dcc.ufla.br/infocomp/artigos/v4.3/art08.pdf> Acesso em: 01/11/2009.
SUCUPIRA, Igor Ribeiro. Programação por Propagação de Restrições: Teoria e
Aplicações. 2003. Disponível em:
<http://www.ime.usp.br/~igorrs/ic/relatorio/relatorio.pdf> Acesso em: 02/11/09.
SUCUPIRA, Igor Ribeiro. Métodos Heurísticos genéricos: Meta-heurísticas e Hiperheurísticas.
2004.
Disponível
em:
<
http://www.ime.usp.br/~igorrs/seminarios/metahiper.ppt> Acesso em: 15 de outubro de
2009.
TECHNIQUE. horárioescolar.com. Disponível em: <
http://www.horarioescolar.com/servlet/com.technique.hesc.Controller> Acesso em 17
de junho de 2009.