An improved tabu search heuristic for solving facility layout design problems

The design of the facility layout of a manufacturing system, usually formulated and solved as a quadratic assignment problem (QAP), is of tremendous importance for its effective utilization. In this paper the authors discuss a new implementation of the tabu search metaheuristic to solve the QAP. The present tabu search implementation includes recently-based and long term memory structure, dynamic tabu list size strategies, and intensification and diversification strategies. The tabu search algorithm converges with a reasonable speed from any random initial solution to very good layouts. The extensive computational experiments, including statistical analysis and library analysis, strongly support the superiority of our tabu search implementation (we refer to it as (CK)) over existing algorithms in the literature.