Texto completo
| |
| Autor(es): |
Luciano Nascimento Moreira
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Carlos. , gráficos, ilustrações, tabelas. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Data de defesa: | 2003-06-16 |
| Membros da banca: |
Cassilda Maria Ribeiro;
Raul Vinhas Ribeiro;
Roseli Aparecida Francelin Romero
|
| Orientador: | Cassilda Maria Ribeiro |
| Área do conhecimento: | Engenharias - Engenharia de Produção |
| Indexada em: | Banco de Dados Bibliográficos da USP-DEDALUS |
| Localização: | Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação. Biblioteca Prof. Achille Bassi ; ICMSC/T; M838de |
| Resumo | |
O problema de roteamento de dados em rede de computadores consiste em minimizar o tempo médio de atraso na transmissão de mensagens, escolhendo para elas um caminho ótimo, através dos arcos da rede. Em seu trabalho, Luvezute propôs um algoritmo primai de relaxamento para otimizar o problema de roteamento de dados. O algoritmo proposto por Luvezute resolve iterativamente o problema de multifluxo, decompondo-o da forma mais independente possível, em subproblemas de simples fluxo, sendo um subproblema para cada mensagem. Esta independência entre os cálculos permite que a resolução dos subproblemas seja simultânea, admitindo-se assim uma implementação em paralelo. Nesta dissertação apresentamos um algoritmo paralelo, do tipo Fase I para encontrar uma solução inicial factível para o problema de multifluxo. Este algoritmo permite resolver de maneira mais rápida os problemas de grande porte que é o nosso objetivo inicial. O algoritmo de Fase I aqui desenvolvido pode ser utilizado para problemas de Multifluxo em geral, isto é, problemas com função objetivo linear ou não linear. O algoritmo desenvolvido foi escrito em linguagem C e implementado numa rede de microcomputadores, usando o sistema operacional UNIX. Além dos testes computacionais, apresentamos uma análise da eficiência do algoritmo e do seu speedup. (AU) | |
| Processo FAPESP: | 00/02088-2 - Desenvolvimento de um algoritmo paralelo de fase I para o problema de multifluxo: uma aplicação ao problema de roteamento de dados e estudo do problema ciclagem no algoritmo fluxo em redes com custo não linear |
| Beneficiário: | Luciano Nascimento Moreira |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |