Programação de Horário em Escolas
André Luiz G. dos Santos 00.2.4990
Caio Yuji Yoneyama 99.1.4033
Francys Wilhan Werner 00.2.4991
Descrição do problema

O problema de programação de
horários em escolas tem como objetivo
a alocação das aulas de uma escola a
um determinado conjunto de horários,
satisfazendo algumas restrições.
Descrição do problema


Solução manual difícil, demorada e o
resultado pode ser insatisfatório
Problema NP-difícil
Características do problema

Dados


Fictícios
Restrições


Essenciais
Não essenciais
Restrições essenciais


Uma turma não pode ter aula com
mais de um professor ao mesmo
tempo;
Um professor não pode dar mais do
que duas aulas seguidas para a
mesma turma da mesma matéria;
Restrições não essenciais

Minimizar o número de dias que um
professor vai à escola;
Estrutura de vizinhança
Dada uma solução s, sua vizinhança
N(s) é constituída por um solução s’
que é obtida de s a partir de um
movimento que consiste na simples
troca de duas atividades (aulas)
distintas de um mesmo turno
Estrutura de vizinhança
Solução s
Estrutura de vizinhança
Solução s’
Função Objetivo
A função objetivo é baseada nas sobreposições, no
excesso de aulas dia e no número de dias a mais
que o professor vai a escola :



fo do professor = (nº de vezes que o prof. vai a escola) –
(nº de vezes que o prof. deveria ir a escola)
fo = (fo de cada professor) * f1+ (nº de sobreposições)*
f2 + (nº de excesso aula dia)* f3
Técnicas utilizadas

Simulated Annealing
Fase de construção

Um quadro de horários é construído
de forma aleatória
Simulated Annealing

Procedimento de otimização local que
admite soluções de piora para escapar
de ótimos locais

Critério de parada: temperatura atual
inferior a temperatura final
Simulated Annealing
Resultados
Parâmetros utilizados:




Para a sobreposição: 40
Para o excesso de aulas dia: 25
Para o excesso de vezes: 7
Solução inicial:


fo = 5405 (131 sobreposições e 1 excessos aulas dia e
vezes 20)
Solução final:



fomin = 84 (nenhuma sobreposição, nenhuma excessos
aula dia e 12 excesso vezes)
nº de iterações = 577500