[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:3637 |
| Date | 13 June 2003 |
| Creators | RENATA MACHADO AIEX |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds