The block layout problem is concerned with locating activities or departments of an organization such that those activities with the strongest interrelationships are closest to each other. Many solution procedures have been proposed for this problem. Research indicates that certain solution procedures perform reasonably well on certain data sets, but yield less desirable results on other problem sets with no clearly superior procedure emerging. Attention has focused on the complexity of the problem as the deciding factor. The measure of complexity most commonly used is the coefficient of variation of the problem data. As the coefficient of variation increases, it is suggested that human planners might be better able to handle the problem. The research in this area indicates mixed results.

It is argued in this paper that these measures are overly simplistic and cannot fully capture all of the aspects which determine problem complexity. A multivariate approach for measuring problem complexity is proposed. This approach is based upon the inherent structure of the problem itself. It is thus based on structural pattern recognition. An algorithm for determining the basic substructures and megastructure of a problem is proposed. Differences in performance of different solution procedures on different layout problems are examined using this multivariate approach. The approach is illustrated with example problems from the literature. An unpublished problem from a company is used to illustrate the utility of the megastructure as a guide for laying out a facility.