UNIVERSIDADE ANHEMBI MORUMBI
HÉLIO FERREIRA DE LIMA JÚNIOR
MARCUS VINICIUS CORRÊA
IMPLEMENTAÇÃO DE UM SISTEMA DE ALOCAÇÃO DE PROFESSORES E
DISCIPLINAS EM GRADES HORÁRIAS UTILIZANDO ALGORITMOS GENÉTICOS
São Paulo
2010
HÉLIO FERREIRA DE LIMA JÚNIOR
MARCUS VINICIUS CORRÊA
IMPLEMENTAÇÃO DE UM SISTEMA DE ALOCAÇÃO DE PROFESSORES E
DISCIPLINAS EM GRADES HORÁRIAS UTILIZANDO ALGORITMOS GENÉTICOS
Trabalho de conclusão de curso apresentado como
exigência parcial para a obtenção do título de Bacharel
em Ciência da Computação pela Universidade Anhembi
Morumbi
Orientador: Prof. Msc. Augusto Mendes Gomes Junior
São Paulo
2010
HÉLIO FERREIRA DE LIMA JÚNIOR
MARCUS VINICIUS CORRÊA
IMPLEMENTAÇÃO DE UM SISTEMA DE ALOCAÇÃO DE PROFESSORES E
DISCIPLINAS EM GRADES HORÁRIAS UTILIZANDO ALGORITMOS GENÉTICOS
Trabalho de conclusão de curso apresentado como
exigência parcial para a obtenção do título de Bacharel
em Ciência da Computação pela Universidade Anhembi
Morumbi
Aprovado
___________________________________________________________________
Prof. Msc. AUGUSTO MENDES GOMES JUNIOR
Universidade Anhembi Morumbi
___________________________________________________________________
Prof.
Universidade Anhembi Morumbi
___________________________________________________________________
Prof.
Universidade Anhembi Morumbi
RESUMO
O Problema de Alocação de Recursos é tradicionalmente muito conhecido
nas instituições de ensino. O problema consiste em conciliar professores, disciplinas
e turmas, formando uma grade horária escolar, de modo que sejam satisfeitas as
condições impostas pela instituição. A busca por uma solução manual do problema
pode demandar o esforço de muitas pessoas durante vários dias e, mesmo assim,
não gerar uma boa solução. O objetivo deste trabalho é estudar o Problema de
Alocação de Recursos, modelando e implementando uma solução para o problema.
A solução possui uma interface web para a utilização, e a estratégia para a
resolução do problema é implementada utilizando algoritmos inspirados na teoria da
evolução natural, denominados algoritmos genéticos.
Palavras-chave: Alocação de Recursos. Grade Horária. Algoritmos Genéticos.
ABSTRACT
The Problem of Resource Allocation is traditionally very popular in
educational institutions. The problem is to reconcile teachers, courses and classes,
creating a timetable, so they comply with the conditions imposed by the institution.
The search for a solution of the problem may require manual effort of many people
for several days and still not generating a good solution. The aim of this work is to
study Resource Allocation Problem, modeling and implementing a solution to the
problem. The solution has a web interface to use, and the strategy for solve the
problem was implemented using algorithms inspired by the theory of natural
evolution, called genetic algorithms.
Key words: Timetabling. Schedule. Genetic Algorithms.
LISTA DE FIGURAS
Figura 1 Pseudocódigo de um algoritmo genético ................................................... 20
Figura 2 Exemplo de cromossomos com codificação binária ................................... 20
Figura 3 Exemplo de Ponto de Cruzamento Único .................................................. 21
Figura 4 Exemplo de Cruzamento em Árvores ........................................................ 22
Figura 5 Pontos de máximos locais e global ............................................................ 23
Figura 6 Seleção proporcional a aptidão .................................................................. 23
Figura 7 Diagrama de Classes ................................................................................. 27
Figura 8 Diagrama de Entidade Relacionamento ..................................................... 28
Figura 9 Diagrama de Casos de Uso ....................................................................... 29
Figura 10 Arquitetura utilizada no desenvolvimento do RAS .................................... 30
Figura 11 Fluxograma do Modelo da Solução .......................................................... 31
Figura 12 Representação do cromossomo para o problema .................................... 32
Figura 13 Exemplo de pontuação da grade horária .................................................. 34
Figura 14 Calculo da pontuação máxima do cromossomo ....................................... 34
Figura 15 Representação dos cromossomos durante o cruzamento........................ 35
Figura 16 Representação do cromossomo após o cruzamento................................ 36
Figura 17 Mutação com disciplinas que possuem carga horária de 2 horas ............ 37
Figura 18 Mutação com disciplinas que possuem carga horária de 4 horas ............ 38
Figura 19 Ambiente Web do RAS ............................................................................. 40
Figura 20 Página de Professores cadastrados ......................................................... 41
Figura 21 Parte da janela da grade horária gerada .................................................. 41
LISTA DE GRÁFICOS
Gráfico 1 Desempenho do cromossomo durante o primeiro teste ............................. 42
Gráfico 2 Desempenho do cromossomo durante o segundo teste ............................ 43
LISTA DE TABELAS
Tabela 1 Exemplo de uma grade horária para uma turma em forma de tabela. ....... 14
Tabela 2 UC01 - Login .............................................................................................. 45
Tabela 3 UC02 - Buscar Professor ........................................................................... 45
Tabela 4 UC03 - Incluir Professor ............................................................................. 46
Tabela 5 UC04 - Alterar Professor ............................................................................ 47
Tabela 6 UC05 - Excluir Professor ............................................................................ 48
Tabela 7 UC06 - Buscar Turma ................................................................................ 49
Tabela 8 UC07 - Incluir Turma .................................................................................. 49
Tabela 9 UC08 - Alterar Professor ............................................................................ 50
Tabela 10
UC09 - Excluir Turma. ........................................................................... 51
Tabela 11
UC10 - Buscar Disciplina ....................................................................... 52
Tabela 12
UC11 - Incluir Disciplina ........................................................................ 52
Tabela 13
UC12 - Alterar Disciplina ....................................................................... 53
Tabela 14
UC13 - Excluir Disciplina ....................................................................... 54
Tabela 15
UC14 - Incluir Horário Disponível .......................................................... 55
Tabela 16
UC15 - Alterar Horário Disponível ......................................................... 56
Tabela 17
UC16 - Excluir Horário Disponível ......................................................... 57
Tabela 18
UC17 – Gerar Grade Horária ................................................................. 57
Tabela 19
UC18 – Visualizar Grade Horária .......................................................... 58
Tabela 20
Descrição da tabela PROFESSOR........................................................ 59
Tabela 21
Descrição da tabela ROLE .................................................................... 59
Tabela 22
Descrição da tabela ROLE_PROFESSOR ............................................ 59
Tabela 23
Descrição da tabela ATIVO ................................................................... 59
Tabela 24
Descrição da tabela DISCIPLINA .......................................................... 59
Tabela 25
Descrição da tabela CURSO ................................................................. 59
Tabela 26
Descrição da tabela DISCIPLINA_CURSO ........................................... 60
Tabela 27
Descrição da tabela PROFESSOR_DISCIPLINA_CURSO ................... 60
Tabela 28
Descrição da tabela TURMA ................................................................. 60
Tabela 29
Descrição da tabela SEMESTRE .......................................................... 60
Tabela 30
Descrição da tabela HORARIO ............................................................. 60
Tabela 31
Descrição da tabela PERIODO.............................................................. 61
Tabela 32
Descrição da tabela DIA_SEMANA ....................................................... 61
Tabela 33
Descrição da tabela DIA_SEMANA_HORARIO .................................... 61
Tabela 34
Descrição da tabela DISPONIBILIDADE ............................................... 61
Tabela 35
Descrição da tabela GRADE_HORARIA ............................................... 61
SUMÁRIO
1
INTRODUÇÃO ........................................................................................... 10
1.1
OBJETIVO ................................................................................................. 10
1.2
JUSTIFICATIVA ......................................................................................... 11
1.3
ABRANGÊNCIA ......................................................................................... 11
1.4
ESTRUTURA DO TRABALHO................................................................... 11
2
PROBLEMA DE ALOCAÇÃO DE RECURSOS (TIMETABLING
PROBLEM) ................................................................................................ 13
2.1
DEFINIÇÃO................................................................................................ 14
2.2
APLICAÇÕES ............................................................................................ 14
2.3
TRABALHOS RELACIONADOS ................................................................ 15
2.3.1
Timetabling com algoritmos genéticos: resultados, restrições e
exploração do paralelismo ...................................................................... 15
2.3.2
Geração Automática de Grade Horária Usando Algoritmos Genéticos:
O Caso da Faculdade de Engenharia Elétrica da UFU .......................... 16
2.3.3
Algoritmo Genético para resolver o problema de Alocação de
Recursos ................................................................................................... 17
3
ALGORITMOS GENÉTICOS ..................................................................... 19
3.1
DEFINIÇÃO................................................................................................ 19
3.2
REPRESENTAÇÃO DO CROMOSSOMO ................................................. 20
3.3
CRUZAMENTO (CROSSOVER)................................................................ 21
3.4
MUTAÇÃO ................................................................................................. 22
3.5
SELEÇÃO .................................................................................................. 23
3.6
APLICAÇÕES ............................................................................................ 24
4
MODELAGEM DO RAS (RESOURCE ALLOCATION SYSTEM) ............. 25
4.1
DESCRIÇÃO .............................................................................................. 25
4.2
ANÁLISE DE REQUISITOS ....................................................................... 26
4.3
DIAGRAMA DE CLASSES......................................................................... 26
4.4
DIAGRAMA ENTIDADE RELACIONAMENTO .......................................... 28
4.5
DIAGRAMA DE CASOS DE USO .............................................................. 29
5
IMPLEMENTAÇÃO DO RAS ..................................................................... 30
5.1
MODELO DA SOLUÇÃO ........................................................................... 30
5.2
CROMOSSOMO ........................................................................................ 32
5.3
GERAÇÃO DA POPULAÇÃO INICIAL ...................................................... 33
5.4
FUNÇÃO CUSTO ...................................................................................... 33
5.5
CRUZAMENTO (CROSSOVER)................................................................ 35
5.6
MUTAÇÃO ................................................................................................. 37
5.7
SELEÇÃO .................................................................................................. 38
5.8
ELITISMO .................................................................................................. 39
5.9
REPRESENTAÇÃO DA SOLUÇÃO........................................................... 39
6
INTERFACE WEB ..................................................................................... 40
7
TESTES ..................................................................................................... 42
8
CONCLUSÃO ............................................................................................ 44
7.1
TRABALHOS FUTUROS ........................................................................... 44
APÊNDICE A – DESCRIÇÃO DOS CASOS DE USO .............................................. 45
APÊNDICE B – DESCRIÇÃO DAS TABELAS ........................................................ 59
REFERÊNCIAS BIBLIOGRÁFICAS ......................................................................... 62
10
1
INTRODUÇÃO
A alocação de recursos (TEXEIRA, 1991) representa um grande problema
no cotidiano de muitas instituições de ensino, que é a necessidade de alocar
professores e disciplinas na grade horária. Porém, esse é um problema complexo,
haja visto que existem múltiplos objetivos, múltiplas restrições e um número grande
de variáveis a serem ponderadas (HAMAWAKI, 2005). Essa grande quantidade de
variáveis existe devido à diversidade da disponibilidade de cada professor, da carga
horária de cada disciplina, da carga horária total diária e semanal da turma/série e
da disponibilidade de laboratórios ou salas especiais (JACOB; ROCHA, 2005).
Problemas de Alocação de Recursos são de natureza combinatória e
inteira, o que dificulta o uso eficiente de algoritmos de otimização para problemas de
pequenas instancias. Na verdade, Even, Itai e Shamir (1976) afirmam que o
problema de Alocação de Recursos escolar, variante relacionada a este trabalho, é
considerado NP-Difícil para quase todas as formas que ele pode aparecer, o que
implica que esses problemas são considerados inviáveis de serem resolvidos por
métodos
otimizantes
em
tempo
computacional
hábil,
pois
o
tempo
de
processamento aumenta exponencialmente com o número de variáveis.
A solução para o problema acima é utilizar algoritmos genéticos, pois,
apesar de não encontrar a melhor solução, pode-se encontrar uma solução boa o
suficiente, utilizando baixo tempo de processamento computacional, (LOPES, 1995).
Dentre os algoritmos heurísticos existentes, o genético é um dos mais
utilizados por ser probabilístico, ou seja, a partir de uma população inicial de
soluções candidatas, ocorre uma evolução em direção a melhores soluções
aplicando operadores modelados em processos genéticos que ocorrem na natureza
(GOLDBERG, 1989).
A partir de um algoritmo genético, é implementado um sistema que realiza a
alocação de professores e disciplinas em grades horárias.
1.1
OBJETIVO
O objetivo deste trabalho é estudar o Problema de Alocação de Recursos,
modelar e implementar uma estratégia que o solucione através de um algoritmo
heurístico. Para este problema será utilizado Algoritmos Genéticos para a sua
11
resolução. O sistema será modelado utilizando técnicas de engenharia de software e
terá uma interface web, seguindo os princípios de usabilidade (NIELSEN, 1993).
1.2
JUSTIFICATIVA
O problema de alocação de recursos (Timetabling Problem) pertence a
classe de problemas NP-Completo (GAREY, 1979), ou seja, seu problema exige
grande demanda de processamento computacional de acordo com a quantidade de
dados de entrada. Quanto maior a quantidade de dados de entrada, maior é o tempo
de processamento. Diante desse grande desafio, o grupo decidiu implementar um
sistema que apresente uma solução para esse problema.
Devido a complexidade do problema e a dificuldade de sua resolução
através de técnicas de programação convencional, para a implementação da
solução foram utilizados algoritmos genéticos (GOLDBERG, 1989). Algoritmos
genéticos são uma técnica de busca utilizada para encontrar a solução exata ou
apropriada para problemas de busca e otimização.
1.3
ABRANGÊNCIA
O projeto abrange o estudo e o desenvolvimento de um sistema para
alocação de professores e disciplinas em grades horárias, utilizando os conceitos de
algoritmos genéticos, e implementado na linguagem de programação Java, com uma
interface web utilizando princípios de usabilidade, metodologias e conceitos como
Ajax (GARRET, 2005) e UML (BOOCH; JACOBSON; RUMBAUGH, 2000).
O algoritmo implementado gera a grade horária de um curso por vez, porém
o modelo de solução pode ser empregado para a geração de horários de diversos
cursos, sem distinção de duração ou quantidade de recursos.
Foram realizadas testes no sistema, buscando analisar seu desempenho e
a qualidade dos resultados obtidos pelo algoritmo em relação à quantidade de
informações que o sistema abrange.
1.4
ESTRUTURA DO TRABALHO
A estrutura do trabalho está dividida nos seguintes capítulos:
12
O capítulo 2 aborda o problema de alocação de recursos, sua definição, suas
aplicações e trabalhos relacionados.
O capítulo 3 aborda a definição de Algoritmos Genéticos, representação do
cromossomo, cruzamento (crossover), mutação, seleção e aplicações.
O capítulo 4 aborda a modelagem, contendo a descrição, casos de uso, diagrama de
classes e diagrama de seqüência do sistema desenvolvido.
O capítulo 5 apresenta a implementação do sistema desenvolvido.
O capítulo 6 demonstra os testes realizados, o ambiente de testes utilizado e a
análise dos resultados obtidos.
O capítulo 7 aborda a conclusão de nosso trabalho e apresenta sugestões de
trabalhos futuros.
13
2
PROBLEMA
DE
ALOCAÇÃO
DE
RECURSOS
(TIMETABLING
PROBLEM)
O problema de alocação de professores e disciplinas em grades horárias é
um problema de difícil solução, principalmente quando o número de disciplinas e
professores é elevado. Este problema é considerado NP-Difícil (Não-Determinístico
de tempo polinomial), ou seja, o esforço computacional necessário para a sua
resolução cresce exponencialmente com o tamanho do problema (GAREY, 1979). A
busca por uma solução manual do problema pode demandar o esforço de muitas
pessoas durante vários dias e, mesmo assim, não gerar uma boa solução
(PEREIRA, 2001).
Expressando a ordem de grandeza da complexidade de resolução de um
problema de elaboração de horários de aulas, Frangouli, Harmandas e
Stamatopoulos (1995) propuseram uma fórmula para determinar o tamanho máximo
do espaço de pesquisa expressa pela equação (1). A expressão do tamanho do
espaço de pesquisa de um problema de elaboração de horários de aulas é mostrada
a seguir:
TEP = (NDS×NAD×NSA)(ND×NAP)
(1)
onde:
TEP é o tamanho do espaço de pesquisa;
NDS é o número de dias da semana letiva;
NAD é o número de aulas diárias para o curso envolvido na distribuição das
aulas consideradas;
NSA é o número de salas de aulas disponíveis para a utilização das aulas;
ND é o número de disciplinas pertencentes ao horário de aula;
NAP é o número de aulas a serem distribuídas para cada uma das
disciplinas.
Para a elaboração deste trabalho, não foi imposta a verificação de alocação
de salas disponíveis. Desta forma, a equação (1) poderia ser apresentada
suprimindo-se a variável NSA como é mostrado na equação a seguir (2):
TEP = (NDS×NAD)(ND×NAP)
(2)
14
2.1
DEFINIÇÃO
O Timetabling Problem pode ser definido como uma lista organizada,
geralmente proposta em forma de tabela, contendo informações divididas em
períodos (horas/dia), e em cada período contendo a disciplina e professor alocado.
A Tabela 1 apresenta um exemplo da grade horária em forma de tabela.
Tabela 1
Exemplo de uma grade horária para uma turma em forma de tabela.
Hora\Dia
Segunda
Terça
Quarta
Quinta
Sexta
19:20
Empreendedorismo
Shintani
LFA
Augusto
Optativa II
IA
Marcelo
Análise de Algoritmo
Augusto
20:10
Empreendedorismo
Shintani
LFA
Augusto
Optativa II
IA
Marcelo
Análise de Algoritmo
Augusto
21:15
Empreendedorismo
Shintani
LFA
Augusto
Optativa II
TCC1
Marcelo
Análise de Algoritmo
Augusto
22:05
Empreendedorismo
Shintani
LFA
Augusto
Optativa II
TCC1
Marcelo
Análise de Algoritmo
Augusto
Sábado
Fonte: O autor (2010)
2.2
APLICAÇÕES
A alocação de professores e disciplinas é um problema complexo, de modo
que sua solução pode demandar muito tempo computacional, classificando-o como
de ordem NP-Difícil. Este tipo de problema pode ser aplicado a qualquer tipo de
instituição de ensino. Porém, a elaboração da grade horária em universidades torna
este problema mais complexo pelo fato de possuir um número de disciplinas e de
professores muito elevado.
Soluções para o problema de alocação de recursos podem ser aplicadas
em diversas áreas como na construção civil, projetos de tecnologia da informação e
até mesmo na alocação de recursos financeiros. A otimização dos recursos
disponíveis pode ser útil para o sucesso de qualquer projeto.
15
2.3
TRABALHOS RELACIONADOS
O problema de alocação de recursos tem sido muito estudado, devido ao
grande número de possíveis aplicações, nesta seção são apresentados alguns
trabalhos relacionados ao tema.
2.3.1
Timetabling com algoritmos genéticos: resultados, restrições e
exploração do paralelismo
O Trabalho de Fucilini, Maruani e Rebonatto (2008) buscou detalhar uma
solução para o problema de timetabling de professores e disciplinas, utilizando um
novo modelo de algoritmos genéticos e solução que utiliza o paralelismo durante a
execução.
A metodologia utilizada foi definir a representação do cromossomo como um
vetor bidimensional, separado por níveis e slot de tempo, determinando peso do slot,
peso dos indivíduos da população, que é composta por professores, disciplinas,
horas, feriados, disponibilidades, etc., visando verificar os resultados obtidos ao final
da execução.
As informações a serem manipuladas pelo algoritmo genético como dados
dos professores, das disciplinas, horários disponíveis, e outras informações
relevantes ficam guardados em uma base de dados, mas durante sua manipulação,
essas informações são armazenadas na memória RAM (Random Access Memory),
visando alcançar um melhor desempenho durante a execução, ao final do
processamento, os resultados são armazenados no banco de dados.
A implementação do sistema foi feita em C++ utilizando o compilador GNU
(GNU Is Not Unix) G++ e modelado em MySQL.
Os resultados desejados foram obtidos. Contudo, o algoritmo genético
utilizado consegue gerar os horários de apenas 1 (um) curso por vez.
A limitação de somente 1 (um) curso por execução, acaba deixando o
algoritmo pouco eficiente, onde o último curso a ser gerado pode ter de esperar por
muito tempo para ter sua grade gerada. Outro problema encontrado foi a limitação
da alocação de disciplinas, onde só se pode alocar as que possuem créditos pares,
pelo fato de ter sido determinado 2 horas/aula. A solução para esse problema foi a
mudança na representação do cromossomo. O cromossomo se divide em 1 (um)
16
vetor de cursos, 1 (um) vetor de níveis de cursos e 1 (um) vetor de relação de
disciplinas em horários. Porém, essa nova representação acabou gerando um
consumo de memória elevado. Sua solução foi implementar um algoritmo genético
utilizando paralelismo, visando aumentar o desempenho durante a procura por
soluções do algoritmo genético.
2.3.2
Geração Automática de Grade Horária Usando Algoritmos Genéticos:
O Caso da Faculdade de Engenharia Elétrica da UFU
O objetivo do trabalho de Hamawaki (2005) foi criar um aplicativo, do qual
seria possível a extração de informações relevantes com relação à proposta
escolhida, constando de uma representação genética para o problema de geração
automática de horário de uma instituição de ensino superior, levando em
consideração a limitação dos recursos, com base em suas informações, utilizando
Algoritmos Genéticos para alcançar uma solução viável.
O aplicativo desenvolvido é composto pelos componentes: algoritmo
genético, responsável pela implementação das operações genéticas (seleção,
elitismo, mutação, cruzamento e cálculo de aptidão) e também pelo processo como
um todo (início/fim), base de dados, local onde é armazenado o conhecimento
necessário para processamento do problema em questão, lista de disciplinas,
professores e suas correspondências, restrições de dias e horários para cada aula,
número de dias na semana e preferências de dias e horários de cada professor.
O funcionamento do sistema desenvolvido, segundo o autor, foi considerado
muito simples. De acordo com o tamanho da população são criadas as populações
das dez espécies (que correspondem aos 10 períodos do curso de graduação de
engenharia elétrica). Nesta etapa as Bases de Dados são acessadas para criação
dos indivíduos (grades horárias). Após esta etapa inicial, o Algoritmo Genético segue
o fluxo padrão. É realizada a seleção, cálculo de aptidão e aplicação dos operadores
genéticos. A seguir é efetuado o teste de evolução entre as espécies das
populações. As espécies com maior aptidão continuam participando da verificação.
A ferramenta desenvolvida reduziu o tempo requerido para a elaboração da
grade horária, e a partir da análise dos resultados obtidos, o autor pode concluir que
as técnicas utilizadas favoreceram a obtenção de uma solução satisfatória e
eficiente para o problema.
17
2.3.3
Algoritmo Genético para resolver o problema de Alocação de Recursos
O trabalho de Colorni, Dorigo e Maniezzo (1992) visou a apresentação da
aplicação de um algoritmo genético adaptado para resolver um problema de
alocação de recursos.
Para a elaboração do algoritmo e investigação do problema, o autor utilizou
a tabela de horário de aulas de uma escola italiana de ensino médio. Porém, as
idéias apresentadas neste trabalho poderão ser aplicadas para a solução de outros
problemas de alocação de recursos. A construção de uma tabela de horários para
uma escola italiana de ensino médio pode ser decomposta na formulação de
diversas tabelas de horários relacionadas.
Este problema tem sido abordado através da utilização de programação
linear com variáveis binárias, utilizando algumas heurísticas. Segundo o autor, se o
problema fosse abordado utilizando algoritmos padrões, isto é, definindo variáveis
binárias xijk, o problema seria representado por 6000 variáveis, o que o tornaria
intratável. Por esse motivo, o autor decidiu abordá-lo por meio de um algoritmo
evolutivo e estocástico, ou seja, através de um algoritmo genético.
Foram encontradas algumas dificuldades na aplicação de algoritmos
genéticos para problemas com restrições de otimização combinatória. A mais
relevante delas foi de que os operadores de crossover e de mutação previamente
definidos poderiam gerar soluções inviáveis.
O problema foi representado através de matrizes, e as restrições foram
gerenciadas da seguinte forma:
• Pelos operadores genéticos, de modo que o conjunto de horas a ser
lecionadas por cada professor, atribuídos na fase de inicialização, não
poderiam ser alterados pela aplicação dos operadores genéticos;
• Pelo algoritmo de filtragem, de modo que a inviabilidade causada pela
aplicação de operadores genéticos são total ou parcialmente eliminadas
pela filtração;
• Pela função objetivo, de modo que a pressão seletiva seria utilizada para
limitar o número de indivíduos com inviáveis.
18
O programa utilizado para os experimentos do algoritmo foi escrito na
linguagem de programação C, e foi executado em um PC utilizando as
configurações padrões.
Foi observado que o algoritmo enquanto explora zonas promissoras do
espaço de busca, sempre identifica soluções viáveis dentro de pequenas iterações.
19
3
ALGORITMOS GENÉTICOS
Os algoritmos genéticos (GOLDBERG, 1989) são uma técnica de busca
utilizada para encontrar a solução exata ou apropriada para problemas de busca e
otimização. Os algoritmos genéticos foram inspirados nos conceitos da teoria da
evolução (DARWIN, 1859) como mutação, seleção natural, hereditariedade e
recombinação (crossing over), de modo que se possa chegar à solução de um
problema através deles, utilizando um processo evolucionário onde não se encontra
a solução, e sim a desenvolve.
3.1
DEFINIÇÃO
Os algoritmos genéticos são implementados em uma simulação de
computador em que uma população de representações abstratas de soluções
candidatas para um problema de otimização evolui em direção as melhores
soluções. Tradicionalmente, as soluções são representadas em seqüências de 0s
(zeros) e 1s (uns), mas outras formas de representar são possíveis.
A evolução geralmente inicia a partir de uma população de indivíduos
gerados aleatoriamente e acontece em várias gerações. Em cada geração, a aptidão
de cada indivíduo é avaliada, alguns indivíduos da população são selecionados de
acordo com sua aptidão, e modificados através de recombinações e mutações
randômicas para formar uma nova população.
Esta nova população é utilizada na próxima iteração do algoritmo.
Geralmente, o algoritmo termina quando um número máximo de gerações foi
produzido, ou um nível satisfatório de robustez é alcançado pela população. Se o
algoritmo terminar devido ao número máximo de geração, uma solução satisfatória
pode não ter sido alcançada.
Na Figura 1 é ilustrado o pseudocódigo de um algoritmo genético.
20
Figura 1 Pseudocódigo de um algoritmo genético. Fonte: OBITKO e SLAVÍK (1999)
3.2
REPRESENTAÇÃO DO CROMOSSOMO
Nos algoritmos genéticos os cromossomos são um conjunto de parâmetros
que definem uma proposta de solução para o problema que o algoritmo tenta
resolver. O cromossomo é geralmente representado por uma seqüência simples de
caracteres 0s e 1s, apesar de outras formas de representações também serem
utilizadas.
A Codificação Binária é a forma mais comum de representação do
cromossomo devido à sua relativa simplicidade, e principalmente porque foi a forma
que os primeiros pesquisadores de algoritmos genéticos utilizaram.
Na Figura 2 é ilustrado um exemplo da representação do cromossomo com
codificação binária.
Figura 2 Exemplo de cromossomos com codificação binária. Fonte: O autor (2010)
Outras formas de representação do cromossomo também são utilizadas,
entre elas estão a Codificação por Permutação (que pode ser utilizada em
problemas que envolvem ordenação como o “Problema do Caixeiro-Viajante”
(APPLEGATE, 2006) ou problemas de ordenação de tarefas), Codificação de
Valores (que pode ser utilizada em problemas em que são utilizados valores mais
complexos, como números reais) e a Codificação em Árvore (que é principalmente
21
utilizada para desenvolver programas ou expressões, ou seja, é utilizada para a
programação genética).
3.3
CRUZAMENTO (CROSSOVER)
Em algoritmos genéticos, crossover é um operador genético utilizado para
combinar a programação de um cromossomo ou cromossomos de uma geração
para a seguinte. É análogo à reprodução e cruzamento biológico em que os
algoritmos genéticos são baseados.
Se somente o operador de reprodução atuar, a população tenderá a se
tornar mais homogênea a cada geração. O operador de cruzamento é incluído em
um algoritmo genético pelo fato de introduzir novas estruturas, recombinando
estruturas já existentes e por ter um efeito de seleção, pois elimina esquemas de
baixa adaptação.
Para cada forma de representação do organismo existem diversas formas
de cruzamento.
Algumas formas de cruzamento para organismos representados através da
Codificação Binária podem ser o Ponto de Cruzamento Único, que pode ser visto um
exemplo na Figura 3, Dois pontos de cruzamento, Cruzamento Uniforme e o
Cruzamento Aritmético.
Figura 3 Exemplo de Ponto de Cruzamento Único. Fonte: MIRANDA (1998)
22
Organismos representados através da Codificação por Permutação
geralmente são cruzados através do Ponto de Cruzamento Único ou Mudança de
Ordem.
Para organismos representados através da Codificação de Valores, podem
ser utilizadas todas as técnicas de cruzamento utilizadas pela Codificação Binária.
Os organismos representados através da Codificação em Árvores
geralmente são cruzados através do Cruzamento em Árvores.
A Figura 4 apresenta um exemplo do cruzamento em árvores.
Figura 4 Exemplo de Cruzamento em Árvores. Fonte: OBITKO (1999)
3.4
MUTAÇÃO
Assim como o operador crossover, a mutação também é um operador
utilizado pelos algoritmos genéticos. A mutação é utilizada para manter a
diversidade genética de uma geração para a outra, de forma semelhante a uma
mutação biológica.
Seu uso exagerado não é recomendável, pois pode reduzir a evolução a
uma busca totalmente aleatória, de modo que é consistida apenas em alterar valores
dos indivíduos de 0 para 1 e vice-versa, buscando explorar regiões não atingidas do
espaço de busca e fugir de valores mínimos e máximos (Figura 5) “viciados”,
chamados de locais. Dessa forma, a mutação deve ser utilizada em uma proporção
de 0.5% a 5% do total de bits do indivíduo.
23
Figura 5 Pontos de máximos locais e global. Fonte: ESPERIDIÃO (2003)
3.5
SELEÇÃO
A seleção consiste na escolha dos indivíduos pertencentes à população
atual que serão responsáveis pela produção da geração posterior.
Existem diversas formas de seleção de indivíduos, sendo que as mais
comuns
são:
seleção
por
torneio,
onde
são
escolhidos
dois
indivíduos
aleatoriamente e o melhor é selecionado, e seleção proporcional a aptidão, também
conhecido como Roleta, onde geralmente a aptidão do indivíduo é determinada
através do cálculo da função objetivo, que depende da especificação do projeto e se
inspira na percepção conclusiva da probabilidade de dois indivíduos bons gerarem
um filho bom é maior do que a de dois indivíduos ruins gerarem um filho bom.
A Figura 6 apresenta um exemplo de seleção por aptidão.
Figura 6 Seleção proporcional a aptidão. Fonte: O autor (2010)
24
3.6
APLICAÇÕES
Os algoritmos genéticos possuem uma larga aplicação em diversas áreas
científicas. Eles podem ser utilizados para solucionar problemas complexos (como
problemas NP-Difíceis), para o aprendizado de máquinas e também para o
desenvolvimento de programas simples.
Uma das vantagens dos algoritmos genéticos é o seu paralelismo. O
algoritmo genético percorre o espaço das soluções utilizando mais indivíduos de
forma que eles são menos propensos a se direcionar para um extremo local do que
os outros métodos.
Algumas das aplicações mais comuns para os algoritmos genéticos são:
Sistemas Dinâmicos não Lineares (HORITA, 2002), Projeto de Redes Neurais
(WILSON, 1991), Trajetória de Robôs (SANTOS; SARAMAGO; STEFFEN, 2004),
Desenvolvimento
de
programas
em
LISP
(List
Processing),
Planejamento
Estratégico (KEMP, 1995), Autômatos auto-programáveis (MIRANDA, 2004),
Gerenciamento de Redes (MIRANDA, 2004), entre outras aplicações.
25
4
MODELAGEM DO RAS (RESOURCE ALLOCATION SYSTEM)
Neste capítulo, para a modelagem do problema, são apresentados os
diagramas com as definições dos casos de uso e o modelo da base de dados do
RAS. Também é descrita a estratégia utilizada para a resolução do problema
proposto, bem como as técnicas utilizadas durante seu desenvolvimento.
De modo a obter uma melhor compreensão do problema e especificar de
forma mais clara aos desenvolvedores, para a modelagem do RAS, foram utilizadas
técnicas de Engenharia de Softwares (NAUR; RANDEL, 1969) como a Modelagem
de Softwares Orientada a Objetos utilizando a UML (BOOCH; JACOBSON;
RUMBAUGH, 2000).
4.1
DESCRIÇÃO
Devido à complexidade conhecida na literatura para a resolução de
Problemas de Alocação de Recursos (IBARAKI; KATOH, 1988), neste trabalho foi
utilizado algoritmos genéticos (GOLDBERG, 1989), como uma técnica de
Inteligência Artificial para a solução de problemas de otimização, com alto grau de
complexidade.
O RAS foi modelado e implementado utilizando técnicas de Modelagem de
Softwares Orientada a Objetos (COAD; YOURDON, 1991).
Problemas de Alocação de Recursos são problemas de otimização, onde,
conhecida a quantidade de recursos disponíveis, pretende-se determinar a forma de
alocá-los por diversas atividades independentes otimizando a função objetivo que a
ser considerada (TEIXEIRA, 1991).
A alocação de recursos é um dos problemas clássicos abordados pela
Pesquisa Operacional (HILLIER; LIEBERMAN, 1990). Este trabalho apresenta um
sistema de alocação de professores em grades horárias utilizando Algoritmos
Genéticos. O método proposto é aplicado no estudo de caso de alocação de
professores em uma instituição fictícia, podendo ser aplicado em situações reais,
pelo fato de não se basear em uma instituição específica.
26
4.2
ANÁLISE DE REQUISITOS
Neste capítulo são apresentados os requisitos funcionais e não funcionais
que o RAS deve ter. Os requisitos aqui contidos foram levantados com base no
conceito geral de um problema de alocação de professores em grades horárias,
podendo ser incrementados na medida em que o sistema agregar mais recursos e
funcionalidades.
Requisitos Funcionais:
•
O sistema deverá permitir a autenticação de usuários a partir da
digitação de Id do usuário e senha pré-cadastrados;
•
O sistema deverá permitir a manutenção (inclusão, atualização, busca e
exclusão de registros) de todas as tabelas através de interface visual;
•
O sistema deverá permitir a geração de grade horária para um curso;
•
O sistema deverá permitir a visualização da grade horária de um curso;
Requisitos Não-Funcionais:
•
O sistema deverá possuir uma interface amigável;
•
O sistema deverá inabilitar a sessão do usuário após 15 minutos de
inatividade;
4.3
DIAGRAMA DE CLASSES
As classes de domínio representam conceitos do mundo real relacionados
ao problema que nosso sistema deve resolver (SOUZA, 2010). São as informações
que precisamos manipular e armazenar para o funcionamento correto da aplicação.
As classes de domínio do RAS estão presentes no diagrama da Figura 7.
O pacote visão contém as páginas Web e outros artefatos relacionados à
interface gráfica com o usuário. Ele interage diretamente com o pacote controle,
onde se encontram as classes de ação que são responsáveis por fazer o intermédio
entre a interface gráfica e a camada de negócio. As classes de aplicação
implementam os casos de uso e manipulam os objetos de domínio do problema. O
pacote de persistência é responsável por armazenar os dados dos objetos de
domínio na base de dados.
27
Figura 7 Diagrama de Classes. Fonte: O autor (2010)
O RAS armazenará informações sobre professores, disciplinas e turmas, de
modo a relacioná-las gerando uma grade horária além de outros dados que também
são pertinentes ao problema.
28
4.4
DIAGRAMA ENTIDADE RELACIONAMENTO
Diagramas Entidade Relacionamento (CHEN, 1976) são a representação de
todos os elementos essenciais abstraídos no processo de analise de sistemas. Uma
das principais técnicas de modelagem ER é documentar os tipos de entidade e
relacionamento
de
uma
forma
gráfica
chamada,
diagrama
de
Entidade
Relacionamento.
As entidades devem interagir de modo a contemplar os requisitos do
negócio, mantendo os dados armazenados de forma integra e sem redundâncias. O
diagrama a seguir representa o modelo ER de uma instituição hipotética, porém, o
mesmo poderá ser aplicado para uma instituição real. Os detalhes das tabelas e de
seus atributos se encontram no apêndice deste trabalho.
Figura 8 Diagrama de Entidade Relacionamento. Fonte: O autor (2010)
29
4.5
DIAGRAMA DE CASOS DE USO
Diagramas de caso de uso descrevem as funcionalidades propostas para o
sistema que será projetado. Casos de uso são interações entre os agentes externos
e o sistema, desse modo pode haver um ou mais casos de uso em cada diagrama.
Jacobson (2004) define os casos de uso como “documento narrativo que
descreve a seqüência de eventos de um ator que usa um sistema para completar
um processo”.
O diagrama dos casos de uso referentes ao RAS está presente na Figura 9.
Figura 9 Diagrama de Casos de Uso. Fonte: O autor (2010)
O administrador pode efetuar alterações, inclusões e exclusões em todas as
tabelas, e os professores poderão apenas incluir, alterar ou excluir suas
disponibilidades, além de visualizar as grades horárias geradas pelo sistema. Os
detalhes deste diagrama se encontram no apêndice deste trabalho.
30
5
IMPLEMENTAÇÃO DO RAS
O RAS foi implementado utilizando a tecnologia JEE6 (Java Enterprise
Edition 6) devido à sua robustez e confiabilidade, além da facilidade no
desenvolvimento de aplicações complexas. A arquitetura do sistema é baseada no
padrão de projetos Service Layer (FOWLER, 2002). A Figura 10 mostra os diferentes
pacotes que compõem a arquitetura.
Figura 10 Arquitetura utilizada no desenvolvimento do RAS. Fonte: O autor (2010)
As sessões contidas neste capítulo definem o modelo da solução utilizada,
a representação do cromossomo, e demonstram os passos seguidos para a geração
da população inicial, bem como a função custo associada ao critério de seleção.
Também são apresentados os processos de seleção, cruzamento e mutação
relacionados ao RAS.
5.1
MODELO DA SOLUÇÃO
O modelo da solução é apresentado em forma de fluxograma na Figura 11.
A seguir são apresentadas definições de seu funcionamento:
o Geração dos dados de entrada como matriz (representando grades
horárias).
o Verifica se o número de indivíduos é menor ou igual a 50.
31
o Realiza a operação de cruzamento.
o Realiza a operação de mutação.
o Avalia os indivíduos da população.
o Seleciona os indivíduos que formarão a próxima geração.
o Verifica se um dos critérios de parada foi atingido.
o Fim da execução e apresentação dos resultados.
Figura 11 Fluxograma do Modelo da Solução. Fonte: O autor (2010)
32
5.2
CROMOSSOMO
O cromossomo foi modelado baseado no problema proposto, onde é
representado por um conjunto de listas pré-definidas, que estão relacionadas.
A Figura 12 ilustra como é representado o cromossomo utilizado no RAS.
Figura 12 Representação do cromossomo para o problema. Fonte: O autor (2010)
Os cursos são representados por uma lista, que é um array que contém N1
objetos, cada um representando um curso qualquer. Para cada curso, pode existir
N2 turmas, dependendo da quantidade de semestres que o curso possui.
As turmas são representadas por uma lista, que é um array que contém N2
objetos, cada um representando uma turma qualquer. Para cada turma, pode
existem N3 disciplinas.
As disciplinas são representadas por uma lista, que é um array que contém
N3 objetos, cada um representando uma disciplina qualquer. Para cada disciplina,
pode existir N4 professores que podem lecioná-la.
Os professores são representados por uma lista, que é um array que
contém N4 objetos, cada um representando um professor qualquer. Para cada
professor, pode existir N5 disponibilidades.
As disponibilidades são representadas por uma lista, que é um array que
contém N5 objetos, cada um representando uma disponibilidade qualquer. Cada
disponibilidade representa um objeto que contém o dia da semana e horário.
33
5.3
GERAÇÃO DA POPULAÇÃO INICIAL
A população inicial é gerada através de um algoritmo que realiza a alocação
de professores e disciplinas de um curso em uma matriz que representa uma grade
horária para todas as turmas do curso. A geração da população inicial é a base para
a execução de um algoritmo genético.
No modelo de solução proposto, durante sua execução são relacionados
professores, disciplinas e turmas de forma aleatória, de modo que as restrições
impostas pelo modelo sejam respeitadas. Ao final da criação da população inicial,
haverá condições suficientes para a aplicação dos operadores genéticos, de modo a
gerar novas populações de melhor qualidade.
5.4
FUNÇÃO CUSTO
Os modelos de algoritmo genético tradicional, em geral possuem uma
tabela de pontuação positiva e negativa para cada caso do cromossomo.
Nosso modelo possui uma validação diferenciada, pois foi elaborado um
algoritmo que faz a avaliação das disponibilidades de cada professor no momento
em que ele será devidamente alocado para uma grade horária em um dia da
semana e horário qualquer.
Essa função é essencial para a alocação correta dos professores e
disciplinas nas grades horárias, impossibilitando a alocação de professores em dias
que não possuem disponibilidade, ou com disciplinas que não possuem
conhecimento e também caso não possuam carga horária suficiente para lecionar
mais disciplinas.
A função custo também trata da pontuação das grades horárias quando
preenchidas. Quando cada slot da grade horária é preenchido, a pontuação da
grade horária ganha 2 pontos. Quando é detectado um slot em branco, perde 2
pontos. Com essa pontuação, com a quantidade de horas letivas por dia, e a
quantidade de dias letivos por semana, a grade horária pode chegar até 40 pontos
quando preenchida por completo, ou até -40 pontos quando não possui nenhum
professor alocado. A Figura 13 mostra um exemplo da pontuação da grade horária.
34
Figura 13 Exemplo de pontuação da grade horária. Fonte: O autor (2010)
Com base nessa pontuação, é possível saber qual grade horária possui
mais professores alocados, permitindo assim saber quando o cromossomo é uma
boa solução gerada, ou seja, quando todas as grades horárias estiverem
preenchidas.
O calculo da pontuação máxima do cromossomo é apresentado na figura
abaixo:
Figura 14 Calculo da pontuação máxima do cromossomo. Fonte: O autor (2010)
Caso o curso possua 8 semestres, e as aulas ocorram 5 vezes por semana,
4 horas por dia, então a pontuação máxima possível para o cromossomo ser uma
solução completa é 320 pontos.
35
5.5
CRUZAMENTO (CROSSOVER)
A operação de cruzamento projetada para o RAS difere das operações
tradicionais, devido a representação do cromossomo utilizada.
O cruzamento é realizado logo após a função de seleção, onde serão
escolhidos 2 cromossomos da população. O cruzamento é realizado a partir das
grades horárias de cada cromossomo, onde é verificada a pontuação de cada uma e
comparando qual das grades possui maior pontuação. A Figura 15 ilustra o exemplo.
Figura 15 Representação dos cromossomos durante o cruzamento. Fonte: O autor (2010)
36
Cada grade horária possui uma pontuação, que corresponde ao seu
preenchimento. Após o algoritmo selecionar as grades horárias com a melhor
pontuação, o cromossomo filho é gerado com partes de seus ascendentes, como
pode ser visto na Figura 16.
Figura 16 Representação do cromossomo após o cruzamento. Fonte: O autor (2010)
Após o cromossomo filho ser gerado, é possível que algumas alocações
inválidas ocorram, como professores com carga horária excedida ou alocação de
37
professores em um mesmo dia para mais de uma turma. Esses casos são validados
por um algoritmo que se encarrega de analisá-los quando o cromossomo filho é
gerado, removendo as alocações não permitidas.
5.6
MUTAÇÃO
A mutação visa obter uma boa distribuição dentro de cada geração do
cromossomo. Após gerar um cromossomo filho, é selecionada de forma aleatória
uma turma que não esteja preenchida por completa, o que caracteriza em uma
porcentagem baixa na execução do algoritmo.
Diferente dos operadores de mutação tradicional, essa função de mutação
não altera apenas o valor do cromossomo. Como a representação do cromossomo é
específica para um problema, a função da mutação, nesse caso, é alterar o
professor alocado para uma disciplina.
No caso das disciplinas que possuem 2 horas/aula, a mutação ocorre dentro
desse cromossomo, onde é selecionada de forma aleatória uma posição no
cromossomo que representa uma grade horária de uma turma. A função de mutação
se encarrega de chegar se existe disponibilidade do professor ser reposicionado em
outro slot da grade horária, favorecendo os professores que serão alocados
futuramente. Pode ser visto um exemplo dessa mutação na Figura 17.
Figura 17 Mutação com disciplinas que possuem carga horária de 2 horas. Fonte: O autor (2010)
38
Caso a disciplina possua 4 horas/aula, a função de mutação seleciona de
forma aleatória um slot qualquer de uma grade horária do cromossomo, e então é
analisado dentro da disciplina naquele slot selecionado quais outros professores,
que podem lecioná-la, estão disponíveis para aquele dia/hora e possuem carga
horária suficiente. Se for encontrado algum professor que corresponda esses
requisitos, então é feita a mutação entre os professores, em todos os slots da grade
horária que possuir a disciplina correspondente. Pode ser visto um exemplo dessa
mutação na Figura 18.
Figura 18 Mutação com disciplinas que possuem carga horária de 4 horas. Fonte: O autor (2010)
5.7
SELEÇÃO
A seleção dos indivíduos é baseada na pontuação de cada indivíduo da
população, ou seja, os indivíduos que possuem melhor pontuação têm maior chance
de serem selecionados para formar a nova população.
A pontuação de um cromossomo é calculada pela soma da pontuação de
todas as grades horárias que ele possui. Com isso, a chance de obter um novo
cromossomo filho com boa pontuação se torna maior.
39
5.8
ELITISMO
Após cada realização das operações de seleção e cruzamento, é gerado
um novo cromossomo filho. Esse cromossomo é avaliado, calculando sua pontuação
e comparado com o melhor cromossomo já obtido. Se o novo cromossomo gerado
obtiver uma pontuação melhor, então ele passa a ser o novo melhor cromossomo
encontrado. Ele será guardado, podendo assim aparecer nas próximas populações
geradas.
5.9
REPRESENTAÇÃO DA SOLUÇÃO
As soluções são representadas por cromossomos, onde cada cromossomo
possui uma lista de turmas e cada turma possui uma matriz que representa a sua
grade horária.
Essa matriz contendo uma grade horária de cada turma para um curso
hipotético é feita preenchida por uma relação entre professores e disciplinas em
horários compatíveis de acordo com o período de aula da turma e as
disponibilidades dos professores.
Cada cromossomo é uma solução, porém, quando um cromossomo
conseguir preencher todas as suas grades horárias, esse cromossomo é
considerado uma solução boa ou satisfatória para o problema.
40
6
INTERFACE WEB
O RAS foi implementado para funcionar em um ambiente web, permitindo
que seu acesso possa ser realizado de qualquer dispositivo com acesso a internet.
O ambiente disponibiliza algumas funcionalidades para o usuário logado. O
administrador tem permissão para alterar todas as informações do sistema, inserir e
excluir dados. Os professores podem tem permissão apenas para alterar suas
disponibilidades, e visualizar as grades horárias geradas.
A figura 19 ilustra como é representado o sistema em um ambiente web.
Figura 19 Ambiente Web do RAS. Fonte: O autor (2010)
O menu apresenta todas as categorias que envolvem o sistema, ou seja, o
usuário, no caso o administrador, pode escolher o tipo de categoria que deseja
acessar, sendo direcionado para uma tela que lhe permite listar, inserir, visualizar,
alterar e excluir dados.
A figura 20, por exemplo, mostra a página que lista os Professores
cadastrados.
41
Figura 20 Página de Professores cadastrados. Fonte: O autor (2010)
Após inserir todos os dados essenciais para gerar uma grade horária, o
administrador pode escolher no menu a opção “Gerar Grade Horária”. Uma nova
janela irá abrir, apresentando a grade gerada (Figura 21).
Figura 21 Parte da janela da grade horária gerada. Fonte: O autor (2010)
42
7
TESTES
O teste do algoritmo genético adotado para o problema se baseia em
analisar a qualidade do cromossomo gerado a cada nova população, ou seja, seu
desempenho após cada geração e a quantidade de gerações realizadas até obter
uma boa solução.
Os testes foram feitos com uma base de dados representada por 25
professores, 46 disciplinas, 8 turmas e uma média de 3 dias disponíveis para cada
professor por semana, gerando uma solução para apenas 1 curso.
No primeiro teste, representado pelo Gráfico 1, a solução foi obtida após ter
realizado a geração de 29 novas populações.
300
250
200
150
100
50
0
1
Gráfico 1
3
5
7
9
11 13 15 17 19 21 23 25 27 29
Desempenho do cromossomo durante o primeiro teste. Fonte: O autor (2010)
O cromossomo iniciou com uma pontuação de 168. Sua pontuação mais
baixa foi de 144 e após a 17 gerações, apresentou menos instabilidade durante o
crescimento, até atingir a pontuação máxima.
O segundo teste, representado pelo Gráfico 2, conseguiu obter uma solução
após 27 gerações.
43
300
250
200
150
100
50
0
1
Gráfico 2
3
5
7
9
11
13
15
17
19
21
23
25
27
Desempenho do cromossomo durante o segundo teste. Fonte: O autor (2010)
O cromossomo iniciou com uma pontuação de 208. Sua pontuação mais
baixa foi de 168 e conseguiu atingir uma boa solução após 27 gerações.
Os testes realizados demonstraram diferentes desempenhos. Isso se deve
devido a disponibilização da grade horária da população gerada. Cada nova
população gerada, as grades horárias são preenchidas de forma aleatória, mas
validando os requisitos necessários dos professores para realizar a alocação de
acordo com sua disponibilidade.
Quando isso é feito, a cada nova geração, o algoritmo trabalho sempre com
1 cromossomo escolhido, como sendo o melhor da população. Esse cromossomo,
enquanto for um bom cromossomo, permanecerá nas populações seguintes, até que
seja gerado um cromossomo melhor.
Em média, o algoritmo conseguiu chegar a uma solução satisfatória em
aproximadamente 18 segundos. Mas esse tempo depende da capacidade de
processamento do servidor e da quantidade de dados utilizados.
Em alguns casos, os testes não conseguiram chegar a uma solução
completa. Nesses casos o algoritmo gera uma grade horária com o melhor
cromossomo da população, mesmo que algumas grades horárias não estejam
preenchidas por completo.
44
8
CONCLUSÃO
O objetivo deste trabalho era estudar o Problema de Alocação de Recursos
e modelar e implementar uma estratégia que o solucionasse através de um
Algoritmo Genético.
Embora a aplicação de algoritmos genéticos para a resolução de problemas
complexos, que exigem grande quantidade de processamento computacional não
garanta um resultado ótimo, com este trabalho foi possível constatar que para
problemas computacionalmente inviáveis o uso de algoritmos genéticos pode gerar
resultados muito satisfatórios.
A alocação de professores em grades horárias, quando feita de forma
manual pode demandar diversos dias de esforço para os responsáveis pela tarefa.
Com a utilização de técnicas heurísticas, como algoritmo genético neste caso,
podem-se descobrir boas soluções em poucos minutos. Apesar da utilização de
dados fictícios para a execução dos testes e geração das soluções, é possível
executar o algoritmo utilizando dados reais.
Vale ressaltar que problemas de alocação de recurso pertencem a classe
de problemas NP-Completo, que são amplamente conhecidos no âmbito
computacional pelo seu nível de complexidade. O objetivo deste trabalho utiliza
conceitos não triviais para a resolução de problemas permitindo que a solução seja
atingida com maior facilidade.
7.1
TRABALHOS FUTUROS
Como trabalhos futuros sugerem-se alguns outros objetivos com base no
RAS como os citados abaixo:
•
A geração da grade horária para diversos cursos simultaneamente.
•
Utilização de mais parâmetros para o algoritmo genético, tais como
campus, nota de avaliação do professor em relação à turma, entre
outros.
•
Melhorar o front-end utilizando técnicas de drag and drop para aprimorar
a usabilidade do sistema.
•
Implementar uma solução distribuída para instancias muito grandes do
Problema de Alocação de Recursos.
45
APÊNDICE A – DESCRIÇÃO DOS CASOS DE USO
Caso de Uso:
UC01 – Login
Sumario:
Este caso de uso inicia-se quando o usuário deseja incluir,
alterar ou excluir algum registro do sistema.
Atores:
Administrador, Professor
Pré-condições:
O usuário estar cadastrado no sistema.
Fluxo Principal:
1.
O usuário acessa o sistema através do endereço
de acesso.
2.
O usuário preenche os campos Usuário e Senha.
3.
O usuário clica no botão Login.
4.
O usuário é direcionado para a pagina inicial da
aplicação e o caso de uso termina.
Fluxos Alternativos:
Fluxos de Exceção:
Não se aplica.
4a. Dados inválidos nos campos de login
4a1. O usuário será direcionado para a página de
login inválido
Tabela 2
UC01 - Login. Fonte: O autor (2010)
Caso de Uso:
UC02 – Buscar Professor
Sumario:
Este caso de uso inicia-se quando o usuário deseja buscar
um professor no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita a busca por um professor.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para localizar um professor cadastrado.
3.
O usuário informa os dados referentes à busca por
um professor e pressiona o botão “Procurar”.
4.
O sistema retorna os registros referentes aos
dados informados pelo usuário.
Fluxos Alternativos:
Fluxos de Exceção:
Tabela 3
UC02 - Buscar Professor. Fonte: O autor (2010)
46
Caso de Uso:
UC03 – Incluir Professor
Sumario:
Este caso de uso inicia-se quando o usuário deseja
registrar um novo professor no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita o cadastramento de um
professor.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para fazer o cadastro completo do
professor.
3.
O usuário informa os dados referentes à inclusão
do professor, confere os dados digitados e submete
a gravação do cadastro.
4.
UC02.
5.
O sistema solicita a confirmação para a gravação.
6.
O usuário confirma a gravação.
7.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
6a. O usuário desiste de cadastrar o professor.
6a1. O usuário pressiona o botão “Cancelar”
6a2. O cadastramento é cancelado e o caso de
uso é encerrado.
Fluxos de Exceção:
4a. Dados inválidos na ficha de preenchimento.
4a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
4a2. Retorna ao passo 2 do fluxo principal.
4b. O professor já está cadastrado no sistema
4b1. O sistema retorna a seguinte mensagem
“Professor já cadastrado.”
Tabela 4
UC03 - Incluir Professor. Fonte: O autor (2010)
Caso de Uso:
UC04 – Alterar Professor
Sumario:
Este caso de uso inicia-se quando o usuário deseja alterar
o registro de um professor cadastrado no sistema.
47
Atores:
Administrador
Pré-condições:
UC01 e haver ao menos um professor previamente
cadastrado.
Fluxo Principal:
1.
UC02.
2.
O sistema lista os professores relacionados aos
parâmetros
de
busca
informados,
o
usuário
seleciona o professor desejado e pressiona o botão
“Alterar”.
3.
O usuário informa os dados referentes à alteração
dos dados do professor, confere os dados digitados
e submete a alteração dos dados do cadastro.
4.
O sistema solicita a confirmação para a gravação.
5.
O usuário confirma a gravação.
6.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
5a. O usuário desiste de alterar o cadastro do
professor.
5a1. O usuário pressiona o botão “Cancelar”
5a2. A alteração é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
2a. Dados não cadastrados no sistema.
2a1. O sistema retorna a seguinte mensagem
“Professor não encontrado”.
2a2. Retorna ao passo 2 do fluxo principal.
4a. Dados inválidos na ficha de preenchimento.
4a1
O sistema retorna a seguinte mensagem
“Dados inválidos”.
4a2
Tabela 5
Retorna ao passo 2 do fluxo principal.
UC04 - Alterar Professor. Fonte: O autor (2010)
Caso de Uso:
UC05 – Excluir Professor
Sumario:
Este caso de uso inicia-se quando o usuário deseja excluir
o registro de um professor cadastrado no sistema.
Atores:
Administrador
48
Pré-condições:
UC01 e haver ao menos um professor previamente
cadastrado.
Fluxo Principal:
1.
UC02.
2.
O sistema lista os professores relacionados aos
parâmetros
de
busca
informados,
o
usuário
seleciona o professor desejado e pressiona o botão
“Excluir”.
3.
O sistema solicita a confirmação para a gravação.
4.
O usuário confirma a gravação.
5.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
4a. O
usuário
desiste
de
excluir
o
professor
cadastrado.
4a1. O usuário pressiona o botão “Cancelar”.
4a2. A exclusão é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
2a. Dados não cadastrados no sistema.
2a1. O sistema retorna a seguinte mensagem
“Professor não encontrado”.
2a2. Retorna ao passo 2 do fluxo principal.
Tabela 6
UC05 - Excluir Professor. Fonte: O autor (2010)
Caso de Uso:
UC06 – Buscar Turma
Sumario:
Este caso de uso inicia-se quando o usuário deseja buscar
uma turma no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita a busca por uma turma.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para localizar uma turma cadastrada.
3.
O usuário informa os dados referentes à busca por
uma turma e pressiona o botão “Procurar”.
4.
O sistema retorna os registros referentes aos
dados informados pelo usuário.
49
Fluxos Alternativos:
Fluxos de Exceção:
Tabela 7
UC06 - Buscar Turma. Fonte: O autor (2010)
Caso de Uso:
UC07 – Incluir Turma
Sumario:
Este caso de uso inicia-se quando o usuário deseja
registrar uma nova turma no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita o cadastramento de uma turma.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para fazer o cadastro completo da
turma.
3.
O usuário informa os dados referentes à inclusão
da turma, confere os dados digitados e submete a
gravação do cadastro.
4.
UC06.
5.
O sistema solicita a confirmação para a gravação.
6.
O usuário confirma a gravação.
7.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
5a. O usuário desiste de cadastrar a turma.
5a1. O usuário pressiona o botão “Cancelar”
5a2. O cadastramento é cancelado e o caso de
uso é encerrado.
Fluxos de Exceção:
4a. Dados inválidos na ficha de preenchimento.
4a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
4a2. Retorna ao passo 2 do fluxo principal.
Tabela 8
UC07 - Incluir Turma. Fonte: O autor (2010)
Caso de Uso:
UC08 – Alterar Turma
Sumario:
Este caso de uso inicia-se quando o usuário deseja alterar
o registro de uma turma cadastrada no sistema.
50
Atores:
Administrador
Pré-condições:
UC01 e haver ao menos uma turma previamente
cadastrada.
Fluxo Principal:
1.
UC06.
2.
O sistema lista as turmas relacionadas aos
parâmetros
de
busca
informados,
o
usuário
seleciona a turma desejada e pressiona o botão
“Alterar”.
3.
O usuário informa os dados referentes à alteração
dos dados da turma, confere os dados digitados e
submete a alteração dos dados do cadastro.
4.
O sistema solicita a confirmação para a gravação.
5.
O usuário confirma a gravação.
6.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
3a. O usuário desiste de alterar o cadastro da turma.
3a1. O usuário pressiona o botão “Cancelar”
3a2. A alteração é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
1a. Dados não cadastrados no sistema.
1a1. O sistema retorna a seguinte mensagem
“Turma não encontrada”.
1a2. Retorna ao passo 2 do fluxo principal.
2a. Dados inválidos na ficha de preenchimento.
2a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
2a2. Retorna ao passo 2 do fluxo principal.
Tabela 9
UC08 - Alterar Professor. Fonte: O autor (2010)
Caso de Uso:
UC09 – Excluir Turma
Sumario:
Este caso de uso inicia-se quando o usuário deseja excluir
o registro de uma turma cadastrada no sistema.
Atores:
Administrador
Pré-condições:
UC01 e haver ao menos uma turma previamente
51
cadastrada.
Fluxo Principal:
1.
UC06.
2.
O sistema lista as turmas relacionadas aos
parâmetros
de
busca
informados,
o
usuário
seleciona a turma desejada e pressiona o botão
“Excluir”.
3.
O sistema solicita a confirmação para a gravação.
4.
O usuário confirma a gravação.
5.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
4a. O usuário desiste de excluir a turma cadastrada.
4a1. O usuário pressiona o botão “Cancelar”.
4a2. A exclusão é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
2a. Dados não cadastrados no sistema.
2a1. O sistema retorna a seguinte mensagem
“Turma não encontrada”.
2a2. Retorna ao passo 2 do fluxo principal.
Tabela 10
UC09 - Excluir Turma. Fonte: O autor (2010).
Caso de Uso:
UC10 – Buscar Disciplina
Sumario:
Este caso de uso inicia-se quando o usuário deseja buscar
por uma disciplina cadastrada no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita a busca por uma disciplina.
2.
O sistema solicita os campos disponíveis a serem
preenchidos
para
localizar
uma
disciplina
cadastrada.
3.
O usuário informa os dados referentes à busca por
uma disciplina e pressiona o botão “Procurar”.
4.
O sistema retorna os registros referentes aos
dados informados pelo usuário.
Fluxos Alternativos:
52
Fluxos de Exceção:
Tabela 11
UC10 - Buscar Disciplina. Fonte: O autor (2010)
Caso de Uso:
UC11 – Incluir Disciplina
Sumario:
Este caso de uso inicia-se quando o usuário deseja
registrar uma nova disciplina no sistema.
Atores:
Administrador
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita o cadastramento de uma
disciplina.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para fazer o cadastro completo da
disciplina.
3.
O usuário informa os dados referentes à inclusão
da disciplina, confere os dados digitados e submete
a gravação do cadastro.
4.
UC10.
5.
O sistema solicita a confirmação para a gravação.
6.
O usuário confirma a gravação.
7.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
6a. O usuário desiste de cadastrar a disciplina.
6a1. O usuário pressiona o botão “Cancelar”
6a2. O cadastramento é cancelado e o caso de
uso é encerrado.
Fluxos de Exceção:
5a. Dados inválidos na ficha de preenchimento.
5a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
5a2. Retorna ao passo 2 do fluxo principal.
Tabela 12
UC11 - Incluir Disciplina. Fonte: O autor (2010)
Caso de Uso:
UC12 – Alterar Disciplina
Sumario:
Este caso de uso inicia-se quando o usuário deseja alterar
o registro de uma disciplina cadastrada no sistema.
53
Atores:
Administrador
Pré-condições:
UC01 e haver ao menos uma disciplina previamente
cadastrada.
Fluxo Principal:
1.
UC10.
2.
O sistema lista as disciplinas relacionadas aos
parâmetros
de
busca
informados,
o
usuário
seleciona a disciplina desejada e pressiona o botão
“Alterar”.
3.
O usuário informa os dados referentes à alteração
dos dados da disciplina, confere os dados digitados
e submete a alteração dos dados do cadastro.
4.
O sistema solicita a confirmação para a gravação.
5.
O usuário confirma a gravação.
6.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
7a. O usuário desiste de alterar o cadastro da
disciplina.
7a1. O usuário pressiona o botão “Cancelar”
7a2. A alteração é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
1a. Dados não cadastrados no sistema.
1a1. O sistema retorna a seguinte mensagem
“Disciplina não encontrada”.
1a2. Retorna ao passo 2 do fluxo principal.
3a. Dados inválidos na ficha de preenchimento.
3a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
3a2. Retorna ao passo 2 do fluxo principal.
Tabela 13
UC12 - Alterar Disciplina. Fonte: O autor (2010)
Caso de Uso:
UC13 – Excluir Disciplina
Sumario:
Este caso de uso inicia-se quando o usuário deseja excluir
o registro de uma disciplina cadastrada no sistema.
Atores:
Administrador
54
Pré-condições:
UC01 e haver ao menos uma disciplina previamente
cadastrada.
Fluxo Principal:
1.
UC10.
2.
O sistema lista as disciplinas relacionadas aos
parâmetros
de
busca
informados,
o
usuário
seleciona a disciplina desejada e pressiona o botão
“Excluir”.
3.
O sistema solicita a confirmação para a gravação.
4.
O usuário confirma a gravação.
5.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
4a. O
usuário
desiste
de
excluir
a
disciplina
cadastrada.
4a1. O usuário pressiona o botão “Cancelar”.
4a2. A exclusão é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
2a. Dados não cadastrados no sistema.
2a1. O sistema retorna a seguinte mensagem
“Disciplina não encontrada”.
2a2. Retorna ao passo 2 do fluxo principal.
Tabela 14
UC13 - Excluir Disciplina. Fonte: O autor (2010)
Caso de Uso:
UC14 – Incluir Horário Disponível
Sumario:
Este caso de uso inicia-se quando o usuário deseja
registrar um novo horário disponível para ministrar aulas.
Atores:
Administrador e Professor
Pré-condições:
UC01.
Fluxo Principal:
1.
O usuário solicita o cadastramento de um horário
disponível.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para fazer o cadastro completo do
horário.
3.
O usuário informa os dados referentes à inclusão
do horário, confere os dados digitados e submete a
55
gravação do cadastro.
4.
O sistema solicita a confirmação para a gravação.
5.
O usuário confirma a gravação.
6.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
5a. O usuário desiste de cadastrar o horário.
5a1. O usuário pressiona o botão “Cancelar”.
5a2. O cadastramento é cancelado e o caso de
uso é encerrado.
Fluxos de Exceção:
4a. Dados inválidos na ficha de preenchimento.
4a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
4a2. Retorna ao passo 2 do fluxo principal.
Tabela 15
UC14 - Incluir Horário Disponível. Fonte: O autor (2010)
Caso de Uso:
UC15 – Alterar Horário Disponível
Sumario:
Este caso de uso inicia-se quando o usuário deseja alterar
o registro de um horário disponível cadastrado no sistema.
Atores:
Administrador e Professor
Pré-condições:
UC01 e haver ao menos um horário previamente
cadastrado.
Fluxo Principal:
1.
O usuário solicita a busca por um horário.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para localizar um horário.
3.
O usuário informa os dados referentes à busca por
um horário e pressiona o botão “Procurar”.
4.
O sistema lista os horários relacionados aos
parâmetros
de
busca
informados,
o
usuário
seleciona o horário desejado e pressiona o botão
“Alterar”.
5.
O usuário informa os dados referentes à alteração
dos dados do horário, confere os dados digitados e
submete a alteração dos dados do cadastro.
6.
O sistema solicita a confirmação para a gravação.
56
7.
O usuário confirma a gravação.
8.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
7a. O usuário desiste de alterar o cadastro do horário.
7a1. O usuário pressiona o botão “Cancelar”.
7a2. A alteração é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
4a. Dados não cadastrados no sistema.
4a1. O sistema retorna a seguinte mensagem
“Horário não encontrado”.
4a2. Retorna ao passo 2 do fluxo principal.
6a. Dados inválidos na ficha de preenchimento.
6a1. O sistema retorna a seguinte mensagem
“Dados inválidos”.
6a2. Retorna ao passo 2 do fluxo principal.
Tabela 16
UC15 - Alterar Horário Disponível. Fonte: O autor (2010)
Caso de Uso:
UC16 – Excluir Horário Disponível
Sumario:
Este caso de uso inicia-se quando o usuário deseja excluir
o registro de um horário disponível cadastrado no sistema.
Atores:
Administrador
Pré-condições:
UC01 e haver ao menos um horário previamente
cadastrado.
Fluxo Principal:
1.
O usuário solicita a busca por um horário.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para localizar um horário.
3.
O sistema lista os horários relacionadas aos
parâmetros
de
busca
informados,
o
usuário
seleciona o horário desejado e pressiona o botão
“Excluir”.
4.
O sistema solicita a confirmação para a gravação.
5.
O usuário confirma a gravação.
6.
O sistema efetua a gravação e o caso de uso
termina.
57
Fluxos Alternativos:
5a. O usuário desiste de excluir o horário cadastrado.
5a1. O usuário pressiona o botão “Cancelar”.
5a2. A exclusão é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
3a. Dados não cadastrados no sistema.
3a1. O sistema retorna a seguinte mensagem
“Horário não encontrado”.
3a2. Retorna ao passo 2 do fluxo principal.
Tabela 17
UC16 - Excluir Horário Disponível. Fonte: O autor (2010)
Caso de Uso:
UC17 – Gerar Grade Horária
Sumario:
Este caso de uso inicia-se quando o usuário deseja gerar
uma grade horária.
Atores:
Administrador
Pré-condições:
UC01 e haver os dados de professor, disciplinas e turmas
previamente cadastrados no sistema.
Fluxo Principal:
1.
O usuário solicita a geração de uma grade horária.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para gerar a grade horária.
3.
O sistema solicita a confirmação para a gravação.
4.
O usuário confirma a gravação.
5.
O sistema efetua a gravação e o caso de uso
termina.
Fluxos Alternativos:
4a. O usuário desiste de excluir o horário cadastrado.
4a1. O usuário pressiona o botão “Cancelar”.
4a2. A exclusão é cancelada e o caso de uso é
encerrado.
Fluxos de Exceção:
3a. Dados não cadastrados no sistema.
3a1. O sistema retorna a seguinte mensagem
“Não há dados suficientes para a geração da
grade horária”.
3a2. Retorna ao passo 2 do fluxo principal.
Tabela 18
UC17 – Gerar Grade Horária. Fonte: O autor (2010)
58
Caso de Uso:
UC18 – Visualizar Grade Horária
Sumario:
Este caso de uso inicia-se quando o usuário deseja
visualizar uma grade horária.
Atores:
Administrador e Professor
Pré-condições:
Haver grade horária previamente cadastrada no sistema.
Fluxo Principal:
1.
O usuário solicita a visualização de uma grade
horária.
2.
O sistema solicita os campos disponíveis a serem
preenchidos para a visualização da grade horária.
3.
O sistema exibe a grade horária para o usuário e o
caso de uso termina.
Fluxos Alternativos:
Fluxos de Exceção:
3a. Dados não cadastrados no sistema.
3a1. O sistema retorna a seguinte mensagem
“Grade horária não encontrada”.
3a2. Retorna ao passo 2 do fluxo principal.
Tabela 19
UC18 – Visualizar Grade Horária. Fonte: O autor (2010)
59
APÊNDICE B – DESCRIÇÃO DAS TABELAS
Nome da Tabela
Descrição
Coluna
PROFESSOR_ID
PROFESSOR_NOME
ATIVO_ID
CARGA_HORARIA
Tabela 20
Descrição da tabela PROFESSOR. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
ROLE_ID
ROLE_DESCRICAO
Tabela 21
ROLE_PROFESSOR
Estrutura que armazena as roles de um professor
Descrição
Tipo de dado
Nulo
ID da role
Varchar2(20)
N
ID do professor
Varchar2(20)
N
Consistência
PK, FK (ROLE)
PK, FK (PROFESSOR)
Descrição da tabela ATIVO. Fonte: O autor (2010)
DISCIPLINA
Estrutura que armazena as informações sobre cada disciplina
Descrição
Tipo de dado
Nulo
Consistência
ID da disciplina
Varchar2(20)
N
PK
Nome
da Varchar2(100)
N
disciplina
Descrição da tabela DISCIPLINA. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
CURSO_ID
CURSO_DESCRICAO
Tabela 25
PK
ATIVO
Estrutura que armazena os professores ativos e não ativos
Descrição
Tipo de dado
Nulo
Consistência
ID da tabela Ativo
Number(1)
N
PK
Descrição da tabela Varchar2(100)
N
Ativo
Nome da Tabela
Descrição
Coluna
DISCIPLINA_ID
DISCIPLINA_DESCRICAO
Tabela 24
Consistência
Descrição da tabela ROLE_PROFESSOR. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
ATIVO_ID
ATIVO_DESCRICAO
Tabela 23
ROLE
Estrutura que armazena o perfil de acesso
Descrição
Tipo de dado
Nulo
ID da role
Varchar2(20)
N
Descrição da role
Varchar2(100)
N
Descrição da tabela ROLE. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
ROLE_ID
PROFESSOR_iD
Tabela 22
PROFESSOR
Estrutura que armazena as informações sobre cada professor.
Descrição
Tipo de dado
Nulo
Consistência
ID do professor
Varchar2(20)
N
PK
Nome do professor
Varchar2(100)
N
Professor ativo no Number(1)
N
FK (ATIVO)
sistema.
Carga
horária Number
N
disponível
do
professor
CURSO
Estrutura que armazena as informações sobre cada curso
Descrição
Tipo de dado
Nulo
Consistência
ID do curso
Varchar2(20)
N
PK
Nome do curso
Varchar2(100)
N
Descrição da tabela CURSO. Fonte: O autor (2010)
60
Nome da Tabela
Descrição
Coluna
DISCIPLINA_ID
CURSO_ID
SEMESTRE_ID
QUANTIDADE_AULAS
Tabela 26
Descrição da tabela DISCIPLINA_CURSO. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
DISCIPLINA_ID
CURSO_ID
PROFESSOR_ID
Tabela 27
PROFESSOR_DISCIPLINA_CURSO
Estrutura que armazena o curso e as disciplinas de cada professor
Descrição
Tipo de dado
Nulo
Consistência
ID da disciplina
Varchar2(20)
N
PK, FK (DISCIPLINA)
ID do curso
Varchar2(20)
N
PK, FK (CURSO)
ID do professor
Varchar2(20)
N
PK, FK (PROFESSOR)
Descrição da tabela PROFESSOR_DISCIPLINA_CURSO. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
TURMA_ID
TURMA_DESCRICAO
SEMESTRE_ID
PERIODO_ID
CURSO_ID
Tabela 28
DISCIPLINA_CURSO
Estrutura que armazena as disciplinas de cada curso
Descrição
Tipo de dado
Nulo
Consistência
ID da disciplina
Varchar2(20)
N
PK, FK (DISCIPLINA)
ID do curso
Varchar2(20)
N
PK, FK (CURSO)
ID do semestre
Number
N
FK (SEMESTRE)
Quantidade
de Number
N
aulas ministradas
da disciplina no
curso.
TURMA
Estrutura que armazena as informações sobre cada turma
Descrição
Tipo de dado
Nulo
Consistência
ID da turma
Varchar2(20)
N
PK
Nome da turma
Varchar2(100)
N
ID do semestre
Number
N
FK (SEMESTRE)
ID do período
Character(1)
N
FK (PERIODO)
ID do curso
Varchar2(20)
N
FK (CURSO)
Descrição da tabela TURMA. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
SEMESTRE_ID
SEMESTRE_DESCRICAO
Tabela 29
Descrição da tabela SEMESTRE. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
HORARIO_ID
HORARIO_INICIO
HORARIO_FIM
PERIODO_ID
Tabela 30
SEMESTRE
Estrutura que armazena as informações sobre os semestres
Descrição
Tipo de dado
Nulo
Consistência
ID do semestre
Number
N
PK
Descrição
do Varchar2(100)
N
semestre
HORARIO
Estrutura que armazena as informações sobre cada horário
Descrição
Tipo de dado
Nulo
Consistência
ID do horário
Number
N
PK
Hora de inicio da Varchar2(5)
N
aula
Hora de termino da Varchar2(5)
N
aula
ID do período
Character(1)
N
FK (PERIODO)
Descrição da tabela HORARIO. Fonte: O autor (2010)
61
Nome da Tabela
Descrição
Coluna
PERIODO_ID
PERIODO_DESCRICAO
Tabela 31
PERIODO
Estrutura que armazena as informações sobre cada período
Descrição
Tipo de dado
Nulo
Consistência
ID do período
Character(1)
N
PK
Descrição
do Varchar2(100)
N
período
Descrição da tabela PERIODO. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
DIA_SEMANA_ID
DIA_SEMANA_DESCRICAO
Tabela 32
Descrição da tabela DIA_SEMANA. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
DIA_SEMANA_ID
HORARIO_ID
Tabela 33
DISPONIBILIDADE
Estrutura que armazena os horários disponíveis de cada professor
Descrição
Tipo de dado
Nulo
Consistência
ID do dia da semana Number(1)
N
PK, FK (DIA_SEMANA)
ID do horário
Number
N
PK, FK (HORARIO)
ID do professor
Varchar2(20)
N
PK, FK (PROFESSOR)
Descrição da tabela DISPONIBILIDADE. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
DISCIPLINA_ID
CURSO_ID
PROFESSOR_ID
DIA_SEMANA_ID
HORARIO_ID
Tabela 35
DIA_SEMANA_HORARIO
Estrutura que armazena os horários de cada dia da semana
Descrição
Tipo de dado
Nulo
Consistência
ID do dia da semana Number(1)
N
PK, FK (DIA_SEMANA)
ID do horário
Number
N
PK, FK (HORARIO)
Descrição da tabela DIA_SEMANA_HORARIO. Fonte: O autor (2010)
Nome da Tabela
Descrição
Coluna
DIA_SEMANA_ID
HORARIO_ID
PROFESSOR_ID
Tabela 34
DIA_SEMANA
Estrutura que armazena as informações sobre cada dia da semana
Descrição
Tipo de dado
Nulo
Consistência
ID do dia da Number(1)
N
PK
semana
Descrição do dia Varchar2(100)
N
da semana
GRADE_HORARIA
Estrutura que armazena os professores e disciplinas, nos dias da semana e
horários disponíveis.
Descrição
Tipo de dado
Nulo
Consistência
ID da disciplina
Varchar2(20)
N
PK, FK (DISCIPLINA)
ID do curso
Varchar2(20)
N
PK, FK (CURSO)
ID do professor
Varchar2(20)
N
PK, FK (PROFESSOR)
ID do dia da semana Number(1)
N
PK, FK (DIA_SEMANA)
ID do horário
Number
N
PK, FK (HORARIO)
Descrição da tabela GRADE_HORARIA. Fonte: O autor (2010)
62
REFERÊNCIAS BIBLIOGRÁFICAS
APPLEGATE, David L. The travelling salesman problem: a computational Study.
Princeton University Press, 2006.
BOOCH, Grady; JACOBSON, Ivar; RUMBAUGH, Jim. Object Management Group:
Unified Modeling Language. Disponível em: <http://www.uml.org/> Acesso em: 28
maio 2010.
CHEN, Peter Pin-Shan. The Entity-Relationship Model--Toward a Unified View of
Data. Massachussets Institute of Technology, 1976.
COAD, Peter; YOURDON, Edward. Object-Oriented Design. Prentice Hall, 1991.
COLORNI, Alberto; DORIGO, Marco; MANIEZZO, Vittorio. A Genetic Algorithm to
solve the Timetable Problem. Dipartimento di Elettronica e Informazione Politecnico
di Milano, 1992.
DARWIN, Charles. A Origem das Espécies. London, 1859.
ESPERIDIÃO, Márcia; SANTOS, Cerqueira Lucas Alberto Souza. Algoritmos
Genéticos - Aspectos Matemáticos. Universidade Federal da Bahia, 2003.
EVEN, S.; ITAI, A.; SHAMIR, A. On the complexity of timetabling and multicommodity
flow problems. SIAM Journal of Computation, v. 5, pp. 691-703, 1976.
FOWLER, Martin. Patterns of Enterprise Application Architecture. Addison-Wesley
Professional, 2002.
FRANGOULI, Harikleia; HARMANDAS, Vassilis; STAMATOPOULOS, Panagiotis.
UTSE: Construction of Optimum Timetable for University Courses – A CLP
Approach. University of Athens, 1995.
63
FUCILINI, Tiago P.; MARUANI, Eli; REBONATTO, Marcelo Trindade. Timetabling
com algoritmos genéticos: resultados, restrições e exploração do paralelismo.
Universidade de Passo Fundo, 2008.
GAREY, Michael R.; JOHNSON, David S. Computers and Intractability: A Guide to
the Theory of NP-Completeness. EUA: W. H. Freeman, 1979.
GARRET, Jesse James. Ajax: A New Approach to Web Applications. Disponível em:
<http://www.adaptivepath.com/ideas/essays/archives/000385.php> Acesso em: 28
maio 2010.
GOLDBERG, David E. Genetic Algorithms in Search, Optimization, and Machine
Learning. EUA: Addison-Wesley Longman Publishing, 1989.
GOMES, Luiz Carlos Filho. Alocação de Professores em Horários do Plantão de
Dúvidas para o Curso e Colégio Objetivo: Uma Abordagem Heurística. Universidade
de São Paulo, 2006.
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.
Universidade Federal de Uberlândia, 2005.
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introduction to Operations Research.
McGraw-Hill, 1990.
HORITA, Vanderlei Minori. Sistemas dinâmicos não lineares. Universidade Estadual
Paulista, 2002.
IBARAKI, Toshihide; KATOH, Naoki. Resource Allocation Problems: Algorithmic
Approaches (Foundations of Computing). The MIT Press, 1988.
JACOBSON, Ivar. Use Cases: Yesterday, Today, and Tomorrow. Disponível em:
http://www-128.ibm.com/developerworks/rational/library/775.html
outubro 2010.
Acesso
em:
29
64
JACOB, Antonio Fernando Lavareda Junior; ROCHA, Cláudio Alex Jorge. AGHORA:
Algoritmos Genéticos para Geração de Horários de Aula. Universidade da
Amazônia, 2005.
KEMP, Roger L. Handbook of Strategic Planning. Nova Iorque: Cummings and
Hathaway Publishers, 1995.
LOPES, L. S. Uma Heurística Baseada em Algoritmos Genéticos Aplicada ao
Problema de Cobertura de Conjuntos. São José dos Campos, 1995.
MIRANDA, Marcio Nunes. Algoritmos Genéticos: Fundamentos e Aplicações.
Disponível em: <http://www.gta.ufrj.br/~marcio/genetic.html> Acesso em: 15 maio
2010.
NAUR, Peter; RANDELL, B. Software Engineering: Report on a Conference
sponsored by the NATO Science Committee. Germany: Scientific Affairs Division, pp.
231, 1968.
NIELSEN, Jakob. Usability Engineering. Boston: Academic Press, 1993. P. 26-37.
OBITKO, Marek; SLAVÍK, Pavel. Visualization of Genetic Algorithms in a Learning
Environment. Bratislava: Comenius University, 1999.
PEREIRA, Jean Fretta; NETO, Wilson Castello Branco. Uma Abordagem
Evolucionária para a Geração de Quadros de Horários. Rio Grande do Sul: Revista
do CCEI, 2001, v. 5, n. 8, P. 103-111.
SANTOS, Rogério Rodrigues dos; SARAMAGO, Sezimaria de Fátima Pereira;
STEFFEN, Valder Jr. Especificação de Trajetória de Robôs em Tempo Ótimo.
Universidade Federal de Uberlândia, 2004.
SOUZA, Vítor E. Silva. Java EE 6 na Prática. JAVA Magazine, Rio de Janeiro, v. 80,
p.20-34, 2010.
65
TEXEIRA, Maria A. Lima Pereira S. Um Problema de Alocação de Recursos.
Universidade do Porto, 1991.
WILSON, Bill. Recurrent Networks Architectures. University of New South Wales,
1991.