Trabalho de Formatura - MAC499
Marcio Fumihiko Suenaga
http://www.linux.ime.usp.br/~tico
Projeto: Escala de Caravana Assistencial
http://www.linux.ime.usp.br/~tico/mac499
Orientador: Prof. Alfredo Goldman
Objetivos
●
●
Estudar os tipos de algoritmos de escala.
Selecionar o que melhor algoritmo que soluciona
o problema
●
Projetar um programa de escala.
●
Se formar!
O que é um problema de
escalonamento?
Como solucionar um problema de
escalonamento?
Exemplo: fila de banco
●
●
●
Antes: uma fila para cada caixa
Problema: nem sempre é justo
para quem chegou antes.
Solução: fila única.
ABEUNI
Aliança Beneficente Universitária
●
22 anos de trabalho voluntário
●
Universitários de qualquer área.
●
44 caravanas
●
Outros trabalhos beneficentes
●
Aproximadamente 300
voluntários ativos
www.abeuni.org.br
A caravana da ABEUNI
●
12 Departamentos
●
9 dias de evento
●
6 dias de atendimento
●
~300 voluntários
●
~50 novos voluntários
Problema: Escala de Calouros
●
Aproximadamente 50 calouros
●
12 departamentos
●
6 dias com 2 turnos por dia
●
12x6x2 = 600 pontos de escala
●
Eliminar o atual preenchimento
manual extremamente cansativo
após alguns dias de evento.
Agoritmos Conhecidos
Estudados em MAC5758
Introdução ao Escalonamento e
Aplicações
●
TABU
●
Contraint Programming
●
Genético
●
Ant-colony
Por que Programação por restrição?
●
Solução rápida
●
Simples
●
Pouco processamento
●
Solução não ideal mas boa.
Constraint Programming
restrição
Constraint Programming
Constraint Programming
Constraint Programming
Constraint Programming
Constraint Programming
Constraint Programming
Constraint Programming
with backtracking
Próximo passo
buscar outra tentativa
que chegue a uma solução
melhor
Constraint Programming
with backtracking
Constraint Programming
with backtracking
Constraint Programming
with backtracking
Restrição com pontuação
3
2
2
Restrição com pontuação
2
3
2
Restrição com pontuação
1
2
Restrição com pontuação
3
Restrição com pontuação
1
As restrições do problema
Restrições de alta prioridade
R1 - Calouros da área podem ser requisitado para o departamento
específico.
R2 – Deve-se aceitar mudanças e escolhas do operador.
R3 - O primeiro turno pode não ter atendimento em alguns
departamentos por falta de população a ser atendida então estes
departamentos poderão ser repetidos sem ser considerado uma repetição.
R4 - Alguns departamentos pedem um número de homens mínimo dentre
os calouros pedidos.
Restrições de baixa prioridade
B1 - Quando acontecer uma repetição, é melhor que a repetição não seja
consecutiva. De preferência o mais distante possível.
B2 - É bom empurrar as repetições para o fim do evento
O programa