Sistema de geração de horários otimizados:
“SESSA”
Sistema
de Geração de Horários Otimizados
Abordagem de Pesquisa Operacional: Programação Inteira
da UnC – Campus Canoinhas: “SESSA”
XI SPPGMNE
Um estudo de caso sob a perspectiva da
designação e sua solução por meio da
Programação Inteira com variáveis binárias
Engº Alexandre Manoel dos Santos, M.Sc.
Universidade Federal da Fronteira Sul - UFFS
Campus de Laranjeiras do Sul/PR
Professor nos cursos de Engenharia de Aqüicultura e Engenharia de Alimentos
[email protected]
[email protected]
Prof. Dr. Sérgio Scheer
Prof. Dr. Paulo Henrique Siqueira
Universidade Federal do Paraná - UFPR
Programa de Pós-Graduação em Métodos Numéricos em Engenharia
Centro de Estudos em Engenharia Civil - CESEC
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [1]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Tópicos:
XI SPPGMNE
Contexto;
Motivações e Objetivos;
Implementação do sistema “SESSA”;
Abordagem utilizada na solução do problema;
Estudo de Caso: semestre 2006_2;
Considerações Finais.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [2]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Contexto:
XI SPPGMNE
A geração automática de horários da UnC - Canoinhas é
um problema de Engenharia (Área da “PO” e de “MNE”);
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [3]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motivações:
XI SPPGMNE
Máximo aproveitamento dos professores :
abordagem sistêmica: definição de “grau” de aproveitamento;
busca pela automatização do processo: algumas soluções não são
manualmente exeqüíveis nem controláveis;
condições para análises quantitativa e qualitativa do processo;
desenvolvimento de ‘know-how’ dentro da UnC – Canoinhas;
Percepção e Sensibilidade :
o problema sob uma perspectiva global e local;
alterações localizadas aumentam a eficiência da solução ?
uma ferramenta para apoiar a busca por uma solução;
a UnC buscando solução para seus problemas ...
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [4]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Um problema de Engenharia:
XI SPPGMNE
Trata-se de uma tarefa complexa: a alocação dos professores
(com suas respectivas disciplinas) nos períodos dos cursos ofertados,
em locais diferentes, levando em consideração as disponibilidades de
tempo dos professores e a atual dimensão da UnC:
Professores:
260
Disciplinas:
648
Semestre 2006/2
Turmas:
122
Locais:
4
Alocações:
1025
Em Engenharia, “Problema” não é sinônimo de “Encrenca”:
Uma pergunta cuja resposta não está disponível;
Uma pergunta cuja resposta disponível não satisfaz um conjunto de exigências ...
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [5]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Objetivos:
XI SPPGMNE
desenvolver um sistema computacional para a
geração de horários otimizados da UnC - Canoinhas;
realizar ensaios de uso do sistema como
ferramenta de apoio para a definição final do horário;
maximizar o aproveitamento dos professores na
geração dos horários da UnC;
comprovar a eficiência do aproveitamento dos
professores no horário gerado.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [6]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Sistema “SESSA”:
XI SPPGMNE
Conjunto de ferramentas e mecanismos
computacionais que facilitam a atividade de geração
do horário otimizado para um dado semestre da
UnC – Canoinhas:
Dados: Professores, disciplinas, turmas e cursos, locais;
Disponibilidades dos professores;
Interfaces gráficas adequadas e interativas;
Alocações otimizadas;
Horários otimizados: dos professores e das turmas;
“SESSA” : homenagem ao hindú que inventou o jogo de xadrez.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [7]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
A estrutura de dados:
XI SPPGMNE
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [8]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Sistema “SESSA”:
XI SPPGMNE
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [9]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Abordagem utilizada na solução:
Arquitetura de esquema triplo:
XI SPPGMNE
1ª Camada
2ª Camada
3ª Camada
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [10]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 1ª Camada:
XI SPPGMNE
Modelagem do problema de alocação :
ciclo da solução: a cada semestre seis processos são executados;
horários como destinos num sistema de transporte - um problema
de designação: programação inteira com variáveis binárias;
cardinalidade de cada conjunto de elementos do modelo
função objetivo: maximizar o aproveitamento dos professores;
as restrições do modelo.
Montagem automatizada das equações :
estabelecimento de uma nomenclatura adequada;
as interfaces do sistema montador;
o arquivo texto exportado para a 2ª camada;
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [11]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Processos que definem o contexto:
XI SPPGMNE
Os processos abaixo ocorrem sempre antes de um
novo semestre letivo:
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [12]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Os horários para a alocação:
XI SPPGMNE
Horários semanais para cada uma das 122 Turmas:
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [13]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Os elementos do modelo:
XI SPPGMNE
Cada alocação representa dois créditos de uma disciplina
pertencente a uma dada turma, a ser lecionada por um
professor em um determinado local de funcionamento,
em um dos 36 horários de destino:
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [14]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
XI SPPGMNE
A função objetivo:
Maximizar a alocação de 262 professores que devem
ministrar 648 disciplinas, pertencentes a 122 turmas distintas,
provenientes de 31 cursos em 4 locais diferentes:
T
Max
L
P
D
C
H

t 1 l 1 p 1 d 1 c 1 h1
(a p  bd )  X tlpdch
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [15]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
As restrições do modelo:
XI SPPGMNE
Cada disciplina deve ser alocada uma única vez ou não deve ser alocada;
Todos os créditos de uma disciplina são alocados ou nenhum deles é alocado;
Numa mesma Turma, alocações distintas não podem ocupar o mesmo horário;
Um professor somente pode estar uma única vez em um mesmo horário;
Um professor não pode se deslocar entre locais diferentes num mesmo turno;
Todas as variáveis do modelo assumem valores binários.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [16]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
XI SPPGMNE
Restrição sobre Disciplinas:
Cada disciplina deve ser alocada uma única vez ou não
deve ser alocada :



onde
H
 X
h1
tlpdch



 Xvirt
tlpdc
 1

 tlpdc  alocações de dois créditos  1,2,3,...,1025

 H  horários especifica dos em cada alocação  1,2,3...,36

XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [17]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
XI SPPGMNE
Restrição sobre Créditos:
Todos os créditos de uma disciplina são alocados ou
nenhum deles é alocado:
Xvirt
tlpd ( c 1)
onde

Xvirt
tlpd ( c 2 )

Xvirt
tlpd ( c 3)

Xvirt
tlpd ( c 4 )

 tlpd  alocações de mesma disciplina  1,2,3,...,648

 c  conjunto de créditos de cada disciplina  1,2,3,4

XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [18]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Restrição sobre Alocações:
XI SPPGMNE
Numa mesma Turma, alocações distintas não podem
ocupar o mesmo horário :



onde
D
C
 X
d 1
c 1
tlpdch



 Xvirt _ turma
tlpdch
 1

 tlpdc  alocações de mesma turma  1,2,3,...,122

 h  horários possíveis em cada turma  1,2,3,...,36

XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [19]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Restrição sobre Professores:
XI SPPGMNE
Um professor somente pode estar uma única vez em um
mesmo horário:



onde
T
 X
t 1
tlpdch



 Xvirt _ professor
tlpdch
 1


 tlpdc  alocações para cada professor  1,2,3,...,n

 h  horários possíveis em todas as turmas  1,2,3,...,36


 1,2,3,...,262
 p  professores
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [20]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Restrição sobre Professores:
XI SPPGMNE
Um professor não pode se deslocar entre locais diferentes
num mesmo turno :
onde
L



 X tlpdch
  Xvirt _ local tlpdch  1

X
tlpdc( h 1)
l 1



 tlpdc (h 1)  alocações nos segundos horários  1,2,3,...,n

 tlpdch 
alocações nos primeiros horários  1,2,3,..., m


 h  primeiros horários em cada turno  1,3,5,7,...,35


p  cada um dos professores  1,2,3,...,262


XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [21]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
XI SPPGMNE
Restrição sobre as Variáveis:
Todas as variáveis do modelo assumem valores binários:
X
tlpdch
 (0  1)
Xvirt _ turma
onde tlpdc1, 2 , 3,...,1025 e h 1, 2 , 3,...36
tlpdch
 (0  1)
Xvirt _ professor
Xvirt _ local
tlpdch
tlpdch
onde tlpdc1, 2 , 3,...,122 e h 1, 2 , 3,...36
 (0  1)
 (0  1)
onde tlpdc1, 2 , 3,...,n e h 1, 2 , 3,...36 e p 1, 2 ,...262
onde tlpdch1, 3, 5, 7 , 9 ,...,35
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [22]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Montagem automatizada das equações:
XI SPPGMNE
Estabelecimento de uma nomenclatura adequada ao
processo de montagem e verificação da validade do modelo:
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [23]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Interface do sistema montador:
XI SPPGMNE
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [24]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 2ª Camada:
XI SPPGMNE
Interface principal: Motor XPress-MP;
Arquivo texto representando a solução do
sistema de equações gerado.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [25]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 2ª Camada:
XI SPPGMNE
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [26]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 3ª Camada:
XI SPPGMNE
Interface do subsistema de visualização dos
resultados;
Cálculo da eficiência do processo de alocação
dos professores.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [27]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 3ª Camada: visualização
XI SPPGMNE
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [28]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Motor na 3ª Camada: eficiência
XI SPPGMNE
 ntp  pna 
EAP %  
* 100

ntp


onde:
 ntp:
número total de professores envolvidos no processo de
alocação;
 pna:
número de professores não alocados;
 EAP: eficiência do processo de aproveitamento dos
professores
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [29]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Estudo de caso: Semestre 2006/2
XI SPPGMNE
Aspectos funcionais;
Caracterização do ensaio “Semestre 2006/2”:
Arquivo para o processador:
Variáveis utilizadas:
Número de equações:
61.866 linhas;
14.040 variáveis;
7.330 equações;
Para descrever:
1025 alocações de 262 professores com 648 disciplinas,
distribuídas em 122 turmas em 4 locais diferentes;
Resultando em 32 alocações não realizadas (16 disciplinas sem
professor): por falta de disponibilidade do professor!
Com 96,87% de eficiência
:= [ ( (1025-32)/1025 )*100 ]
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [30]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Aspectos funcionais:
XI SPPGMNE
Input do sistema (afetam a eficácia do SESSA):
Professores: pontos, disciplinas e disponibilidades;
Cursos e Turmas: horários ofertados;
Disciplinas e créditos;
Locais de funcionamento dos cursos e turmas
Por que não funcionou no semestre passado?
...erros...
Aspectos fundamentais (afetam a eficiência do SESSA):
Professores que vem de fora da cidade;
Disciplinas em regime rotativo (fora do horário);
Especificidades de cada turma/professor/disciplina;
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [31]
Sistema de geração de horários otimizados:
“SESSA”
Abordagem de Pesquisa Operacional: Programação Inteira
Considerações finais
XI SPPGMNE
O sistema “SESSA”:
É eficaz;
Possui eficiência comprovável;
Encontra-se em fase de testes: (user´s point of view);
Encontra-se em fase de refinamentos, durante o uso;
Possui aceitabilidade e aceitação comprovada.
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [32]
Sistema de geração de horários otimizados:
“SESSA”
Sistema
de Geração de Horários Otimizados
Abordagem de Pesquisa Operacional: Programação Inteira
da UnC – Campus Canoinhas: “SESSA”
XI SPPGMNE
Um estudo de caso sob a perspectiva da
designação e sua solução por meio da
Programação Inteira com variáveis binárias
Engº Alexandre Manoel dos Santos, M.Sc.
Universidade Federal da Fronteira Sul - UFFS
Campus de Laranjeiras do Sul/PR
Professor nos cursos de Engenharia de Aqüicultura e Engenharia de Alimentos
[email protected]
[email protected]
FIM
XI SPPGMNE – Semana do PPGMNE /UFPR - Métodos Numéricos em Engenharia - [33]