[en] AUTONOMIC PARALELIZATION OF METAHEURISTICS IN COMPUTATIONAL GRIDS

[pt] PARALELIZAÇÃO AUTONÔMICA DE METAHEURÍSTICAS EM AMBIENTES DE GRID

[pt] ALETEIA PATRICIA FAVACHO DE ARAUJO

[pt] METAHEURISTICAS PARALELAS

[pt] ESTRATEGIA DE PARALELIZACAO

[pt] COMPUTACAO EM GRID

[en] PARALLEL METAHEURISTICS

[en] PARALELIZATION STRATEGY

[en] COMPUTATIONAL GRID

[pt] O desenvolvimento de metaheurísticas paralelas autonômicas para serem executadas eficientemente em ambientes de grid é o objetivo desta tese. A aplicação paralela deve ser capaz de se auto-adaptar às mudanças que ocorrem dinamicamente no ambiente, sem que o usuário precise interferir diretamente no código da mesma. Para isso, a metaheurística autonômica deve ser vista como uma aplicação com dois níveis independentes: middleware e estratégia. O middleware é responsável por gerenciar todo o ambiente de execução, de acordo com as características da aplicação. A estratégia hierárquica distribuída permite a cooperação entre todos os processos envolvidos, sem degradar o desempenho da aplicação devido ao aumento da comunicação entre processos. Para validar esta proposta foram desenvolvidas duas implementações paralelas de metaheurísticas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Para ambos os problemas, as implementações desenvolvidas foram testadas no ambiente grid Sinergia, formado por máquinas localizadas em três diferentes cidades do Estado do Rio de Janeiro. As parelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura.

[en] The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheuristic should be seen as an application on two independent levels: middleware and strategy. The middleware is responsible for managing the entire execution environment, according to the characteristics of the application. The distributed hierarchical strategy enables the cooperation between all processes involved, without degrading the performance of the application due to increased communication between processes. To validate this proposal, two parallel implementations of metaheuristics were developed, one for the mirrored traveling tournament problem and the other for the diameter constrained minimum spanning tree problem. For both problems, the developed implementations were tested in the grid Synergy environment, formed by machines located in three different cities in the state of Rio de Janeiro. The paralelizations improved, for several instances, the best known results in the literature.

CELSO DA CRUZ CARNEIRO RIBEIRO

EUGENE FRANCIS VINOD REBELLO

SERGIO LIFSCHITZ

SIMONE LIMA MARTINS

RENATO FONTOURA DE GUSMAO CERQUEIRA

CELSO DA CRUZ CARNEIRO RIBEIRO

EDSON NORBERTO CACERES

MARIO ANTONIO RIBEIRO DANTAS

2008-08-15

2008-04-07

[pt] TEXTO

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

PORTUGUÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=12077@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=12077@2

https://doi.org/10.17771/PUCRio.acad.12077