Alocação de Salas
Via Simulated Annealing
Daniela Leal de Barcelos
Elayne Ferreira de Souza
Simulated Annealing
 Proposto
por Kirkpatrick et al. (1983)
 Simula
o processo de recozimento de
materiais
 Admite
soluções de piora para escapar de
ótimos locais
 Técnica
de pesquisa local
Sobre o problema:
O problema de alocação de salas (PAS) diz
respeito à distribuição de aulas, com horários
previamente estabelecidos, a salas,
respeitando-se um conjunto de restrições de
várias naturezas (Schaefer 1999).
Descrição do problema em
questão

Problema fictício com os seguintes atributos:
 Número de salas - 8
 sendo 7 reais e uma virtual
de horários – 90
17 horários de segunda a sexta-feira e 5
horários aos sábados
Número

Descrição do problema em
questão

Capacidade das Salas
Sala
virtual
Capac
0
1
2
3
4
5
6
7
70 60 44 55 44 60 70
Descrição do problema em
questão
Número
de aulas - 75
 sendo 7 reais e uma virtual.
 Cada aula tem como características:
• Sigla que representa o departamento
do qual faz parte;
• Código da disciplina;
• Código da turma matriculada;
Descrição do problema em
questão
•
•
•
•
•
Indicador se a aula é teórica ou
prática;
Dias em que é disponibilizada;
Horário de início e fim;
Demanda da turma;
Semanalmente, o número de aulas
de uma certa disciplina é de no
máximo 6 horários.
Descrição do problema em
questão

Restrições
Uma sala não pode ser alocada para uma
turma maior que sua capacidade;
Uma aula deve ser dada em, no máximo, 3
dias durante a semana;
Descrição do problema em
questão
Uma turma não pode ocupar mais de uma
sala em um mesmo intervalo de horários;
 Evitar a ociosidade de carteiras em uma
sala;
 Uma mesma sala não pode ser ocupada
por mais de uma turma ao mesmo tempo.

Modelagem do problema

Representação
 A soluções inicial e final do problema são
representadas por matrizes com 91 linhas
e 8 colunas, onde as linhas representam os
horários disponíveis e as colunas
representam as salas. São definidas,
respectivamente como:
 tabelaS0;
 tabelaSstar.
Vizinhança

É considerada um vizinho da solução corrente,
a solução criada através dos movimentos de
troca e alocação, onde:
Troca corresponde a inserção de um
determinado elemento em uma posição
vazia.
 Alocação corresponde a trocar a(s) sala(s)
de uma turma por outra sala vazia no
mesmo horário.
Função objetivo

A função objetivo consiste no valor das
penalidades referentes a não cumprimento de
um requisito.
É considerado essencial o fato de uma sala
não poder ter sobrecarga de alunos. Caso
isso ocorra, é gerada uma inviabilidade na
solução.
Função objetivo
Outra penalidade que pode ser calculada
é o fato de haver ociosidade de carteiras.
Neste caso, o valor adicional à função
objetiva será 1 e inviabilidades não serão
geradas.

Função objetivo

O cálculo da função objetivo é representado
através do somatório de todas as penalidades
sofridas.
Sendo pexcesso a penalidade por excesso
e pociosidade, a penalidade por
ociosidade, temos:
int fo = ∑(pexcesso + pocisidade)
Solução inicial

São escolhidos, aleatoriamente, uma sala e um
horário. Caso neste instante esta sala já esteja
ocupada, uma nova escolha aleatória é
efetuada;

É usada neste caso uma semente igual a 1000.
Solução final

É gerada utilizando o método de Simulated
Annealing com os seguintes parâmetros:
Número
Máximo de iterações em uma
dada temperatura – 500;
Inicial – obtida através de
uma função auto-adaptativa;
Temperatura
Coeficiente
de resfriamento – 0,99;
Solução final
O
valor final da função objetivo é
representada pelo menor valor das fo’s de
todas as soluções encontradas.
Resultados Computacionais
Função Objetivo/Tempo
700000
619838
Função Objetivo
600000
500000
400000
300000
200000
100000
23242
0
0
2
2,18 2,49
4
4,08 4,12
Tempo
6
6,09
8
10
12
Conclusão

Os resultados obtidos com a utilização do
método Simulated Annealing foram
satisfatórios. Porém, poderia ser interessante
refinar a solução final deste problema utilizando
uma outra metaheurística. Essa etapa ajustaria
ainda mais as aulas às salas disponíveis.