HIBRIDIZAÇÃO DE MÉTODOS EXATOS E HEURÍSTICOS PARA RESOLUÇÃO DE PROBLEMAS DE OTIMIZAÇÃO COMBINA / HYBRIDIZATION OF EXACT AND HEURISTIC METHODS TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEM

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

04/03/2011

RESUMO

A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

ASSUNTO(S)

vizinhança de grande porte problema de programação máquinas paralelas não relacionadas problema das p-medianas capacitado metaheurísticas híbridas ciencia da computacao capacitated p-median problem hybrid metaheuristics unrelated parallel machine scheduling problem large-scale neighborhood

Documentos Relacionados