首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Massively parallel tabu search for the quadratic assignment problem
Authors:Jaishankar Chakrapani  Jadranka Skorin-Kapov
Institution:(1) Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, 11794 Stony Brook, NY, USA;(2) Harriman School for Management and Policy, State University of New York at Stony Brook, 11794 Stony Brook, NY, USA
Abstract:A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn 2 processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号