AN EXPERIMENTAL INVESTIGATION OF PROBABILITY DISTRIBUTION OF SOLUTION TIME IN GRASP AND ITS APPLICATION ON THE ANALYSIS OF PARALLEL IMPLEMENTATIONS / UMA INVESTIGAÇÃO EXPERIMENTAL DA DISTRIBUIÇÃO DE PROBABILIDADE DO TEMPO DE SOLUCAO EM HEURISTICAS GRASP E SUA APLICAÇÃO NA ANALISE DE IMPLEMENTAÇÕES PARALELAS

AUTOR(ES)
DATA DE PUBLICAÇÃO

2002

RESUMO

GRASP (Greedy Randomized Adaptive Search Procedure)é uma metaeurística de partidas múltiplas usada para obter soluções para problemas de otimização combinatória. Nesse trabalho. A metaheurística GRASP tem sido usada para obter soluções de qualidade para muitos problemas de otimização combinatória. Nesse trabalho é proposta uma metodologia para análise do comportamento da metaheurística GRASP. Também são propostas estratégias de hibridização com o religamento de caminhos. Essas estratégias foram desenvolvidas para o problema de atribuição de três índices (AP3) e para o problema de escalonamento de tarefas conhecido na literatura como job-shop schedulling problem (JSP) e são analisadas de acordo com a metodologia proposta. A metodologia para análise do comportamento do método GRASP pode ser usada para prever a partir da versão seqüencial do algoritmo, como a qualidade da solução do algoritmo implementado em paralelo irá variar. Os algoritmos GRASPs desenvolvidos para AP3 e para JSP foram paralelizados e os resultados são comparados aos resultados obtidos usando a metodologia proposta.

ASSUNTO(S)

metaheuristics job-shop scheduling problem grasp metaheuristicas algoritmos paralelos grasp parallel algorithms problema de atribuicao de tres indices metodoloia para analise do grasp problema de escalonamento de tarefas combinatorial optimization 3-index assignment problem otimizacao combinatoria methodology for analysis of grasp

ACESSO AO ARTIGO

Documentos Relacionados