Simulated annealing, an analogy between statistical mechanics and combinatorial optimization, has attracted considerable attention due to its potential in dealing with certain traditional optimization problems. However, it has been shown to be parameter sensitive and requires more computational effort to produce high quality solutions than traditional heuristics. The present paper reports on a new approach to applying this method to a class of quadratic assignment problems, i.e., the facility layout problem. This approach combines the simulated annealing methodology with a specific layout design rule, which in the case of this study is a ‘Move Desirability Table’. Two annealing methods are proposed based on this approach which differ only in cooling schedule. The first method produces high quality solutions, while the second method is faster with a slight degradation in the quality of solutions and therefore suitable for larger problems. Performance of the two methods was numerically tested on standard problems as well as two larger problems (n=50 and n=100; n is the number of facilities) and was compared to that of Wilhelm & Ward, Connolly and other heuristics, e.g., QAPH4 CRAFT, biased sampling and the revised Hillier procedure. As the experimental results, it was found that except in the case of n=50, 100, the proposed methods are computationally faster than Wilhelm & Ward and that the solution qualities of the proposed methods in all the cases are superior to those of Wilhelm & Ward, Connolly and other heuristic procedures.