ads:
Fundação Edson Queiroz
Universidade de Fortaleza
CONSTRUÇÃO DE TABELA DE HORÁRIO
ESCOLAR NA WEB
José Auriço Oliveira
Dissertação submetida ao Corpo Docente do
Mestrado em Informática Aplicada da Universidade
de Fortaleza como parte dos requisitos
necessários para a obtenção do grau de Mestre
em Ciência da Computação.
Orientador: Prof. Plácido Rogério Pinheiro, D. Sc.
Aprovada por
:
Prof. Plácido Rogério Pinheiro, D. Sc.
(Presidente da Banca)
Prof. Dario José Aloise, D. Sc.
Prof. Antonio Clécio Fontelles Thomaz, D. Sc.
Fortaleza, Ce - Brasil
2002
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
OLIVEIRA, JOSÉ AURIÇO
Construção de Tabela de Horário Escolar
na WEB [Fortaleza] 2003
x, 84 p. 29,7 cm (MIA/UNIFOR, M. Sc.,
Engenharia do Conhecimento,2003)
Tese – Universidade de Fortaleza, MIA
1. Tabela de Horário
2. Programação Linear Inteira
3. Otimização na Internet
I. MIA/UNIFOR II. TÍTULO (série)
ads:
iii
Dedico este trabalho à memória do Professor José
Guilherme Pimenta Araújo, pelo exemplo de
perseverança e pelo incentivo ao aprender, a minha
querida esposa Alda, pela paciência, auxilio e
compreensão, aos meus filhos, Mariana e Guilherme
Neto, pelas horas que o estudo tirou de nossa
convivência, aos meus pais, Josias e Áurea, pela
formação e exemplo de vida baseada no trabalho
árduo.
iv
AGRADECIMENTOS
Ao Governo do Estado do Ceará, através das seguintes instituições: Extinto
SEPROCE
pela oportunidade ofertada e custeio parcial,
ETICE
por permitir a
continuidade do Curso,
SEPLAN
pela liberação dos horários para a conclusão dos
créditos,
FUNCAP
pela bolsa de estudo fornecida e
SEDUC
por ser a fonte
motivadora do problema e pelas informações disponibilizadas.
Ao meu orientador e mestre
Professor Plácido Rogério Pinheiro,
pelo exemplo e
constante incentivo na elaboração deste trabalho e dos artigos publicados.
A todos os colegas do curso do MIA, pela troca de experiência e lamentações.
Ao time da STI, pela força e companheirismo, e em especial
Ariana Falcão da
Silva
, superintendente, pelo incentivo dado para a conclusão deste trabalho.
Aos companheiros da ETICE
Carlos Jorge, Paulo Aguiar e Rômulo Frota
, pelo
apoio oferecido sempre que foi necessário.
Aos diretores de Escolas do Governo do Estado do Ceará, pela cooperação e boa
vontade.
Aos Professores Doutores
Dario José Aloise
e
Antonio Clécio Fontelles Thomaz
pela participação em minha banca examinadora.
Aos funcionários do MIA, pelo apoio e paciência oferecido.
v
Resumo da Dissertação apresentada ao Mestrado em Informática Aplicada (MIA) da
Universidade de Fortaleza (UNIFOR) como parte dos requisitos necessários para a
obtenção do grau de Mestre em Ciência da Computação (M. Sc.).
CONSTRUÇÃO DE TABELA DE HORÁRIO ESCOLAR NA WEB
José Auriço Oliveira
Março/2003
Orientador: Prof. Plácido Rogério Pinheiro, D. Sc.
Programa: Ciências da Computação.
O objetivo deste trabalho é apresentar um ambiente de apoio a construção de
tabela de horário escolar utilizando a WEB. Este ambiente caracteriza-se pela
configuração, geração e resolução de um modelo computacional estruturado em um
problema de programação linear inteira disponibilizado na WEB para as escolas de
ensino médio. A arquitetura implementada oferece flexibilidade na aplicação em
outros problemas no serviço público que possam ser solucionados através de
variadas técnicas de pesquisa operacional. Os resultados obtidos desta
implementação no Estado do Ceará permitirão otimizar o processo de construção
das tabelas de horários nas escolas estaduais.
vi
Abstract of Dissertation presented to MIA/UNIFOR as a partial fulfillment of the
requirements for the degree of Master of Science (M. Sc.)
CONSTRUCTION OF SCHOOL TIMETABLING IN THE WEB
José Auriço Oliveira
March / 2003
Advisor: Prof. Plácido Rogério Pinheiro, D. Sc.
Department : Computer Science.
The objective of this research is to present a support environment to the construction
of school timetabling using the WEB. This environment is characterized by the
configuration, generation and resolution of a computacional model structured in a
problem of interger linear programming in the WEB to the schools of medium
teaching. The implemented architecture offers flexibility to be used in other problems
in the public service that can be solved through varied techniques of operational
research. The results of this implementation in Ceará’s State will allow the the state’s
schools to optimize it’s construction of school timetabling.
vii
SUMÁRIO
Lista de Figuras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
Lista de Tabelas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1. Motivação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Objetivos do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Organização do Trabalho. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. O Problema da Construção de Tabela de Horário . . . . . . . . . . . . . . . . . . . . . .
4
2.1. Apresentação do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Modelagem do Problema de Horário Escolar . . . . . . . . . . . . . . . . . . . . 6
2.3. Técnicas e Abordagens de Solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4. Abordagens relacionadas com Programação Linear Inteira . . . . . . . . . . 13
2.5. Implementações do Problema de Horário Escolar . . . . . . . . . . . . . . . . . 15
2.6. Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3. Aplicações da Otimização na WEB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.1 Otimização na Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Solução de Arquitetura de Otimização na Internet . . . . . . . . . . . . . . . . . 21
3.3 Ambientes de Otimização na Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4. O Ambiente de Construção de Tabela de Horário Escolar na Internet . . . . . .
30
4.1 O Problema nas Escolas do Estado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1.1 Organização das Escolas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1.2 A Grade Curricular. . . . . . ............. . . . . . . . . . . . . . . . . . . . . . . . 32
viii
4.1.3 Forma de Contratação de Professores pelo Estado . . . . . . . . . 33
4.1.4 Construção da Tabela de Horário nas escolas . . . . . . . . . . . . . . 33
4.2 O Modelo em Programação Linear Inteira . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 A Arquitetura do Ambiente na INTERNET . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Descrição do Ambiente de Construção de Tabela de Horário Escolar . . . 44
4.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5. Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
57
5.1 Descrição do Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Modelo linear inteiro gerado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .. . . . 59
5.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 60
6. Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
6.1 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 63
Referencias Bibliográficas . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
64
Apêndice A: Dados dos professores com disciplinas lecionadas . . . . . . . . . . .
69
Apêndice B: Exemplo Da função objetivo do modelo gerado pelo
ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
Apêndice C : Resultado da resolução do modelo gerado através do
software lindo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
Apêndice D : Resultado da resolução do modelo gerado pelo ambiente. . . . . .
72
Apêndice E : Resultado da resolução do modelo gerado pelo ambiente. . . . . .
73
ix
LISTA DE FIGURAS
Figura 3.1:
Plataforma de um Provedor de Serviço de Aplicação (ASP)
[Geoffrion & Krishnan 2001] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Figura 3.2: Arquitetura multicamada para resolver problemas de otimização.
[Cohen et Al 2001] .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Figura 3.3: Arquitetura de dados na INTERNET para otimização.
[Cohen et Al 2001] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Figura 3.4. Arquitetura de simulação baseada na INTERNET. [Yen 97a] . . . . . . 23
Figura 3.5. Fluxo de uma ferramenta de simulação baseada na INTERNET.
[Yen 97a] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Figura 3.6. Estrutura do ambiente NEOS. [Czyzyk et all 97] . . . . . . . . . . . . . . . . . 27
Figura 4.1: Estrutura das Escolas de Ensino Médio do Estado.. . . . . . . . . . . . . . .31
Figura 4.2. Estrutura de um ambiente de Gestão Escolar integrado
com o ambiente de construção de tabela de horário.. . . . . . . . . . . . . . . .. .35
Figura 4.3. Arquitetura do Ambiente de otimização na INTERNET.. . . . . . . . . . . 40
Figura 4.4. Estrutura de Dados armazenada no Banco de Dados. . . . . . . . . . . . 45
Figura 4.5. Organização dos componentes do Ambiente na INTERNET.. . . . . . . 48
Figura 4.6 : Interface do módulo de controle de acesso.. . . . . . . . . . . . . . . . . . . . 49
Figura 4.7 : Interface do menu principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Figura 4.8 : Interface do módulo configurador do modelo.. . . . . . . . . . . . . . . . . . 51
x
Figura 4.9 : Interface do módulo Gerador do Modelo.. . . . . . . . . . . . . . . . . . . . . . 52
Figura 4.10 : Interface do módulo Editor do Modelo.. . . . . . . . . . . . . . . . . . . . . . . 53
Figura 4.11 : Interface do módulo de resolvedor do modelo. . . . . . . . . . . . . . . . . . 54
Figura 4.12 : Interface do módulo de Consultas e Relatórios. . . . . . . . . . . . . . . . . 55
Figura 5.2: Comportamento da matriz de solução gerada pelo LINDO.. . . . . . . . . 59
xi
LISTA DE TABELAS
Tabela 4.1: Intervalos de aulas por turno adotado no Estado. . . . . . . . . . . . . . . 34
Tabela 4.2: Exemplo de grade curricular para o 1
o
ANO. . . . . . . . . . . . . . . . . . . 35
Tabela 4.3: Dados dos professores necessários ao modelo matemático. . . . . . 38
Tabela 4.4: Dados das disciplinas/turmas necessários ao modelo matemático.. 39
1
Capítulo 1
INTRODUÇÃO
1.1. Motivação
O problema da construção de horário escolar se repete a cada ano em
todas as escolas estaduais de ensino médio, ocasionado pelas aposentadorias,
contratação de novos professores, aditivos de contratos, afastamentos e alteração
da demanda de alunos. Os diretores de escolas realizam este trabalho de forma
manual, e cada alteração realizada na lotação de algum professor, causa sérios
transtornos, além de prejuízos financeiros devido à ocorrência de professores cuja
carga horária não é utilizada na sua totalidade.
O presente trabalho focaliza o problema da alocação de professores de
determinadas disciplinas a horários nas Escolas de Ensino Médio do Governo do
Estado do Ceará. O problema consiste em determinar aulas para períodos nos quais
nenhum professor esteja envolvido em mais de uma aula ao mesmo tempo, e
satisfazendo por outro lado a um conjunto de restrições, que diz respeito dentre
outras a carga horária das disciplinas, quantidade de turmas e indisponibilidade de
horários dos professores. A solução manual para o problema usualmente requer em
geral vários dias de trabalho, em muitos casos sem obter um resultado satisfatório. A
diversidade de restrições determinada por imposições administrativas e técnicas
torna o problema de difícil generalização, transformando cada caso em particular. É
também considerado um problema NP-completo [Garey & Johnson 79].
2
Neste contexto serão analisados os modelos matemáticos apresentados
na literatura, para avaliar a sua aplicabilidade a realidade das Escolas de Ensino
Médio do Estado do Ceará, sendo detectado que para a solução contemplar a todos
os fatores restritivos no contexto do Ceará, seria necessário que cada escola
pudesse configurá-lo para sua realidade. Considerando a existência de um grande
número de escolas e as suas localizações, por razões econômicas, esta solução
deveria ser disponibilizada de forma centralizada através da WEB.
1.2. Objetivos do Trabalho
O objetivo principal deste trabalho é desenvolver um ambiente de apoio à
decisão na WEB utilizando técnicas de pesquisa operacional que permita aos
diretores de escolas a construção de horários escolares para as 421 Escolas de
Ensino Médio do Governo Estadual, abrangendo o interior e a capital do Estado.
Este trabalho se propõe a atingir os seguintes objetivos específicos:
• Definir um modelo utilizando Programação Linear Inteira que possa ser
aplicado à realidade das escolas de Ensino Médio do Governo Estadual do Ceará;
• Implementar um ambiente disponibilizado através da WEB para os
diretores de escolas que, de forma transparente, permita gerar o modelo e encontrar
uma solução viável em tempo hábil, utilizando softwares comerciais;
• Disponibilizar um ambiente de otimização na WEB, que possibilite a
resolução de problemas utilizando técnicas de pesquisa operacional com a
agregação de novos modelos e resolvedores.
A abordagem do trabalho com relação às escolas é feita de forma
individualizada, contudo com o acréscimo de algumas restrições a Secretaria de
3
Educação do Estado - SEDUC, pode com facilidade adaptá-lo para ser gerado de
forma regionalizada ou para todo o Estado.
1.3. Organização do Trabalho
Este trabalho está organizado em seis capítulos, conforme descritos
resumidamente a seguir:
Neste capítulo é feita uma apresentação da motivação para o tema, os
objetivos pretendidos e as contribuições esperadas com a elaboração do trabalho.
O capitulo 2 apresenta os principais trabalhos pesquisados sobre o tema
objeto do estudo, destacando-se as várias modelagens do problema, técnicas e
abordagens de solução e as implementações já realizadas.
Alguns trabalhos, abrangendo a WEB e a utilização de técnicas de
pesquisa Operacional, são destacados no capítulo 3, os quais apresentam uma
proposta de arquitetura para os ambiente de otimização na WEB.
O capítulo 4 apresenta o Ambiente de Construção de tabela de Horário
Escolar na WEB, detalhando algumas características das escolas estaduais, o
modelo matemático utilizado e a descrição dos componentes do ambiente.
No capitulo 5 será apresentado os testes e resultados realizados no
ambiente. Por fim, as conclusões e as sugestões para trabalhos futuros são
apresentadas no capítulo 6.
4
Capítulo 2
O PROBLEMA DA CONSTRUÇÃO DE TABELA DE
HORÁRIO
2.1. Apresentação do Problema
Um problema de construção de tabela de horário é caracterizado pela
atribuição de um evento a um determinado assunto, em um intervalo de tempo
envolvendo várias restrições. Dentre os problemas que possuem estas
características destacamos:
• Elaboração de tabelas de jogos para campeonatos e torneios;
• Escala de tripulação de linhas aéreas;
• Construção de horário escolar;
• Escala de empregados em hospitais, companhias de eletricidade,
companhias telefônicas, companhias de água e esgoto;
• Escala de auditores em fiscalizações;
• Escala de policiais militares e civis.
Os problemas de construção de tabela de horário são particularmente
desafiadores para os pesquisadores, devido à característica combinatória e a difícil
generalização em virtude da quantidade de variantes que o problema pode assumir.
A construção de tabela de horário
para instituições educacionais é um
problema clássico. Horários são uma necessidade de toda instituição de ensino,
incluindo escolas de ensino fundamental, ensino médio e universidades. São vários
5
os problemas encontrados na elaboração de tabela de horário, tais como alocação
das aulas para os professores, alocação de salas, laboratórios e equipamentos.
Além disso, é necessário considerar as combinações de algumas destas restrições.
Neste contexto, as aulas de uma instituição são o conjunto de reuniões
entre professores e alunos num conjunto de períodos de tempo. Nestes períodos de
tempo, os recursos disponíveis são limitados, por exemplo, a indisponibilidade do
professor em determinado horário, e várias outras restrições podem ser adicionadas.
Portanto, o problema de construção de grades horárias pode ser visto como relações
entre conjuntos de professores, disciplinas, alunos, períodos de tempo e recursos.
Estas relações estão sujeitas ainda a uma série de restrições, cujas combinações
aumentam a complexidade do problema.
Durante os últimos quarenta anos muitos artigos relacionados ao problema
de tabela de horário vêm sendo apresentados, os quais são destacados na vasta
bibliografia dos trabalhos de [Schmidt & Strohlein 80] e nos surveys de [Junginger
86]; [de Werra 85]; [Carter 86]; [Fang 94] e [Schaerf 95]. Em adição, várias
aplicações vêm sendo desenvolvidas e empregadas com sucesso.
Segundo [Schaerf 95], existem diversas subclasses do Problema de
Geração de Tabela de Horário, diferentes entre si pela instituição envolvida – ensino
superior, médio ou fundamental – e pelas características de cada uma (definidas
pelas restrições e critérios de satisfação de seus modelos). Entretanto, elas podem
ser agrupadas em três classes principais:
6
a) Problema para escolas: a alocação semanal de todas as turmas de
uma escola, evitando o encontro de disciplinas ministradas por um
mesmo professor no mesmo período letivo.
b) Problema para cursos universitários: a alocação semanal de todas as
cadeiras de um conjunto de cursos universitários, visando minimizar a
sobreposição de cadeiras com alunos em comum.
c) Problema para exames universitários: a alocação dos exames de um
conjunto de cursos universitários, evitando a sobreposição de exames
com alunos em comum e maximizando o intervalo de tempo entre
exames de um mesmo estudante.
Neste trabalho, será apresentada uma abordagem para o problema do
horário escolar nas escolas de ensino médio do Governo do Estado do Ceará,
destacando a construção de um ambiente de otimização para o problema
disponibilizado através da WEB.
2.2. Modelagem do Problema de Horário Escolar
Nesta seção, apresentaremos alguns trabalhos de modelos matemáticos
descritos na literatura. Em alguns casos, o problema de horário consiste em procurar
alguma combinação que satisfaça todas as restrições. Nestes casos o problema é
formulado como um problema de pesquisa. Nos casos que é requerido um horário
que satisfaça todas as restrições e minimize ou maximize uma função objetivo, o
problema é formulado como um problema de otimização [Schaerf 95].
Inicialmente, consideremos a seguinte formulação:
7
m turmas c
1
,... , c
m
;
n professores t
1
, ... , t
n
;
p períodos 1, ... ,p.
Temos também uma matriz não negativa inteira R
mxn
, chamada matriz
requerimento, onde r
ij
é o número de aulas dadas por um professor t
j
para uma
turma c
i
.
O problema consiste em determinar aulas para períodos de modo que
nenhum professor ou turma seja envolvido em mais de uma aula ao mesmo tempo.
A formulação matemática é a seguinte [de Werra 85]:
Assim sendo, a restrição (1), assegura que cada professor lecione o
número certo de aulas para cada classe. As restrições (2) e (3) asseguram que cada
professor ou turma não esteja envolvido em mais de uma aula para cada período.
A resolução de P1, pode ser realizada através de um bipartite
multigraph, conforme [Even et al 76] ou o problema pode ser reduzido a um edge
P1 otimizar x
ijk
(i=1, ... ,m; j=1, ... ,n; k=1, ... ,p)
p
s.t.
∑
∑∑
∑
x
ijk
= r
ij
(i=1, ... ,m; j=1, ... ,n;) (1)
k=1
n
∑
∑∑
∑
x
ijk
≤
≤≤
≤ 1
(i=1, ... ,m; k=1, ... ,p;) (2)
j=1
m
∑
∑∑
∑
x
ijk
≤
≤≤
≤ 1 (j=1, ... ,n; k=1, ... ,p;) (3)
i=1
x
ijk
= {0, 1}
(i=1, ... ,m; j=1, ... ,n; k=1, ... ,p) (4)
onde x
ijk
= 1 se a turma c
i
e o professor t
j
se encontra num período
p, e x
ijk
= 0 caso contrário.
8
coloring on graphs como em [de Werra 85]. Para pequenas aplicações de
problemas de horários, foram apresentados algoritmos exatos utilizando graph-
colouring em [Korman 79].
O problema
P1
não inclui nenhuma restrição sobre a possibilidade que
uma turma ou professor esteja indisponível em um determinado tempo. A seguinte
formulação é atribuída a [Junginger 86]. Junginger introduz duas matrizes binárias
T
mxp
e C
nxp
tal que t
ik
= 1 (c
ik
= 1) se professor t
i (turma ci)
está disponível no
período k, e t
jk
= 0 (c
ik
= 0) caso contrário
,
depois disso, substitui as restrições (2) e
(3) em P1 pelas restrições (7) e (8) [Schaerf 95], como a seguir:
Os modelos apresentados anteriormente são problemas cuja solução é
qualquer tabela de horário possível. Contudo, em várias aplicações uma solução de
tabela de horário pode produzir um custo menor do que outra. Esta consideração
motiva à formulação do problema de tabela de horário como um problema de
otimização com uma função objetivo para ser minimizada ou maximizada.
Junginger propõem adicionar ao P1 a seguinte função objetivo [Schaerf
95]:
n
∑
∑∑
∑
x
ijk
≤
≤≤
≤ t
ik
(i=1, ... ,m; k=1, ... ,p;) (7)
j=1
m
∑
∑∑
∑
x
ijk
≤
≤≤
≤ c
jk
(j=1, ... ,n; k=1, ... ,p;) (8)
i=1
9
[Colorni,Dorigo e Maniezzo 92] inseriu uma função objetivo, incluindo
aspectos de tabela de horários baseado nos valores: custo didático, custo
organizacional e custo de pessoal.
[Souza, Maculan e Ochi 2000] apresentaram uma função objetivo
estruturada em penalidade, a qual deve ser minimizada:
f(Q) = ω * f
1
(Q) + δ * f
2
(Q) + ρ * f
3
(Q)
em que as duas primeiras componentes mensuram o nível de inviabilidade caso
exista turma tendo aula com mais de um professor ou caso exista turma sem aula,
respectivamente, e a terceira, o nível de satisfação dos professores com relação ao
atendimento de seus requisitos pessoais.
Outras variantes do problema básico são propostas na literatura. As mais
populares são: Aulas simultâneas apresentadas em [Yoshikawa et al 94];
Professores para mais de uma disciplina apresentada em
[Cooper e
Kingston 93].
Aulas com tempo de duração variável e intervalo para lanches são outras variantes
apresentadas em [Drexl & Salewski 97].
m n p
min
∑
∑∑
∑
∑
∑∑
∑
∑
∑∑
∑
d
ijk
x
ijk
(9)
i=1 j=1 k=1
onde um grande d
ijk
é designado para período k no qual uma aula de
professor t
j
para classe c
i
é menos desejável.
10
2.3. Técnicas e Abordagens de Solução
Nesta seção, apresentaremos as técnicas e abordagens de solução
propostas na literatura para o problema de construção de tabela de horário.
2.3.1 Heurísticas Diretas
: São baseadas em uma simulação do modo manual de
resolver o problema. Um típico exemplo deste método é o sistema SCHOLA , o qual
é descrito também em [Junginger 86]
.
Muitos dos trabalhos recentes propõem
alguma heurística direta para a solução do problema de horário. Em [Schmidt &
Strolein 79] é apresentado uma lista destes algoritmos. Outro trabalho mais recentes
utilizando heurísticas diretas pode ser analisado em [ Souza, Maculan e Ochi 2000].
2.3.2 Redução a
graph coloring: [Neufeld e Tartar 74] propõem uma redução para
o problema de grapf coloring. [De Werra 85] resume grande parte da teoria dos
grafos, apresentando um tutorial de introdução em formulações de problemas
simples de tabela de horários. [Carter 86] faz uma revisão de grapf coloring que
pode ser aplicado a problemas práticos de tabela de horário.
2.3.3 Técnicas de fluxo em rede:
[Osterman e de Werra 93] reduz o problema de
horário a uma seqüência de problemas de fluxo em rede. Foi criada uma rede para
cada período de forma que cada fluxo na rede identifique uma aula dentro de um
período. Em [de Werra 85] existe uma proposta de um método similar criando uma
rede para cada classe. Os trabalhos de [Selim 83] e [Dinkel 89] também utilizam
modelos em redes.
11
2.3.4 Simulated Annealing)
:
[Abramson 91] apresenta uma aplicação desta técnica
em tabela de horário escolar utilizando algoritmos seqüenciais e paralelos. Ele
considera também como uma extensão, a possibilidade que diferentes classes
possam ter estudantes comuns. Com esta extensão sua solução pode ser também
empregada na categoria de tabela de horário de cursos. Outras referencias sobre a
utilização de Simulated annealing em tabela de horário podem ser encontradas no
trabalho de [Fang 94].
2.3.5 Abordagem com programação lógica:
[Schaerf 95] comenta sobre uma
abordagem de aplicação de programação lógica utilizando o PROLOG como
linguagem de implementação. A maior vantagem desta abordagem é a habilidade de
expressar em um modo declarativo as restrições envolvidas no problema.
2.3.6 Abordagem baseada em restrições:
O trabalho de [Yoshikawa et al 94]
propõem o uso de um solver de problema de relaxação de restrições de propósito
geral, chamado COASTOOL. Em um problema de relaxação de restrições, uma
penalidade é colocada em cada restrição e o objetivo é encontrar uma solução que
minimize o total de penalidades.
2.3.7 Tabu search
: A atual forma de utilização de tabu search é derivada de [Glover
86] e [Taillard 90]. A idéia atrás de tabu search é iniciar com uma solução randômica
e mover sucessivamente para uma vizinhança corrente. Vários autores na literatura
estudaram esta abordagem de solução. Aplicações de tabu search em problemas de
horários podem ser encontradas em [Costa 94]; [Schaerf & Schaerf 95]; [Colorni,
Dorigo & Maniezzo 92], [Hertz 91, 92] e [de Werra 85].
12
2.3.8 Algoritmos Genéticos
: Algoritmos Genéticos (AG) imitam o processo de
seleção natural e podem ser utilizados como uma técnica para resolver problemas
complexos de otimização, os quais apresentam grandes espaços de
pesquisa[Abramson e Abela 92]. Vários trabalhos na literatura propõem a utilização
de AG para resolver problemas de horários, um dos primeiros sucessos da aplicação
de AG em tabela de horários escolares foi desenvolvido em uma escola de segundo
grau italiana e relatado em [Colorni, Dorigo & Maniezzo 92]. Em [Davis 91]
encontramos uma abordagem de uma AG híbrido algoritmo guloso para resolver
problema de grapf colouring simples, os quais são facilmente relacionados com
problemas de tabelas de horários. [Ling 92] usa AG híbrido em um problema de
tabela de horários de professores de uma escola politécnica de Singapura. A
representação utilizada é a semelhante a de [Colorni, Dorigo & Maniezzo 92]. [Chan
94] e [Fang 94] usam uma abordagem similar de representação dividindo a função
de avaliação em uma função custo e uma função penalidade. [Burke, Elliman &
Weare 94] utiliza um algoritmo de graph colouring para primeiro encontrar uma
tabela de horário possível e depois utilizar AG para trabalhar nesta solução inicial.
2.3.9 Programação Matemática
: Programação matemática é uma família de
técnicas para otimizar uma função restringida por variáveis independentes.
Aplicações da programação linear em problemas de horários são apresentados em
[Mata 89], e relaxação lagrangeana é referenciada em [Fang 94]. Uma vasta relação
de autores que solucionaram problemas de tabela de horários utilizando técnicas de
programação linear inteira pode ser encontrada em [Schaerf 95]. Uma aplicação de
Programação Linear Inteira com variáveis 0-1 e de Relaxação Lagrangeana é
apresentada em [Tripathy 84] e [Carter 89], demonstrando que esta técnica pode ser
13
utilizada com sucesso também para grandes problemas de tabela de horário.
Apresentaremos, no item 2.4, com mais detalhes alguns trabalhos publicados na
literatura, relacionados com construção de tabela de horários, modelados através de
programação linear inteira.
2.4 Abordagens relacionadas com Programação Linear Inteira
O problema de construção de um horário escolar apresentado na literatura
de forma geral como Timetabling, possui uma grande variedade de problemas
descritos e muitos caminhos diferentes para a sua solução têm sido propostos. Estes
problemas dependem do tipo de escola e de seu sistema educacional. Desta forma,
não existe um modelo universal que possa ser sempre aplicado.
Quanto aos caminhos propostos para a solução, cada um deles é
desenvolvido para atender certos aspectos de um problema de Timetabling. Se o
tamanho do problema for pequeno, um modelo baseado em programação linear
inteira pode ser utilizado. Conforme cresce a dimensão do problema, é freqüente o
uso de técnicas de decomposição. Outras formulações têm obtido sucesso
considerável, conforme apresentado anteriormente, algoritmo genético; métodos
heurísticos de busca, como por exemplo, a bem conhecida busca tabu; a
programação de lógica de restrições; entre outros.
Vários trabalhos da literatura em Timetabling datam do período de 1960 a
1970 quando se percebeu a possibilidade da utilização de computadores na
resolução deste tipo de problema. Um crescente fluxo de literatura tratando de
aspectos teóricos e soluções computadorizadas apareceram em periódicos de
ciência da computação e pesquisa operacional. Livros foram publicados por diversos
autores no Reino Unido. As abordagens de ciência da computação e pesquisa
14
operacional culminaram com uma extensiva revisão da literatura apresentada em
[Schmidt & Strohlein 80]. Schmidt & Strohlein, discutem, em seu trabalho uma
abordagem de pesquisa operacional a qual consiste essencialmente na utilização de
programação linear inteira.
Em uma das primeiras aplicações de programação linear inteira em
[Lawrie 69], foi usado como variável um conjunto de cursos em uma escola, os quais
podem ser oferecidos ao mesmo tempo sem produzir conflitos. O processo de
construção destes conjuntos de cursos era realizado de forma manual, para em
seguida ser colocado no modelo para ser resolvido. De acordo com a quantidade de
cursos ficaria impossível realizar a construção dos conjuntos.
[Tripathy 84] apresenta um estudo que explora a possibilidade de
aplicação de técnicas de programação matemática para a solução de problemas de
construção de horário. O estudo demonstra a possibilidade de utilizarmos
programação linear inteira para resolver problemas de construção de tabela de
horário com o uso de técnicas de relaxação lagrangeana e incorporação de
procedimentos de branch and bound em um conjunto especial de variáveis. Vários
procedimentos utilizando estratégias de Branch and Bound são referenciados em
[Fang 94].
[Drexl & Salewski 97] apresentam uma formulação de programação
matemática em termos de otimização binária, que permite a solução de problemas
de construção de horários para pequenas instancias, utilizando resolvedores
padrões.
[Oliveira & Pinheiro 2001] apresentam uma formulação matemática
utilizando programação linear inteira para modelar o problema de construção de
15
horário escolar em escolas de ensino médio e resolvê-lo através de solvers padrões
em um ambiente disponibilizado na WEB.
Em [Schaerf 95], foram apresentados vários autores que solucionaram
problemas de tabela de horários utilizando técnicas de programação linear inteira.
2.5. Implementações do Problema de Horário Escolar
Quase todos os trabalhos de tabela de horário descrevem uma significava
implementação de software. Em adição, cada trabalho usualmente apresenta o
resultado da aplicação do método para um ou mais casos de teste.
O sucesso da implementação é medido de duas formas diferentes:
• Número de aulas alocadas referentes ao total. Os resultados relatados
variam de 95% a 100% dependendo de vários casos.
• Valor da função objetivo para a solução ótima. Este valor geralmente tem
um significado prático diferente. Ele pode representar o número de
professores insatisfeitos dependendo da interpretação dada no problema.
Em ambos os casos, os resultados são geralmente comparados com um
resultado anterior adquirido através de procedimentos não automatizados.
Os softwares e o hardware utilizados para o desenvolvimento variam
muito, de acordo com cada caso. Discussões sobre implementações e experiências
podem ser encontradas em [Sabin & Winter 86], e em [Junginger 86].
A técnica de Problema de Satisfação de Restrições (PSR) é definida por
um conjunto de variáveis, cada qual com um discreto e finito conjunto de valores
possíveis e um conjunto de restrições entre estas variáveis [Fang 94]. Uma solução
16
para um PSR é um conjunto de valores de variáveis que satisfaça todas as
restrições. Um exemplo da aplicação de um algoritmo PSR a um problema de tabela
de horários escolar pode ser encontrado em [Meisels et. Al. 93] [Fang 94]. Várias
ferramentas comerciais para PSR são descritas em [Duncan 93], as três principais
ferramentas utilizadas para construir aplicações de tabelas de horários são:
•
CHIP,
originalmente desenvolvida em Munique, é baseada na
linguagem de programação lógica PROLOG;
•
CHARME
, é derivada da CHIP, possui sintaxe parecida com a
linguagem C.
•
ILOG SOLVER
(anteriormente conhecida como PECOS) é uma
biblioteca e não uma linguagem. Ela adota uma abordagem orientada a
objeto e, portanto, é considerada boa para modelagem.
Uma aplicação em tabela de horário implementada na linguagem de
programação CHIP em uma faculdade de medicina em Berlim foi apresentada em
[Goltz 2000]. Em [Mata 89], foi apresentado um modelo heurístico implementado na
linguagem FORTRAN IV com capacidade para 50 professores. Outras técnicas de
implementações através de inteligência artificial podem ser revisadas nos trabalhos
de [Fang 94] e [Schaerf 95].
Conforme apresentado neste tópico, não existe na literatura um trabalho
fortemente baseado na WEB, relacionado com problema de horário escolar. Existem
várias explicações para este fato, uma discussão sobre a utilização da WEB com
Otimização é apresentada em [Dolk 2000]. Na revista Interfaces, volume 31, foi
publicada uma edição especial com vários trabalhos apresentados focando Internet
com Pesquisa Operacional. Destacamos também os trabalhos de [Yen 97a] que
17
descrevem o fluxo de desenvolvimento de ferramentas de simulação baseado na
WEB e de [Yen 97b] que apresenta um modelo e uma implementação de um
sistema de scheduling baseado na INTERNET, no capitulo 3 deste trabalho
detalharemos mais estes artigos.
2.6. Conclusão
Apresentamos uma revisão de vários trabalhos existentes na literatura
sobre o problema de horário, focalizando os modelos propostos, as técnicas de
resolução destes modelos e algumas implementações e os resultados apresentados
nos trabalhos desenvolvidos sobre o assunto, destacamos também alguns trabalhos
sobre a utilização da Pesquisa Operacional com a WEB.
A abordagem da nossa proposta será semelhante à de alguns trabalhos
referenciados nesta seção, principalmente os trabalhos referentes à programação
linear inteira e os sobre à utilização da Pesquisa Operacional com a WEB. Estes
trabalhos aplicados à realidade das escolas de ensino médio da rede pública
estadual serão utilizados como base do referencial teórico para a definição do
ambiente de construção de tabela de horário na WEB.
18
Capítulo 3
APLICAÇÕES DA OTIMIZAÇÃO NA WEB
3.1 Otimização na WEB
Inovações na Ciência da Computação freqüentemente conduziram a
avanços em otimização, acredita-se que o crescimento da Internet possa dar
continuidade a esta tendência. Otimização pode ser considerada como adaptada a
inovações da Internet, principalmente por duas razões.
Primeiro, não há uma única maneira de resolver problemas de otimização.
Centenas de solvers foram desenvolvidos para tirar proveito das características de
tipos de problema particulares. Para muitos tipos de problemas, varias
implementações e diversos métodos competem em velocidade, confiança, custo e
conveniência.
Segundo, novas aplicações de otimização tipicamente envolvem construir
novos modelos. Para suportar esta atividade de construir modelos, sistemas de
modelagem especializados vêm sendo desenvolvidos para construir, analisar e
manter modelos de otimização. Estes sistemas manipulam modelos
independentemente da escolha do solver, e podem ser encaixados em uma
variedade de solvers.
Um profissional que necessite construir uma aplicação em otimização
conseqüentemente deverá construir um ambiente que independentemente do
modelo gerado possa utilizar uma variedade de solvers existentes em pacotes
integrados de otimização. Neste contexto, os serviços disponibilizados pela Internet
19
servem de guia para acessar os diversos softwares de otimização existentes.
Conforme [Czyzyk et all 97] os algoritmos e softwares sobre otimização são
dinâmicos por natureza, sofrendo mudanças em curto espaço de tempo,
contribuindo para a INTERNET ser o mecanismo que disponibiliza facilmente o
acesso às freqüentes atualizações.
As oportunidades e aplicações em Pesquisa Operacional na era da
INTERNET foram assunto de uma edição especial da INTERFACES, volume 31 em
2001, destacando-se os artigos de [Fourer & Goux 2001], [Geoffrion & Krishnan
2001] e [Sodhi 2001] outras fontes de consultas sobre otimização na INTERNET
podem ser encontradas em [Czyzyk et all 97] e [Dolk 2000].
[Fourer & Goux 2001] distinguem três categorias de clientes para software
de otimização de propósito geral.
(1)
Modeladores
trabalham diretamente com solvers e sistemas de
modelagem para construir modelos de otimização e
encontrar maneiras de conseguir soluções aceitáveis.
(2)
Desenvolvedores de Aplicação
criadores de software que rodam
solvers, mas como parte de um grande pacote que trata
desde funções genéricas como gerenciamento de dados a
interface de apresentação gráfica.
(3)
Usuários
utilizam pacotes de aplicação buscando otimização em
algum estágio.
Modeladores se beneficiam mais rapidamente das inovações que auxiliam
pessoas que utilizam software de otimização. Alguns desenvolvedores de aplicações
são também modeladores. Usuários nem sempre sabem que estão utilizando-se de
20
solvers, entretanto, todos são afetados de alguma forma pelas melhorias dos
serviços de otimização, mesmo que indiretamente.
[Geoffrion & Krishnan 2001] comentam sobre a importância da infra-
estrutura para suportar as aplicações na INTERNET, apresentando os ASP
(application service provider), provedores de serviço de aplicação, como importante
exemplo de infra-estrutura segura e com centros de dados com alta disponibilidade
de conexões aos provedores de serviço internet (Internet service provider). Tais
ASPs oferecem uma plataforma para disponibilizar software como um serviço(Figura
3.1).
Figura 3.1: Plataforma de um Provedor de Serviço de Aplicação (ASP) [Geoffrion & Krishnan 2001]
No exemplo um ASP oferece acesso ao software de aplicação executado
em um servidor de aplicação pela Internet a um cliente através de um programa local
(freqüentemente um browser de Internet). O servidor de aplicação tem acesso
seguro a aplicações e banco de dados legado ou caso contrário, por interfaces de
21
programa de aplicação (APIs). Este é um modo crescentemente popular para
empresas de software tornarem o software deles disponível como um serviço.
Considerando a infra-estrutura necessária para disponibilizar as
aplicações na INTERNET, algumas soluções de arquitetura foram definidas para
incluir uma camada de serviços de otimização. A seguir alguns trabalhos sobre este
assunto serão detalhados.
3.2 Solução de Arquitetura de Otimização na Internet
[Cohen et Al 2001] propõem que para explorar o potencial da INTERNET o
processamento seja dividido através de múltiplos servidores de forma a resolver
problemas de otimização de forma conveniente e eficiente. As aplicações devem ser
desenvolvidas de acordo com a arquitetura apresentada na figura 3.2.
Figura 3.2: Arquitetura multicamada para resolver problemas de otimização. [Cohen et Al 2001]
22
Na arquitetura apresentada, o usuário através de um Internet browser
submete um programa a um servidor de aplicação. O servidor de aplicação carrega
informações para construir um modelo como, por exemplo, um modelo linear ou
modelo linear inteiro. Algumas das informações que o usuário necessita para
construir este modelo podem residir em um banco de dados qualquer, o qual pode
ser acessado via um servidor de banco de dados. Ao mesmo tempo o usuário pode
requerer que o modelo seja otimizado. O servidor de aplicação então inicia o
processo em um servidor de otimização. Passando este modelo (regras de negócio)
para encontrar a solução.
O servidor de otimização pode também necessitar acessar o banco de
dados. Quando este finalizar a otimização, o servidor de otimização envia a um
usuário uma mensagem de email com uma URL(uniform resurce locator) que
apresenta a solução, ou pode ser também publicado um relatório com a solução em
diferentes canais de um portal na INTERNET. O servidor de aplicação pode
processar esta URL e disponibilizar a solução armazenando no banco de dados.
[Cohen et Al 2001] considerando a classificação dos dados em estáticos e
dinâmicos e a necessidade especifica de cada tipo de problema de otimização,
propõem uma arquitetura de dados para suportar soluções de otimização baseadas
na INTERNET. Utilizando-se de um sistema de ERP (enterprise resource
planning) e um sistema de dados legados sob um data warehouse, os dados
instantâneos destes sistemas transacionais são periodicamente armazenados dentro
de um datawarehouse. Soluções (expressadas por modelos de negócios e
resolvedores em servidores de otimização) localizados acima dos dados do data
warehouse, são saídas deste feedback entre o warehouse e o ERP. Conforme
23
apresentado na figura 3.3, pode-se verificar soluções de APS (planejamento
avançado e escalonamento), PDIO (otimização de distribuição de produção e
estoque) e IRP (planejamento de reabastecimento de estoque) como saídas desta
arquitetura.
Figura 3.3: Arquitetura de dados na INTERNET para otimização. [Cohen et Al 2001]
Outra abordagem pode ser encontrada em [Yen 97a], propondo a
arquitetura de uma ferramenta de simulação baseada na INTERNET, como sendo
composta de quatro componentes. Conforme figura 3.4:
Figura 3.4. Arquitetura de simulação baseada na INTERNET. [Yen 97a]
24
[Yen 97a] apresenta os componentes da arquitetura como sendo:
(1) Database. As estruturas e funções dos objetos são
armazenadas e manipuladas em um banco de dados.
Existem dois tipos de objetos definidos como base – os
primitivos e os de aplicação. Os de aplicação são derivados
dos primitivos.
(2) Designer. É a ferramenta com interface gráfica que
possibilita ao usuário construir e editar o desenho do
sistema. Usando o designer, usuários podem arrastar ou
deletar objetos do sistema e especificar atributos
correspondentes.
(3) Compiler. Durante o processo de desenho, o compilador
checa se a estrutura ou sintaxe do sistema estão corretas. A
checagem da sintaxe pode ser feita no modo interativo, para
verificar o desenho imediatamente após cada passo, ou no
modo batch, para verificar a correção depois de submetido à
requisição. As checagens das regras são definidas como
gramáticas similares às de sintaxe de linguagem de
programação.
(4)
Simulator
. Diferente da correção estrutural, o simulador
verifica as correções funcionais ou semânticas do sistema.
Em adição, este também simula o processo do sistema com
animações e avaliar a performance.
25
O fluxo do processo de uma ferramenta de simulação, de acordo com [Yen
97a], é o seguinte: O designer,
a partir de um database e através de uma
ferramenta gráfica, edita o modelo e o configura de acordo com suas características,
enviando para o compiler
que checa a estrutura e envia para o simulator gerar o
cenário da solução devolvendo para a análise do designer. Este fluxo continua até
que os resultados sejam os esperados. Conforme figura 3.5.
Figura 3.5. Fluxo de uma ferramenta de simulação baseada na INTERNET. [Yen 97a]
3.3 Ambientes de Otimização na Internet
Segundo [Fourer & Goux 2001] o recente uso da Internet em otimização
limitava-se a prover software para download. Assim muitos solvers não comerciais
estiveram por muito tempo disponíveis via protoco ftp, geralmente através de sites
mantidos por seus desenvolvedores. O primeiro site central para downloading de
software matemático, o repositório NETLIB , começou no inicio de 1980 e incluía
uma variedade de solvers.
26
O advento da Internet tem encorajado extensivas relações de recursos
online, incorporando listas de links de hipextexto para downloads e também muitos
outras informações.
O Decision Tree for Optimization software, desenvolvido por Hans
Mittelmann e Peter Spellucci, organizou software de otimização não comercial por
tipo de problema. Este site também lista problemas testes, livros, tutoriais,
modelagem de sistemas, pacotes de diferenciação automáticos, e ferramentas de
análise de modelos. O site ZIB MATHPROG também oferece links para muitas
classes de códigos de otimização de domínio público e informações relacionadas.
Vários resolvedores de diferentes tipos de modelos de otimização, usando
servidores de otimização e outros recursos, podem ser encontrados com mais
detalhes em [Fourer & Goux 2001].
[Geoffrion & Krishnan 2001] apresentam várias fontes de computações
estatísticas disponíveis na internet como StatLib, StatPages.net, StatPoint Internet
Statistical Computing Center, e SticiGui. Neste mesmo trabalho pode ser encontrada
uma vasta relação de opções na Internet para projetos que requerem construção de
aplicações disponíveis na INTERNET, que necessitem construir modelos e
disponibilizar os resultados pela INTERNET, ou que necessitem de pesadas
ferramentas industriais, e também, uma relação de fornecedores que se
especializaram em fornecer a infra-estrutura necessária para executar as aplicações
dos clientes, através de terceirização.
O NEOS (Network-Enable Optimization System) apresentado em
[Czyzyk et all 97] forma um ambiente de cooperação desenvolvido pelo Laboratório
27
Nacional de Argonne e Universidade de Northwestern, para possibilitar a resolução
de problemas de otimização através da Internet.
Esse ambiente é formado por três componentes básicos: ferramentas
NEOS, o guia NEOS e o servidor NEOS.
• Ferramenta NEOS é uma biblioteca de softwares de otimização gratuitos escritos
por pesquisadores no projeto NEOS;
• O guia NEOS é uma listagem atualizada que descreve a teoria sobre área de
otimização, incluindo FAQs com links para códigos comerciais e não comerciais
que oferecem gratuitamente downloads de versões demos para programação
linear e não linear;
• O servidor NEOS é o componente que possibilita o acesso do usuário à
biblioteca NEOS através da Internet. Os usuários podem submeter seus
problemas através de email, WWW ou ferramenta windows. Estes problemas são
alocados e resolvidos em uma estação de trabalho em Argonne, Northwestern.
A estrutura do ambiente NEOS é centralizada, como mostrada na Figura
3.6. Todos os hosts que integram esse ambiente devem ser cadastrados no servidor
NEOS. As requisições de clientes são sempre direcionadas para esse servidor.
Figura 3.6. Estrutura do ambiente NEOS. [Czyzyk et all 97]
28
Segundo [Czyzyk et all 97], três tipos de requisições são aceitas. Os
usuários podem submeter problemas de otimização ao servidor via e-mail, através
de uma página da Internet ou pela ferramenta de submissão disponibilizada. Ao
receber essas requisições, o servidor as distribui aos resolvedores de otimização
(Optimization Solvers) responsáveis pela execução do algoritmo.
O conjunto de algoritmos disponibilizado pelos resolvedores de otimização
forma a biblioteca de software NEOS. Essa biblioteca possui a característica de ser
distribuída, pois os resolvedores de otimização são hosts espalhados em diferentes
espaços de endereçamento conectados pela Internet. A comunicação entre o
servidor NEOS e esses resolvedores é baseada em sockets.
O NEOS possui um sistema de alocação de recursos distribuídos que
garante ao ambiente o balanceamento de carga e tolerância à falhas esperadas.
No guia NEOS alguns problemas de otimização como estudo de casos
são apresentados, dentre eles:
• O problema da dieta utilizando programação linear;
• Otimização de portifolio utilizando programação quadrática;
• Planejamento de gás natural utilizando programação linear estocástica.
• O problema de cutting-stock utilizando programação linear inteira.
O servidor NEOS é o componente central do NEOS. Através dos solvers
e do servidor, são suportados problemas de várias áreas tais como, programação
linear, programação linear estocástica, otimização de redes linear, otimização sem
restrição.
29
3.4 Conclusão
Neste capitulo, foram apresentados os trabalhos de alguns autores da
literatura de Pesquisa Operacional, destacando a importância da utilização da
Internet para a área de otimização. Foram referenciados as oportunidades
oferecidas e o futuro da otimização utilizando a INTERNET.
Apresentamos como deve ser a arquitetura de uma ferramenta de
otimização utilizando a Internet, considerando a definição da infra-estrutura
necessária segundo os trabalhos de [Geoffrion & Krishnan 2001]; a divisão em
camadas e a arquitetura de dados segundo os trabalhos de [Cohen et Al 2001] e a
arquitetura de simulação baseada na INTERNET nos trabalhos de [Yen 97a]. Alguns
dos ambientes de otimização disponíveis atualmente foram abordados destacando o
NEOS apresentado no trabalho de [Czyzyk et all 97].
Este referencial teórico será utilizado como base para a definição da
arquitetura do ambiente de construção de tabela de horário escolar na INTERNET,
apresentado neste trabalho.
30
Capítulo 4
O AMBIENTE DE CONSTRUÇÃO DE TABELA DE HORÁRIO
ESCOLAR NA WEB
4.1 O Problema nas Escolas do Estado
Neste capitulo, será apresentado o problema da construção de horário nas
escolas de ensino médio do Estado do Ceará. Para auxiliar o entendimento se faz
necessário o conhecimento da forma como estão estruturados os vários
componentes envolvidos nas escolas, dentre eles a organização das escolas, a
grade curricular e a forma de contratação dos professores.
4.1.1 Organização das Escolas
As escolas estaduais atualmente estão organizadas através dos Centros
Regionais de Desenvolvimento da Educação (CREDES), responsáveis pela gestão
educacional das escolas vinculadas. Os diretores de escolas realizam a gestão
educacional de cada escola individualmente.
O Estado do Ceará possui atualmente 21 CREDES, abrangendo todas as
regiões do Estado. O Ensino Médio no Estado é atendido por 421 escolas
localizadas na capital e no interior do Estado.
As escolas de ensino médio funcionam de maneira geral, nos turnos da
manhã, tarde e noite. O ensino médio é formado por 1
o
ano, 2
o
ano e 3
o
ano,
31
podendo ter mais de uma turma por turno, denominadas geralmente por letras do
alfabeto A, B...Z. Conforme apresentado na figura 4.1.
Figura 4.1: Estrutura das Escolas de Ensino Médio do Estado.
Cada aula é dividida em 50 minutos nos turnos manhã e tarde e com
intervalos variados no turno da noite, sendo que este tempo deve ser computado até
completar a carga horária exigida pela disciplina. Uma tabela com as divisões de
tempo para cada turno, será apresentada a seguir.
TURNO HORA
TURNO HORA
TURNO HORA
Manhã 07:10h Tarde 13:00h Noite 18:20h
08:00h 13:50h
19:10h
09:10h 15:00h
19:55h
10:00h 15:50h
20:50h
10:50h 16:40h
21:30h
Tabela 4.1: Intervalos de aulas por turno adotado no Estado.
32
Portanto, de acordo com a tabela 4.1, podem ser alocadas 5 aulas por dia
da semana, sendo que no total existem 25 possibilidades de se alocar uma disciplina
considerando-se a quantidade de dias úteis da semana.
4.1.2 A Grade Curricular
A grade curricular é uma peça fundamental para a construção do horário
escolar. Destas grades curriculares são extraídos dados importantes para a
implantação do modelo matemático apresentado neste trabalho, como por exemplo:
Lista de disciplinas de cada serie; Carga horária semanal de cada disciplina por
serie; Carga horária semanal total da serie. A tabela 4.2 apresenta um exemplo de
grade curricular para o 1
o
ANO do ensino médio.
ETAPA: 1º ANO – A MANHÃ
HISTÓRIA 2
GEOGRAFIA 2
FILOSOFIA 2
ARTE E EDUC. 1
PORTUGUÊS 4
INGLÊS 2
EDUC. FÍSICA 2
MATEMÁTICA 4
FÍSICA 2
QUÍMICA 2
BIOLOGIA 2
Tabela 4.2: Exemplo de grade curricular para o 1
o
ANO.
33
4.1.3 Forma de Contratação de Professores pelo Estado
O Governo do Estado contrata atualmente os professores através de um
uma quantidade de horas fixas (exemplo 100 horas, 200 horas e 300 horas), seja
efetivo ou temporário, sendo que cabe aos diretores de Escola alocar de acordo com
suas necessidades os professores e informar ao CREDE caso o professor não tenha
sua carga horária totalmente alocada, para que possa ser utilizada em outra Escola.
Portanto no momento da construção do horário escolar deve ser respeitada a carga
horária máxima a ser alocada para determinado professor, de acordo com o contrato
do mesmo com o Governo do Estado.
Cada professor, no momento do contrato, de acordo com sua habilitação,
será relacionado com as disciplinas específicas de cada série que o mesmo pode
poderá lecionar. Como exemplo, João Dantas poderá lecionar matemática no 1
o
Ano e Física no 2
o
Ano.
4.1.4 Forma de Construção da Tabela de Horário Escolar
O problema da construção dos horários escolares tem a sua definição
bastante diversificada de acordo com as características de cada instituição e a
concepção dos dirigentes das escolas, obviamente as restrições apresentadas
podem ou não ser adotadas. Portanto a solução para este problema deve permitir
que se possa decidir entre a inclusão ou não de determinada restrição.
Atualmente a elaboração do horário escolar de cada unidade de ensino
médio estadual, é realizada, de forma geral, da seguinte maneira:
34
a) A relação de lotação dos professores com as disciplinadas habilitadas, é
enviada em cada período letivo a cada unidade de ensino estadual, através
da Secretaria de Educação do Estado;
b) Os dirigentes de escola coletam as informações sobre as indisponibilidades
de horários de cada professor;
c) De posse destas duas informações e com a relação de turmas que a escola
está ofertando, o dirigente faz a designação de cada professor, construindo
o quadro de horário escolar da instituição.
4.2 O Modelo em Programação Linear Inteira
O processo de construção de uma tabela de horário escolar, pode ser
dividido em três fases principais.
• Definição dos dados de entrada relativos às turmas de alunos;
• Definição dos dados de entrada relativos aos professores;
• Determinação de período em que cada aula será lecionada.
As duas primeiras fases envolvem decisões legais e administrativas, e são
fornecidas por sistemas secundários (conforme figura 4.2) ou de forma manual,
pelos dirigentes das escolas.
35
Figura 4.2. Estrutura de um ambiente de Gestão Escolar integrado com o ambiente
de construção de tabela de horário.
Os dados dos professores necessários a construção do modelo estão
relacionados na tabela 4.3.
Professor
Disciplinas lecionadas;
Disponibilidade de horários para todos os dias que têm aula;
Séries lecionadas.
Tabela 4.3: Dados dos professores necessários ao modelo matemático.
Módulo de Resolução do
Problema de Geração de
Tabela de Horário
Sistema de
Gerenciamento
Escolar
Dados dos
Alunos
Dados dos
Professores
Dados das
Turmas
Tabela de
Horários
36
Os dados das disciplinas e turmas necessários a construção do modelo
estão relacionados na tabela 4.4.
Disciplinas/Turmas
Horário das aulas; (quantidade de aulas por turno)
Dias da semana que têm aula;
Disciplinas lecionadas por série, com a respectiva carga horária;
Quantidade de turmas formadas por série;
Carga horária de cada disciplina por série;
Carga horária total da série.
Tabela 4.4: Dados das disciplinas/turmas necessários ao modelo.
Após a conclusão das primeiras duas fases, o problema fica definido e
conseqüentemente os dados estarão disponíveis para serem usados na terceira
fase. Apresentaremos a formulação do modelo matemático e definiremos a
terminologia utilizada a seguir.
Considerando a variável de decisão a seguir:
X
ijkl
( i = professor , j = horário , k = disciplina
, L
= turma ),
onde x
ijkl
= 1 se professor
I
leciona no horário
J
a disciplina
K
da turma
L
,e
x
ijkl
= 0 caso contrário. Assim podemos definir:
Função objetivo:
Seja
m
o número de professores a serem considerados como
participantes na tabela de horário em questão;
n
o número de horários que podem
ser considerados na tabela de horário;
p
o número de disciplinas que podem ser
37
consideradas na tabela de horários e
q
o número de turmas que podem ser
consideradas na tabela de horários, temos:
m n p q
min
∑
∑∑
∑
∑
∑∑
∑
∑
∑∑
∑
∑
∑∑
∑
c
ijkl
x
ijkl
i=1 j=1 k=1 l=1
Onde um valor
c
ijkl
é designado para período
j
no qual uma aula de professor
i
para
disciplina
k
de uma turma
L
é menos desejável. Esta constante custo será
inicializada com o valor 1, para efeito de estudo de caso, mais será mantida no
modelo para que o mesmo esteja preparado para futuras implementações onde seja
necessária altera-la.
Por fim, precisamos enumerar as restrições do modelo, de
acordo com os dados obtidos nas fases anteriores. Temos então:
Restrições:
1. Um professor deve estar em, no máximo, uma única turma no mesmo dia e
horário em que ele estiver disponível.
Σ
ΣΣ
Σ
j
∈
∈∈
∈
J
Σ
ΣΣ
Σ
k
∈
∈∈
∈
K
Σ
ΣΣ
Σ
l
∈
∈∈
∈
L
x
ijkl
≤
≤≤
≤
1
∀
∀∀
∀
i , onde
I – conjunto de professores que lecionam em k.
J - conjunto de horários definidos como disponíveis pelo professor i.
K - conjunto de disciplinas por turma lecionadas pelo professor i.
L - conjunto de turmas lecionadas pelo professor i.
38
2. Uma turma pode ter, no máximo, um professor alocado em cada horário de aula.
Σ
ΣΣ
Σ
i
∈
∈∈
∈
I
x
ijk
≤
≤≤
≤
1
∀
∀∀
∀
j ,
∀
∀∀
∀
k ,
∀
∀∀
∀
l onde
I - conjunto de professores que lecionam em k
J - conjunto de horários definidos como disponíveis pelo professor i
K - conjunto de disciplinas por turma lecionadas pelo professor i
L - conjunto de turmas lecionadas pelo professor i.
3. A carga horária semanal de cada disciplina de todas as turmas deve ser
respeitada.
Σ
ΣΣ
Σ
j
∈
∈∈
∈
J
x
ijkl
= C
∀
∀∀
∀
i,
∀
∀∀
∀
k ,
∀
∀∀
∀
l onde
I - conjunto de professores que lecionam em k
J - conjunto de horários definidos como disponíveis pelo professor i
K - conjunto de disciplinas por turma lecionadas pelo professor i
L - conjunto de turmas lecionadas pelo professor i.
C - carga horária semanal de cada disciplina de cada turma
4. Se a carga horária total de uma turma for inferior a carga total do colégio, os
horários livres desta turma deverão ser os últimos horários de cada dia.
Σ
ΣΣ
Σ
j
∈
∈∈
∈
M
x
ijkl
= 1
∀
∀∀
∀
i ,
∀
∀∀
∀
k ,
∀
∀∀
∀
l onde
39
K - conjunto de disciplinas por turma lecionadas pelo professor i
L - conjunto de turmas lecionadas pelo professor i.
M - conjunto dos horários iniciais para cada dia da semana
Σ
ΣΣ
Σ
j
∈
∈∈
∈
N
x
ijkl
≤
≤≤
≤
1
∀
∀∀
∀
i ,
∀
∀∀
∀
k ,
∀
∀∀
∀
l onde
N - conjunto complementar de M
5. Um professor não pode dar aulas seguidas a uma mesma turma mesmo que
sejam matérias diferentes.
x
ijkl
+
x
ij+1kl
≤
≤≤
≤
1
∀
∀∀
∀
i ,
∀
∀∀
∀
j ,
∀
∀∀
∀
k ,
∀
∀∀
∀
l, onde:
I - conjunto de professores que lecionam em k
J - conjunto de horários definidos como disponíveis pelo professor i
K - conjunto de disciplinas por turma lecionadas pelo professor i
L - conjunto de turmas lecionadas pelo professor i.
Quanto a esta restrição alguns diretores de escolas incentivam o caso
contrário, portanto o sistema pode desabilitar esta restrição de acordo com a
configuração informada pelo dirigente.
Este modelo pode ser alterado com a inclusão de outras restrições que os
diretores das escolas considerem necessárias. A forma de habilitar estas restrições
antes da geração do modelo matemático, torna o modelo adaptável às diferentes
realidades das escolas. Portanto, esta característica de ser configurável, permite
40
uma flexibilidade que torna o ambiente de construção de tabela de horário escolar
na INTERNET, aplicável a todas as 421 escolas do Estado do Ceará.
Outra característica relevante é a transparência das técnicas de
modelagem matemática para os diretores de escolas, os quais através de uma
interface amigável, desconhecem a forma como é construído o modelo, e
conseqüentemente como está sendo solucionado o problema de construção da
tabela de horário de sua escola.
4.3 A Arquitetura do Ambiente na INTERNET
O Ambiente de construção de tabela de horário na INTERNET é composto
por múltiplos servidores segundo a arquitetura proposta por [Cohen et Al 2001] para
ambientes de otimização na Internet. Apresentamos na figura 4.3 como estão
distribuídos os componentes do ambiente.
Figura 4.3. Arquitetura do Ambiente de otimização na INTERNET.
41
Conforme descrito na figura 4.3, o componente utilizado pelo usuário pode
ser qualquer browser INTERNET padrão de mercado, como por exemplo, Internet
Explorer ou Netscape, é através dele que o usuário realiza suas interações com o
Ambiente, podendo acessá-lo de qualquer computador ligado a Internet. Cada
diretor de Escola possui um login e uma senha, para poder acessar as informações
da Escola que o mesmo é gestor, podendo alterar, consultar, configurar e resolver os
modelos matemáticos que irão gerar a tabela de horário da Escola.
O segundo componente da arquitetura é o Servidor INTERNET, utilizamos
o IIS da Microsoft , como apresentado na figura 4.3. Este componente disponibiliza
para os browsers as páginas estáticas e dinâmicas do ambiente na INTERNET. Nos
testes realizados e apresentados no próximo capítulo foi utilizado o servidor
Personal Web Server, contudo poderia ser o APACHE, ou outro servidor
semelhante, considerando que fica transparente para o ambiente onde está sendo
utilizado.
No terceiro componente estão armazenados no servidor de aplicação dois
módulos de aplicativos. O primeiro módulo é uma aplicação em DELPHI da Borland
que fará a interface com o servidor de otimização. Este módulo será responsável em
repassar o modelo gerado e receber sua solução do resolvedor. O segundo módulo
são CGI’s DELPHI da Borland, que será o aplicativo que irá realizar a interface com
o servidor de banco de dados gerando o modelo matemático a ser submetido ao
resolvedor e atualizando a base de dados, disponibilizando aos diretores de escolas
as consultas dos resultados do modelo e outras informações disponíveis.
42
No quarto componente da arquitetura foi utilizado como Servidor de Banco
de Dados o INTERBASE, considerando que foi o banco de dados utilizado nos
testes do ambiente, conforme figura 4.3. O ORACLE será a plataforma definitiva de
banco de dados a ser utilizada pelo Ambiente nas instalações da Secretaria de
Educação. Ressaltamos que o ambiente está preparado para utilizar qualquer banco
de dados relacional de mercado que possua drivers ODBC.
O quinto e último componente da arquitetura apresentada na figura 4.3 é o
servidor de otimização ou resolvedor. Foi utilizado como software matemático de
otimização o pacote
Lindo 6.0
da LINDO Systems INC. Neste componente serão
resolvidos os modelos matemáticos gerados pelo ambiente de construção de tabela
de horário. Através de um aplicativo que servirá de interface entre o servidor de
aplicação e o servidor de otimização, o modelo gerado será recebido e resolvido
pelo Lindo. O resultado gerado será devolvido para o servidor de aplicação atualizar
a base de dados com a tabela de horário gerada.
Este ambiente caracteriza-se pela sua arquitetura distribuída, suporte à
execução de problemas de otimização, política de controle de acesso e
disponibilidade na Internet.
O trabalho de [Yen 97a], que propõem uma estrutura de uma ferramenta
de simulação baseada na INTERNET, composta por quatro componentes
(Database, Designer, Compiler e Simulator), foi utilizado como base para o módulo
de geração do modelo matemático. Fazendo uma analogia ao modelo apresentado
no trabalho, definiremos como foi composto o módulo de otimização do ambiente
proposto:
43
Database – Esta é a estrutura central do ambiente de modelagem
matemática, considerando que as estruturas de dados são armazenadas em um
banco de dados relacional e a partir deste serão recuperadas as informações para
geração do modelo e apresentação dos resultados após a sua solução.
Designer
–
Esta estrutura é a interface gráfica disponibilizada para os
diretores de escolas na INTERNET, acessada através de um Browser. É utilizada na
fase de modelagem para configurar as opções de restrições a serem geradas no
modelo, bem como para atualizar a base de dados através das seguintes opções:
• Configuração das restrições habilitadas para o modelo matemático do
colégio;
• Alteração da base de dados do colégio;
• Iniciação do processo de geração e resolução do modelo;
• Geração de relatórios da tabela de horário para as turmas e para os
professores, dentre outras.
Compiler – Esta estrutura será utilizada para a edição do modelo de
programação linear inteira gerado e verificação das alternativas de restrições
utilizadas, bem como para checagem dos parâmetros utilizados no modelo.
Simulator – Nesta estrutura o modelo matemático utilizando as técnicas
de programação linear inteira, será resolvido através de um Software Comercial de
otimização instalado no servidor de otimização, podendo a solução ser efetivada ou
não no banco de dados do ambiente de acordo com os resultados da simulação.
O ambiente de construção de horário escolar na INTERNET é composto
de uma ferramenta de simulação conforme proposto por [Yen 97a] e de uma
arquitetura de ambiente de otimização na internet conforme proposto por [Cohen et
44
Al 2001], para oferecer uma flexibilidade na aplicação em outros problemas que
possam existir no Serviço Público Estadual e que possam ser resolvidos através das
técnicas de pesquisa operacional.
Esta forma de implementar o ambiente de otimização na INTERNET
permite que vários problemas possam ser solucionados com métodos de resolução
variados, sem causar grande impacto nos demais componentes do ambiente. Foram
utilizadas técnicas de programação linear inteira para a modelagem do problema e
como resolvedor o Lindo API na implementação deste ambiente, outras
metodologias de otimização e solvers poderão ser utilizadas de forma transparente
para os demais componentes.
4.4 Descrição do Ambiente de Construção de Tabela de Horário Escolar
O principal objetivo do ambiente de Construção de Tabela de Horário
Escolar é oferecer um ambiente para suportar o atendimento das 421 escolas de
ensino médio do Estado do Ceará na área de otimização de alocação de
professores a horários. O ambiente apresentado possui as seguintes características:
Acesso pela Internet
: Considerando o cenário econômico e a existência de várias
instituições distribuídas geograficamente pelo Estado, esta característica é de
natureza essencial ao ambiente;
Configurável
: devido à autonomia das instituições, cada uma está apta a configurar,
conforme as necessidades e disponibilidades locais, o conjunto de restrições do
modelo matemático a ser gerado;
45
Arquitetura Multicamadas
: para facilitar a aplicabilidade a outros problemas de
otimização e a reusabilidade do ambiente.
4.4.1 Estrutura de Dados do Ambiente de Construção de Tabela de Horário
Escolar
A estrutura de dados armazenada no servidor de banco de dados
fornecerá todas as informações para o controle de acesso, geração do modelo
matemático, geração das consultas e relatórios. Será apresentada a seguir esta
estrutura de dados, através da figura 4.4.
Figura 4.4. Estrutura de Dados armazenada no Banco de Dados.
46
Algumas tabelas da Estrutura de Dados são originadas dos sistemas
tradicionais de Gestão Escolar, outras são alimentadas pelos diretores das escolas e
as demais são atualizadas pela resolução do modelo matemático, gerado pelo
Ambiente. Serão detalhadas a seguir, as entidades que compõem a estrutura de
dados.
•
TB_Carga_Horaria
- Esta entidade armazena a quantidade de carga horária
necessária para cada disciplina de determinada etapa. Por exemplo, 4 horas
para matemática do 3
o
ANO.
•
TB_Colegio
- Esta entidade armazena o cadastro com as escolas de ensino
médio do Estado. Permitindo que o controle de acesso seja individualizado
por cada colégio. Por exemplo, o diretor do colégio Renato Braga, só poderá
alterar os dados do próprio colégio.
•
TB_Disciplina -
Esta entidade armazena a relação de disciplinas ministrada
no ensino médio. Exemplo, matemática, física, etc.
•
TB_Etapa -
Esta entidade armazena as etapas que compõem o ensino
médio. Exemplo, 1
o
ANO, 2
o
ANO e 3
o
ANO.
•
TB_Horário -
Esta entidade armazena os intervalos de horas que compõem
uma aula por dia da semana. Exemplo, 13:00 as 13:50 de segunda-feira.
•
TB_Indisponível -
Esta entidade armazena os intervalos contidos na TB-
Horário, que determinado professor não pode lecionar. Correspondem as
restrições de horários de cada professor. Exemplo, 13:00 as 13:50 de quarta-
feira.
47
•
TB_Lecionar -
Esta entidade armazena quais disciplinas de determinada
etapa o professor pode lecionar. Exemplo, Professor José pode lecionar
Matemática do 2
o
ANO e Física do 1
o
ANO.
•
TB_Professor -
Esta entidade armazena o cadastro dos professores
contratados pelo Estado para ministrar o ensino médio.
•
TB_Turma -
Esta entidade armazena todas as turmas de cada etapa em
determinado colégio. Exemplo, 1
o
ANO A TARDE do Renato Braga.
•
TB_Turma_Disciplina -
Esta entidade armazena a tabela de horário gerada
pelo modelo matemático para determinada turma de um colégio.
•
TB_Usuário -
Esta entidade armazena todos os usuários do ambiente de
construção de tabela de horário escolar, seja diretor de escola ou da área
técnica e administrativa.
4.4.2 Componentes do Ambiente de Construção de Tabela de Horário Escolar
O Ambiente de Construção de Tabela de Horário Escolar é formado por
um conjunto de componentes que interagem para a resolução de um problema. A
composição deste conjunto de componentes é a seguinte: Controle de Acesso,
Configurador do Modelo, Gerador do Modelo, Editor do Modelo, Resolvedor do
Modelo e a Interface de Consultas e Relatórios. A Figura 4.5 mostra a organização
destes componentes na arquitetura do Ambiente.
48
Figura 4.5. Organização dos componentes do Ambiente na INTERNET.
Os componentes do ambiente, Configurador do Modelo, Gerador do
Modelo e Editor do Modelo, conforme demonstrado na figura 4.5, formam o que
denominamos de centro de simulação e podem ser utilizados pelo usuário para
simular diversas situações. Após concluir a simulação o modelo pode ser repassado
para ser resolvido e a sua solução armazenada na base de dados.
Cada componente apresentado na figura 4.5 pode ser considerado como
um módulo computacional. Todos os módulos estão interligados através de uma
interface e apesar de trabalharem em conjunto diferem na forma de implementação
conforme descrito na seção anterior.
49
•
Controle de Acesso –
O módulo de controle de acesso gerencia todo o
acesso dos usuários ao ambiente na INTERNET. Através da interface
mostrada na figura 4.6, o módulo solicita o login e a senha do usuário. Após
validado o usuário poderá realizar todas as opções do ambiente
disponibilizadas para o seu nível de acesso. Este módulo interage
principalmente com as tabelas TB-Usuário e TB-Colégio.
Figura 4.6 : Interface do módulo de controle de acesso.
50
•
Menu Principal –
O menu principal é a interface disponibilizada ao diretor de
escola após o login no ambiente. A partir dele todas as opções podem ser
acessada, conforme figura 4.7.
Figura 4.7 : Interface do menu principal.
•
Configurador do Modelo –
O configurador do modelo compõe um dos
componentes conceituais do Centro de Simulação. Através deste módulo o
Diretor de Escola terá acesso às opções de restrições do Modelo Matemático,
podendo ativar ou desativar determinada restrição do modelo. Outras opções
disponíveis dizem respeito às turmas a serem oferecidas para cada etapa, e a
alteração de indisponibilidade de horários de determinado professor. As
51
opções escolhidas serão utilizadas pelo módulo Gerador do Modelo. A
interface do configurador do modelo pode ser visualizada através da figura
4.8.
Figura 4.8 : Interface do módulo configurador do modelo.
•
Gerador do Modelo -
O módulo Gerador do Modelo possui uma interface
bastante simples conforme figura 4.9. O usuário submete uma requisição ao
Gerador do Modelo através de um botão, que é responsável por executar uma
rotina que lê a base de dados, que pode ter sofrido alguma atualização com
as alterações realizadas pelo configurador do modelo, em seguida gera um
arquivo texto com o modelo gerado. Este arquivo texto pode ser visualizado
através do editor ou utilizado pelo módulo resolvedor do modelo para construir
52
a tabela de horários. O gerador do modelo compõe o segundo modulo do
Centro de Simulação.
Figura 4.9 : Interface do módulo Gerador do Modelo.
•
Editor do Modelo
- O Editor complementa o modelo conceitual do Centro de
Simulação. Através deste módulo o usuário pode editar o modelo gerado pelo
módulo gerador e verificar todas as variáveis e restrições geradas. Esta opção
compõe o ambiente, mas não será utilizada necessariamente pelo Diretor de
Escola, pois requer conhecimento em modelagem ou programação. Contudo
foi implementada para futuras utilizações em outras aplicações a serem
53
adicionadas ao ambiente. Um exemplo de utilização deste módulo pode ser
visualizado na figura 4.10.
Figura 4.10 : Interface do módulo Editor do Modelo.
•
Resolvedor do Modelo
- O módulo resolvedor do modelo, conforme figura
4.11, pode ser executado a partir de um conjunto de opções informadas.
Pode resolver o problema de geração de tabela de horários de forma parcial,
deixando a critério do usuário a forma de resolver o modelo linear inteiro. Um
exemplo de resolução pode ser a geração da tabela de horário apenas de
54
uma determinada etapa, em que foi alterada alguma restrição de professor. O
funcionamento deste módulo pode ser dividido nas 3 fases seguintes:
o Leitura do arquivo texto;
o Submissão do arquivo para o software de otimização que resolverá
o modelo linear inteiro;
o Recebimento e gravação na base de dados do resultado gerado
pelo software de otimização.
Figura 4.11 : Interface do módulo de resolvedor do modelo.
•
Interface de Consultas e Relatórios
- A Interface de Consultas e Relatórios
é o módulo responsável por disponibilizar aos usuários uma interface gráfica
55
pela qual possam submeter requisições ao Ambiente de Construção de
Tabela de Horário Escolar e visualizar respostas via Internet. A Figura 4.12
mostra a interface do usuário:
Figura 4.12 : Interface do módulo de Consultas e Relatórios.
Através deste modulo o usuário realiza uma série de consultas e gera
relatórios dentre eles:
• Horários de indisponibilidades de professores;
• Horários alocados por professores;
• Tabela de horários por turma;
• Tabela de horário por etapa;
• Relação de professores alocados por etapa e turma.
56
4.5 Conclusão
Neste capitulo, foi apresentado o problema da construção de tabela de
horário escolar conforme a realidade das Escolas de ensino médio do Estado do
Ceará, destacando-se a organização das escolas, a grade curricular, a forma de
contratação de professores pelo estado e a forma de construção da tabela de
horário escolar utilizada atualmente pelos diretores de escolas.
O modelo de programação linear inteira utilizado para modelar o problema
foi apresentado, demonstrando como foram definidas as variáveis e a forma de
representação das restrições do modelo.
Apresentou-se a Arquitetura do Ambiente na WEB com base nos
referenciais teóricos apresentados e como foi implementado o protótipo utilizado
neste trabalho. Considerações com respeito a futuras implementações foram
referenciadas.
Finalmente, foi apresentada a descrição do Ambiente de Construção de
Tabela de Horário Escolar, destacando-se a estrutura de dados armazenada no
banco de dados, como elemento central, para o pleno funcionamento dos módulos
computacionais que compõem a estrutura do Ambiente. Foi apresentado cada
módulo isoladamente e demonstrada a forma de interface para o usuário.
57
Capítulo 5
TESTES E RESULTADOS
5.1 Descrição do Estudo de Caso
Este capítulo tem como objetivo mostrar os resultados experimentais de um
estudo de caso em uma escola utilizando o ambiente de Construção de Tabela de
Horário Escolar na WEB. Nos testes realizados foram verificados os seguintes itens:
o desempenho dos componentes do ambiente quanto ao perfeito funcionamento e a
viabilidade da utilização do modelo de programação linear inteira para a resolução
do problema gerado de acordo com a realidade da escola.
Para a realização do teste do ambiente foi utilizada uma típica escola de
ensino médio estadual. Os dados utilizados para a simulação foram os seguintes:
• 1(uma) turma do turno da manhã do 1o ANO denominada A;
• 13(treze) professores habilitados a ministrar as disciplinas desta turma;
• 11(onze) disciplinas com as respectivas cargas horárias para a etapa;
• 25(vinte e cinco) intervalos de tempo na semana para aulas;
• Todos os horários dos professores estão disponíveis;
• Alguns professores ministram disciplinas diferentes;
Para a geração do modelo matemático o diretor de escola desabilitou a
restrição que não permite aulas seguidas de um mesmo professor, ressaltamos que
os custos foram considerados, na implementação como unitários.
58
O ambiente foi instalado em um PC Pentium II 450 64 Mb e todos os
componentes da arquitetura foram hospedados e ativados para funcionar no mesmo
equipamento. Utilizamos os seguintes softwares neste estudo de caso:
Browser WEB : Internet Explorer 5.5;
Servidor WEB : Microsoft Personal Web Server – PWS;
Servidor de Banco de Dados : Interbase 6.0 da Borland;
Servidor de otimização : Software Lindo 6.0;
Considerando o porte do estudo de caso, o equipamento utilizado
possibilitou a execução do ambiente, com todas as opções, abrangendo a
configuração, geração e resolução do modelo.
5.2 Modelo linear inteiro gerado
A partir dos dados configurados e armazenados no banco de dados, o modelo
foi gerado , apresentando as seguintes características:
• 235(duzentos e trinta e cinco) variáveis;
• 236(duzentos e trinta e seis) restrições;
A função objetivo do modelo de programação linear inteira gerada pode ser
visualizada no apêndice B.
A geração do modelo ocorreu em tempo real ao clicar-se a opção do gerador,
sendo gravado um arquivo, com extensão .LTX, utilizada pelo LINDO para posterior
resolução do modelo.
O modelo matemático gerado é visualizado através de uma tela do ambiente,
ficando disponível para sua resolução através da opção do resolvedor.
59
5.3 Resultados
Conforme Apêndice C, a resolução através do LINDO apresentou uma
solução ótima e em tempo real(logo apos a ativação do botão de geração),
ressaltamos que o dado relativo ao tempo deve-se ao porte do modelo gerado.
Foram selecionados 25 variáveis o que corresponde as 25 aulas necessárias
semanalmente para a turma do 1
o
ano A, através de 42 iterações.
A figura 5.2, apresenta o comportamento da matriz resultado gerada pelo
software LINDO.
Figura 5.2: Comportamento da matriz de solução gerada pelo LINDO.
No apêndice C, apresentamos o arquivo gerado pelo ambiente com o
resultado gerado pelo LINDO, este arquivo é utilizado pelo módulo resolvedor para
carregar as variáveis selecionadas no banco de dados, no momento da carga das
60
tabelas de horários geradas para a turma A as indisponibilidades dos professores é
atualizada para que os mesmos possam ser utilizados nos demais horários não
alocados.
Os apêndices D e E, apresentam as consultas de tabela de horários geradas
por turma e a tabela de horários indisponíveis por professor gerados pelo ambiente,
respectivamente.
De acordo com o resultado apresentado não ocorreu conflito com relação a
horários de um mesmo professor e nem de professores diferentes na turma. As
cargas horárias de cada disciplina foram respeitadas, ocasionando o preenchimento
dos 25 intervalos de horários permitidos por semana.
5.4 Conclusão
Apresentamos um estudo de caso, para testar o funcionamento do ambiente
de construção de horário escolar na WEB. Conforme resultados apresentados o
ambiente suportou os testes com perfeição de funcionamento dos seus
componentes e apresentou uma solução satisfatória ao problema gerado através do
ambiente.
Os testes permitiram verificar alem da funcionalidade de cada componente, a
performance do ambiente, tendo em vista que apesar da sobrecarga no
equipamento, utilizado como multi-servidor, o problema foi resolvido com relativa
facilidade computacional.
A capacidade de visualizar o modelo gerado antes da resolução do mesmo
facilitou as correções necessárias ao ambiente, o que comprova a eficiência da
arquitetura de simulação utilizada por [Yen 97a]. Destacamos também a arquitetura
61
de um ambiente de otimização na INTERNET por [Cohen et Al 2001], que oferece
uma flexibilidade muito grande na correção de falhas em componentes específicos
do ambiente, sendo que cada problema é detectado mais facilmente e tratado de
forma isolada.
62
Capítulo 6
CONCLUSÕES E TRABALHOS FUTUROS
6.1 Conclusão
Apresentamos neste trabalho um ambiente de construção de tabela de
horário na Internet, para atender as 421 Escolas de Ensino Médio do Governo
Estadual. Para atingir os objetivos desta pesquisa, foi necessária a execução das
seguintes etapas:
• Definição de um modelo matemático que pudesse ser aplicado à
realidade das escolas de Ensino Médio do Governo Estadual;
• Implementação de um sistema utilizando técnicas de otimização que
permitisse gerar o modelo e encontrar uma solução viável em tempo
hábil, utilizando softwares comerciais;
• Disponibilizar em ambiente Internet para atender a todas as escolas
estaduais de ensino médio;
As principais contribuições consideradas com a conclusão desta pesquisa
são:
• Melhoria da qualidade dos serviços prestados ao cidadão;
• Otimização da utilização dos recursos gastos com os professores
estaduais;
• Facilidade e agilidade para os diretores de escolas construírem a tabela
de horários de suas escolas;
• Reutilização do ambiente desenvolvido na plataforma INTERNET em
outros problemas semelhantes de alocação no Serviço Público;
Destacamos para o bom resultado desta pesquisa os trabalhos realizados
pelos seguintes autores:
• Quanto à programação linear inteira para problemas de construção de
tabela de horário no trabalho de [Tripathyy 84];
63
• Quanto a arquitetura de uma ferramenta de otimização utilizando a
Internet, considerando a definição da infra-estrutura necessária segundo
os trabalhos de [Geoffrion & Krishnan 2001]; a divisão em camadas e a
arquitetura de dados segundo os trabalhos de [Cohen et Al 2001] e a
arquitetura de simulação baseada na INTERNET nos trabalhos de [Yen
97a].
6.2 Trabalhos Futuros
Como trabalhos futuros, pretende-se:
• Migrar todo o ambiente desenvolvido para a plataforma de Software
Livre, utilizando JAVA, possibilitando a implantação do mesmo em
organizações que não possam fazer investimentos em plataformas de
software proprietárias;
• Estudar a viabilidade de utilizar o ambiente em outros problemas do
serviço público estadual, que possam ser solucionados através de
otimização;
• Implantar o ambiente em todo o Estado, permitindo a possibilidade de
gerar e resolver modelos entre várias escolas de um mesmo CREDE;
• Implementar um sistema de otimização mais genérico, com várias
possibilidades de técnicas de solução e outros softwares resolvedores,
diferentes do LINDO.
64
REFERÊNCIAS BIBLIOGRÁFICAS
[Carter 86].M. W. Carter. A survey of practical applications of examination
timetabling algorithms. Operations Research, 34(2), 193-202, 1986 in Andrea
Schaerf. A survey of automated timetabling. Tech. Rep. CS-R9567, CWI, Amsterdam,
NL, 1995.
[Carter 89]. M.W. Carter. A Lagrangean Relaxation Approach to the Classroom
Assignment Problem, INFOR, 27, No. 2, 230-246 (1989).
[Cohen et Al 2001]. Cohen, Marc-david, Kelly, Charles B and Medaglia ,Andrés
L..2001, Decision Support with Internet-Enabled Software , Interfaces, Vol. 31, No. 2
(March-April), pp. xx-xx.
[Colorni, Dorigo & Maniezzo 92].Alberto Colorni, Marco Dorigo e Vittorio
Maniezzo. Metaheuristics for high school timetabling. Computational Optimization
and Applications. Vol 9, 1998, 275-298.
[Cooper & Kingston 93].T. B. Cooper, & J. H. Kingston. The solution of real
instances of the timetabling problem. The computer Journal, 36(7), 645-653, 1993 in
Andrea Schaerf. A survey of automated timetabling. Tech. Rep. CS-R9567, CWI,
Amsterdam, NL, 1995.
[Czyzyk et all 97].Czyzyk,J.;Owen,J.H.;and Wright,S.J.1997, ptimization on the
Internet, OR/MS Today,Vol.24,No.5(October),pp.48.Retrieved 18 October 2000 from
http://lionhrtpub.com/orms/orms-10-97/neos.html.
[De Werra 85]. D. de Werra. An introduction to timetabling. European Journal of
Operational Research, 19, (1985) 151-162.
65
[Dinkel 89]. Dinkel, J.J., Mote, J. and Venkataramanan, M. A. An Efficient
Decision Support System for Academic Course Scheduling. Operations Research,
Vol 37, No. 6 , 853-864 (1989).
[Dolk 2000]. Daniel R. Dolk. Integrated model management In the data
warehouse era. European Journal of Operational Research, 122, 199-218 (2000).
[Drexl & Salewski 97]. Andreas Drexl and Frank Salewski. Distribution
Requirements and compactness constraints in school timetabling. European Journal
of Operational Research 102, 1997 193-214.
[Duncan 93]. Tim Duncan. A review of commercially available constraint
programming tools. Technical Report AIAI-TR-149, Artificial Intelligence Applications
Institute, University of Edinburg, 1993.
[Even et al 76]. Even, S., Itai, A., & Shamir, A. On the complexity of timetabling
and multicommodity flow problems. SIAM Journal of Computation, 5 (4), 691-
703.(1976) in Andrea Schaerf. A survey of automated timetabling. Tech. Rep. CS-
R9567, CWI, Amsterdam, NL, 1995.
[Fang 94]. Hsiao-Lan Fang. Genetic Algorithms in Timetabling and Scheduling.
PHD Thesis, Department of Artificial Intelligence, University of Edinburg, 1994.
[Fourer & Goux 2001]. Fourer, Robert and Goux, Jean-Pierre 2001,
Optimization as an Internet resource, Interfaces, Vol. 31, No. 2 (March-April), pp. xx-
xx.
[Garey & Johnson 79]. Michael R. Garey and David S. Johnson. Computers and
Intractability: a Guide to the Theory of NP-completeness. Freeman, 1979.
[Geoffrion & Krishnan 2001]. Geoffrion, Arthur M. and Krishnan ,Ramayya 2001,
Prospects for Operations Research in the E-Business Era, Interfaces, Vol. 31, No. 2
(March-April), pp. xx-xx.
66
[Goltz 2000]. Hans-Joachim Goltz. On methods of constraints-basead
timetabling. Proceedings PACLP’2000. Manchester,april 2000 pp. 167-177.
[Junginger 86].W. Junginger. Timetabling in Germany – a survey. Interfaces, 16,
66-74,1986 in Andrea Schaerf. A survey of automated timetabling. Tech. Rep. CS-
R9567, CWI, Amsterdam, NL, 1995.
[Korman 79] S. M. Korman. Chapter 8: The graph-colouring problem. In N.
Christo_des, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization.
Wiely, Chichester, 1979. In Hsiao-Lan Fang. Genetic Algorithms in Timetabling and
Scheduling. PHD Thesis, Department of Artificial Intelligence, University of Edinburg,
1994
[Lawrie 69]. N.L. Lawrie. Na integer linear programming model of a school
timetabling problem. Computer Journal. 12:307-316.
[Mata 89]. Samuel Silva da Mata. O Problema do Horário na Escola de
Segundo Grau: Modelagem e Implementação, Tese de mestrado, Progr. de Eng. de
Sistemas e Computação, COPPE / UFRJ, Rio de Janeiro, 1989.
[Meisels et al 93]. Amnon Meisels, Jihad Ell-sana & Ehud Gudes. Comments on
CSP algoritms applied to timetabling. Technical report, Department of mathematics
and Computer Science, Israel, 1993 In Hsiao-Lan Fang. Genetic Algorithms in
Timetabling and Scheduling. PHD Thesis, Department of Artificial Intelligence,
University of Edinburg, 1994
[Neufeld, & Tartar 74] Neufeld, G. A., & Tartar, J. Graph coloring conditions for
the existence of solutions to the timetable problem. Communications of the ACM, 17
(8), 450 - 453. . (1974). in Andrea Schaerf. A survey of automated timetabling. Tech.
Rep. CS-R9567, CWI, Amsterdam, NL, 1995.
67
[Oliveira & Pinheiro 2001], J. A. Oliveira & P.R. PINHEIRO. Um Ambiente De
Apoio a Construção de Horário Escolar na Internet: Modelagem, implementação e
Aplicação nas Escolas de Ensino Médio , pp. 435 a 443. Anais do XXIII Simpósio
Brasileiro de Pesquisa Operacional, Campos do Jordão-SP, 2001.
[Ostermann, & de Werra 83] Ostermann, R., & de Werra, D. Some experiments
with a timetabling system. OR Spektrum, 3, 199 - 204. . (1983). ) in Andrea Schaerf.
A survey of automated timetabling. Tech. Rep. CS-R9567, CWI, Amsterdam, NL,
1995.
[Sabin & Winter 86]. G. C. W. Sabin & G. K. Winter. The impact of automated
timetabling on universities – a case study. Journal of the operational Research
Society, 37, 689-693, 1986 in Andrea Schaerf. A survey of automated timetabling.
Tech. Rep. CS-R9567, CWI, Amsterdam, NL, 1995.
[Schaerf 95]. Andrea Schaerf. A survey of automated timetabling. Tech. Rep.
CS-R9567, CWI, Amsterdam, NL, 1995. Available at
http://www.cwi.nl/ftp/CWIreports/AP.
[Schmidt & Strohlein 80]. G. Schmidt, T. Strohlein. Timetable Construction an
annotated Bibliography. The Computer Journal, vol.23,no. 4, pp. 307-315,(1980) in
Samuel Silva da Mata. O Problema do Horário na Escola de Segundo Grau:
Modelagem e Implementação, Tese de mestrado, Progr. de Eng. de Sistemas e
Computação, COPPE / UFRJ, Rio de Janeiro, 1989.
[Selim 83]. Selim, S. M. An Algorithm for Producing Course and Lecture
Timetables. Computers and Education, 7/2, 101-108 (1983).
[Sodhi 2001]. Sodhi, Mohan 2001, Applications and opportunities for OR/MS in
Internet-enabled supply chains and electronic marketplaces, Interfaces, Vol. 31, No.
2 (March-April), pp. xx-xx.
[Souza, Maculan e Ochi 2000]. M.J.F. Souza, N. Maculan e L.S. Ochi. Uma
heuristica para o problema do horário de escolas. Proceedings do XXIII CNMAC,
2000.
68
[Tripathy 84]. Arabinda Tripathy. School timetabling – a case in large binary
integer linear programming. Management Science. Vol. 30. No. 12, 1984.
[Tripathy 92]. Arabinda Tripathy. Computerised decision aid for timetabling – A
case analysis. Discrete Applied Mathematics, 35(3),313-323,1992.
[Yen 97a]. Benjamim Ping-Chang Yen. Internet-based simulation tools.
Proceedings of the 3
rd
International Symposium on logistic, padua, italy, july 9-11,
1997.
[Yen 97b]. Benjamim Ping-Chang Yen. Design and Developerment Scheduling
system on the Internet. Proceedings of the Industrial Engineering and Engineering
management, August 18-22, 1997.
[Yoshikawa et al 94]. M. Yoshikawa, K. Kaneko, Y. Nomura & M. Watanabe. A
constraint-based approach to high-school timetabling problems: a case study. In
proc. Of the 12
th
Nat. Conf. On IA, 1111-1116, 1994.
69
Apêndice A
DADOS DO PROFESSORES COM DISCIPLINAS
LECIONADAS (Dados Fictícios)
70
Apêndice B
EXEMPLO DA FUNÇÃO OBJETIVO DO MODELO GERADO
PELO AMBIENTE
MAX X0104011 + X0104021 + X0104041 + X0104051 + X0104071 + X0104081 + X0104091 + X0104101 +
X0104111 + X0104121 + X0104131 + X0104141 + X0104161 + X0104171 + X0104181 + X0104191 + X0104201 +
X0104211 + X0104221 + X0104231 + X0104241 + X0104251 + X0302011 + X0302021 + X0302041 + X0302051 +
X0302061 + X0302071 + X0302091 + X0302111 + X0302131 + X0302141 + X0302151 + X0302161 + X0302171 +
X0302201 + X0302221 + X0302231 + X0302241 + X0302251 + X0306011 + X0306021 + X0306041 + X0306051 +
X0306061 + X0306071 + X0306091 + X0306111 + X0306131 + X0306141 + X0306151 + X0306161 + X0306171 +
X0306201 + X0306221 + X0306231 + X0306241 + X0306251 + X0309011 + X0309021 + X0309041 + X0309051 +
X0309061 + X0309071 + X0309091 + X0309111 + X0309131 + X0309141 + X0309151 + X0309161 + X0309171 +
X0309201 + X0309221 + X0309231 + X0309241 + X0309251 + X0407011 + X0407021 + X0407031 + X0407041 +
X0407051 + X0407061 + X0407071 + X0407081 + X0407091 + X0407101 + X0407111 + X0407121 + X0407131 +
X0407151 + X0407161 + X0407171 + X0407181 + X0407191 + X0407201 + X0407211 + X0407231 + X0407241 +
X0407251 + X0710011 + X0710021 + X0710031 + X0710041 + X0710051 + X0710061 + X0710081 + X0710091 +
X0710101 + X0710111 + X0710121 + X0710131 + X0710141 + X0710151 + X0710161 + X0710171 + X0710181 +
X0710191 + X0710201 + X0710211 + X0710221 + X0710231 + X0710251 + X0811031 + X0811041 + X0811051 +
X0811061 + X0811071 + X0811081 + X0811091 + X0811101 + X0811111 + X0811121 + X0811131 + X0811141 +
X0811151 + X0811161 + X0811171 + X0811181 + X0811191 + X0811201 + X0811211 + X0811221 + X0811231 +
X0811241 + X0811251 + X0903011 + X0903021 + X0903031 + X0903041 + X0903051 + X0903061 + X0903071 +
X0903081 + X0903091 + X0903101 + X0903121 + X0903131 + X0903141 + X0903151 + X0903161 + X0903171 +
X0903181 + X0903191 + X0903211 + X0903221 + X0903231 + X0903241 + X0903251 + X1005011 + X1005021 +
X1005031 + X1005051 + X1005061 + X1005071 + X1005081 + X1005091 + X1005101 + X1005111 + X1005121 +
X1005141 + X1005151 + X1005161 + X1005171 + X1005181 + X1005191 + X1005201 + X1005211 + X1005221 +
X1005231 + X1005241 + X1005251 + X1208011 + X1208021 + X1208031 + X1208041 + X1208061 + X1208071 +
X1208081 + X1208091 + X1208101 + X1208111 + X1208121 + X1208131 + X1208141 + X1208151 + X1208161 +
X1208171 + X1208181 + X1208191 + X1208201 + X1208211 + X1208221 + X1208241 + X1208251 + X1301011 +
X1301021 + X1301031 + X1301041 + X1301051 + X1301061 + X1301071 + X1301081 + X1301101 + X1301111 +
X1301121 + X1301131 + X1301141 + X1301151 + X1301181 + X1301191 + X1301201 + X1301211 + X1301221 +
X1301231 + X1301241
71
Apêndice C
RESOLUÇÃO DO MODELO GERADO ATRAVÉS DO
SOFTWARE LINDO
NO. ITERATIONS= 42
OBJECTIVE FUNCTION VALUE
1) 25.00000
VARIABLE VALUE REDUCED COST
X0104011 1.000000 0.000000
X0104251 1.000000 0.000000
X0302041 1.000000 0.000000
X0302111 1.000000 0.000000
X0302151 1.000000 0.000000
X0302231 1.000000 0.000000
X0306201 1.000000 0.000000
X0309091 1.000000 0.000000
X0309161 1.000000 0.000000
X0407021 1.000000 0.000000
X0407101 1.000000 0.000000
X0710121 1.000000 0.000000
X0710181 1.000000 0.000000
X0811061 1.000000 0.000000
X0811221 1.000000 0.000000
X0903031 1.000000 0.000000
X0903171 1.000000 0.000000
X1005071 1.000000 0.000000
X1005211 1.000000 0.000000
X1208081 1.000000 0.000000
X1208131 1.000000 0.000000
X1301051 1.000000 0.000000
X1301141 1.000000 0.000000
X1301191 1.000000 0.000000
X1301241 1.000000 0.000000
72
Apêndice D
RESULTADO DA RESOLUÇÃO DO MODELO GERADO
PELO AMBIENTE (Dados Fictícios)
73
Apêndice E
RESULTADO DA CONSULTA DE INDISPONIBILIDADES
APÓS RESOLUÇÃO DO MODELO (Dados Fictícios)
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
