Implementacao do algoritmo paralelo para o problema de roteamento de dados no sistema pvmw'95.

• Processo: 98/11997-4
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 1998
• Data de Término da vigência: 31 de outubro de 1999
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Cassilda Maria Ribeiro
• Beneficiário: Fredson Carlos Javurek de Oliveira
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Programação não linear Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Paralelos | Fluxo Em Redes | Programacao Nao Linear | Roteamento De Dados

Resumo

Usando a formulação primal do problema de roteamento, desenvolveu-se duas versões de um algoritmo paralelo primal de relaxamento. Todas as duas versões trabalham com vários subproblemas: um subproblema para cada produto. A primeira versão utiliza um algoritmo tipo gradiente projetado para resolver os subproblemas. Na outra versão, os subproblemas são resolvidos através do método simplex convexo. Foi feito a implementação seqüencial destes algoritmos em Turbo Pascal num PC486-DX O processo iterativo de atualização de fluxo foi implementado usando um processo semelhante ao método iterativo de Jacobi. A versão que apresentou melhor resultado é a que resolve o subproblema pelo simplex convexo. Nosso objetivo agora é proceder a implementação paralela, em linguagem C. da versão que apresentou o melhor resultado no PVM'95. (AU)