A heuristic algorithm for the quadratic assignment formulation to the plant layout problem

Abstract

A heuristic algorithm for solving the quadratic assignment formulation to the plant layout problem is presented. The algorithm involves deriving an initial assignment of departments to sites (a construction phase) and then, possibly, improving the solution through exchange between pairs of departments. A ‘classical’ numerical example is used to demonstrate the effectiveness, costwise and in terms of computational effort, of the algorithm. Finally, a set of examples previously used by various authors is assembled and solved in the Appendix. Results are compared to optimal solution values and to the average solution of another known heuristic. These examples could serve as a sample set for testing the effectiveness of other approaches to this problem.