Projeto de um Algoritmo
Genético Híbrido para
Planejamento Operacional de
Curto Prazo de Minerações a
Céu Aberto
Robert Fabricio Subtil
Roteiro








Introdução
Problema de escalonamento de tarefas
Algoritmos genéticos
Processos de lavra
Planejamento operacional de curto prazo
Modelo proposto de algoritmo genético híbrido
Resultados
Trabalhos futuros
Introdução

Modelos de otimização têm sido adotados
com maior frequência no setor
empresarial
 Diminuindo
custos
 Aumentando lucros e a competitividade no
mercado global
Problema de escalonamento de
tarefas
Envolvem alocação de recursos no tempo
 São classificados como NP-Difícil

Problema de escalonamento de
tarefas

Modelo clássico:
 Existe
um conjunto de máquinas disponíveis e um
conjunto de tarefas a serem executadas
Onde:
 As tarefas devem ser executadas numa sequência
conhecida de uma ou mais operações
 Uma operação é definida pelo seu tempo de
processamento e pela máquina que a executa
 Cada máquina executa uma operação por vez
Objetivo : determinar uma sequência de alocação para
todas as máquinas, minimizando custos
Problema de escalonamento de
tarefas
Geralmente envolve muitas restrições
 Métodos propostos

 Modelos
exatos
 Métodos de aproximação
 Buscas Locais e Meta-heurísticas

Algoritmos genéticos têm sido muito
utilizados na resolução deste tipo de
problema
Algoritmos Genéticos
São baseados na idéia de evolução
natural proposta por Charles Darwin,
aliadas às idéias sobre genética proposta
por Mendel
 São capazes de encontrar soluções de
qualidade em tempo razoável

Algoritmos genéticos:
Funcionamento
Processos de lavra
O fluxo operacional inicia-se com a
especificação do cliente
 Planejamentos

 Longo
Prazo
 Médio Prazo
 Curto Prazo
Processos de lavra:
Operações de lavra e transporte
Planejamento Operacional de
Curto Prazo : Processo atual
Processo atual

Possíveis problemas
 não
cumprimento da meta de qualidade no decorrer
do plano, especialmente nos turnos finais
 ociosidade e sobrecarga de equipamentos
 não uniformidade da produção
 deslocamentos desnecessários das máquinas
 incompatibilidade da produção com a frota de
caminhões
Dados de uma área
Proposta
Proposta de Slots

Equipamentos podem deslocar-se a qualquer
instante pelas entidades da mina
Proposta do algoritmo genético
híbrido









Representação da solução
Geração da população inicial
Avaliação dos indivíduos
Seleção
Cruzamento
Mutação
Elitismo
Verificação do critério de sobrevivência
Critério de parada
Representação da solução
Indivíduo
População
Geração da população inicial

Distribuição das áreas nos turnos do plano
 Fechamento
da qualidade e produção por turno
 Respeitar quantidade de massas por área
 Respeitar a quantidade de áreas por turno
 Respeitar capacidade de produção dos
equipamentos de carga

Alocação das máquinas nas frentes de lavra
Distribuição das áreas nos turnos
Alocação das máquinas nas
frentes de lavra
Avaliação dos indivíduos: Produção
e deslocamentos
Avaliação dos indivíduos:
Aderência de carga X transporte
Seleção

Torneio
 Seleciona
os mais aptos considerando as
prioridades de minimização dos custos
Cruzamento


Manter as distribuições das áreas encontradas na
geração inicial
Modelo do problema de cobertura de conjuntos
Cruzamento
Mutação
É feita entre dois pontos que devem
representar o intervalo entre dois turnos
 Executa-se o modelo matemático
proposto na geração da população inicial
 Refaz a alocação das máquinas nos
turnos envolvidos

Elitismo

Insere na próxima geração, sempre o
melhor indivíduo encontrado
Verificação do critério de
sobrevivência
Sempre substituir os ancestrais
 Substituir os ancestrais quando a média
dos descendentes for maior ou igual a
média dos ancestrais

Critério de parada

Número de gerações
Resultados: Dados das Áreas
Resultados: Dados das máquinas
Resultados: Turnos
Resultados: Plano
Trabalhos futuros
Otimização dinâmica da programação de
produção
 Limites de máquinas nas áreas
 Incluir remoção de estéril

Dúvidas ?
Comentários?
Agradecimentos.