A graph‐pair representation and MIP‐model‐based heuristic for the unequal‐area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal‐area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed‐integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a ‘graph pair’ to determine and manipulate the relative location of the departments in the layout. The graph‐pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph‐pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph‐pair representation technique are discussed at the end of the paper.