A hybrid heuristic for the facilities layout problem

This paper presents a heuristic procedure for solving the facilities layout problem. The basic approach is the combination of a constructive method with exchange procedures, used repetitively. The constructive heuristic uses information obtained in the process of computing the Gilmore-Lawler bounds as the criterion for choosing the next assignment. Different partial solutions, to be used as starting points for multiple application of the constructive procedure, are obtained by development of a limited breadth-first search tree. The nodes of this tree are evaluated for selection by the Graves-Whinston expected value method. Computational results show that the method compares favorably with two competing procedures from the literature in finding solutions within 0.39% of the best-known solutions for well-known problems. Computing times are reasonable for problems with as many as 36 facilities. The authors also present a new best-known solution for one version of the Steinberg problem, found in the process of experimentation.