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 we discuss a new implementation of the tabu search metaheuristic to solve the QAP. Our tabu search implementation includes recency-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. Our 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.