Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

GRASP para o PQA: um limite de aceitação para soluções iniciais

2000; Sociedade Brasileira de Pesquisa Operacional; Volume: 20; Issue: 1 Linguagem: Português

10.1590/s0101-74382000000100006

1678-5142

Maria Cristina Range, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto,

Optimization and Packing Problems

O Problema Quadrático de Alocação (PQA) pertence à classe dos problemas NP-Hard e desafia os pesquisadores tanto em sua teoria quanto em sua parte computacional. Pela sua alta complexidade muitos métodos heurísticos têm sido desenvolvidos para tentar resolvê-lo aproximadamente. A metaheurística GRASP (greedy randomized adaptive search procedures) se mostrou bastante eficiente. Neste trabalho, uma proposta para descartar soluções iniciais supostamente ruins é apresentada com base na normalização de custos calculadas num intervalo entre limites de solução. Para este GRASP restrito, foi observada uma redução do tempo computacional para encontrar as soluções ótimas ou soluções viáveis de boa qualidade quando comparado ao GRASP original.