INTELIGÊNCIA COMPUTACIONAL
PARA OTIMIZAÇÃO
• O Problema de Sequenciamento
em Processadores Paralelos
O PROBLEMA
• Técnica utilizada;
• Modelagem;
MODELAGEM
• Leitura dos dados;
• Montagem do modelo de solução;
• Submissão da solução a uma heurística
VND
ALGORITMO
• Solução inicial usando 3-FASES;
• Refinamento usando VND;
3-FASES
• Fase 1-Alocação inicial
- Dividir o intervalo [pmim, pmax] em r intervalos
aproximadamente iguais;
- Os intervalos são mais úteis nas fases 2 e 3;
- Dividir as tarefas entre os processadores seguindo
um critério;
3-FASES
• Fase 2-Balanceamento
- Melhora a solução encontrada pela FASE 1;
- Troca tarefas do processador mais carregado para
o menos carregado;
- A escolha da tarefa a ser trocada é
orientada pelo tempo médio de finalização;
3-FASES
• Fase 3-Duplas Trocas
- Incorporar novas soluções ao espaço de busca;
- Melhor troca envolvendo uma tarefa do
processador mais carregado e uma de outro
processador;
- Volta para a FASE 2;
- A escolha das tarefas a serem trocadas é
orientada pela diferença dos tempos de
processamento entre elas;
3-FASES
• Escolha do Parâmetro r
Valores Recomendados de r
n/m
(1,10)
[10,50)
[50,100)
[100,200)
[200,100)
r*
2
5
10
15
20
VND
Refinar a solução;
Vizinhanças;
N(1)(s)
N(2)(s)
VND
procedimento VND
1. Seja s0 uma solução inicial e r o número de estruturas
diferentes de vizinhança;
2. s  s0; {Solução corrente}
3. k  1; {Tipo de estrutura de vizinhança}
4. enquanto (k  r) faça
5.
Encontre o melhor vizinho s’  N (k) (s);
6.
se f(s’) < f(s)
7.
então s  s’;
k  1;
8.
senão k  k + 1;
9.
fim-se ;
10. fim-enquanto ;
11. Retorne s;
fim VND;
FUNÇÃO OBJETIVO
• fo = max {Ci} ,
0 ≤ i < m;
CONCLUSÃO
• Tempo exponencial
• Heurísticas
BIBLIOGRAFIA
• Tese de Doutorado. Algoritmos Heurísticos
e Exatos para Resolução do Problema de
Sequenciamento em Processadores
Paralelos. Felipe Martins Müller.
• Notas de aula de Inteligência
Computacional. Prof° Marcone Jamilson
Freitas Souza. Acesso em 20/11/2003.
COMPONENTE
Daniel Magalhães Nobre