| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313000 |
| ISSN: | 0101-7438 |
| Authors: | Rangel, Maria Cristina1 Abreu, Nair Maria Maia de2 Boaventura-Netto, Paulo Oswaldo |
| Institutions: | 1Universidade Federal do Espirito Santo, Centro Tecnologico, Vitoria, Espirito Santo. Brasil 2Universidade Federal do Rio de Janeiro, Instituto Alberto Luiz Coimbra de Pos-Graduacao e Pesquisa de Engenharia, Rio de Janeiro. Brasil |
| Year: | 2000 |
| Season: | Jun |
| Volumen: | 20 |
| Number: | 1 |
| Pages: | 45-58 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Experimental |
| English abstract | The Quadratic Assignment Problem (QAP) is an NP-hard problem which has been defying researchers both in theoretical aspects and in what concerns computational results. Owing to its high complexity, several heuristics have been developed trying to approximate its solution. The GRASP metaheuristic (greedy randomized adaptive search procedures) shows a good efficiency with it. In this work a proposal to discard initial supposedly bad initial solutionsis based on cost normalization is presented. A reduction of computational time to find optimal or near-optimal solutions was observed with this GRASP, when compared with the original version |
| Portuguese abstract | 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 |
| Disciplines: | Ciencias de la computación, Matemáticas |
| Keyword: | Matemáticas aplicadas, Computación, GRASP, Metaheurísticas, Problemas cuadráticos, Problema cuadrático de asignación |
| Keyword: | Computer science, Mathematics, Applied mathematics, Computing, GRASP, Metaheuristics, Quadratic problems, Quadratic assignment problem |
| Full text: | Texto completo (Ver HTML) |
