Título
[en] AN EXPERIMENTAL INVESTIGATION OF PROBABILITY DISTRIBUTION OF SOLUTION TIME IN GRASP AND ITS APPLICATION ON THE ANALYSIS OF PARALLEL IMPLEMENTATIONS
Título
[pt] 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
[pt] RENATA MACHADO AIEX
Vocabulário
[pt] GRASP
Vocabulário
[pt] ALGORITMOS PARALELOS
Vocabulário
[pt] PROBLEMA DE ESCALONAMENTO DE TAREFAS
Vocabulário
[pt] PROBLEMA DE ATRIBUICAO DE TRES INDICES
Vocabulário
[pt] METODOLOGIA PARA ANALISE DO GRASP
Vocabulário
[pt] OTIMIZACAO COMBINATORIA
Vocabulário
[pt] METAHEURISTICAS
Vocabulário
[en] GRASP
Vocabulário
[en] PARALLEL ALGORITHMS
Vocabulário
[en] JOB-SHOP SCHEDULING PROBLEM
Vocabulário
[en] 3-INDEX ASSIGNMENT PROBLEM
Vocabulário
[en] METHODOLOGY FOR ANALYSIS OF GRASP
Vocabulário
[en] COMBINATORIAL OPTIMIZATION
Vocabulário
[en] METAHEURISTICS
Resumo
[pt] 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.
Resumo
[en] GRASP (Greedy Randomized Adaptive Search Procedure) is a
multi-start metaheuristic for combinatorial optimization
problems. GRASP has been used to find quality solutions of
several combinatorial optimization problems. In this work
we describe a methodology for analysis of GRASP. Hybrid
strategies of GRASP with path relinking are also proposed.
These strategies are studied for the 3-index assignment
problem (AP3) and for the job-shop schedulling problem
(JSP) and are analyzed according to the methodology
proposed. The methodology for analysis of GRASP is used to
predict qualitatively how the quality of the solution
varies in a parallel independent GRASP, using the data of
the GRASP sequential version as input. The GRASPs for the
AP3 and for the JSP are parallelized and the computational
results are compared to the results obtained using the
methodology proposed.
Orientador(es)
CELSO DA CRUZ CARNEIRO RIBEIRO
Coorientador(es)
MAURICIO G C REZENDE
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
MAURICIO G C REZENDE
Banca
HENRIQUE PACCA L LUNA
Banca
VINICIUS A ARMENTANO
Catalogação
2003-06-13
Apresentação
2002-08-05
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=3637@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=3637@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.3637
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF CAPÍTULO 8 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF