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

The single-period unequal-area facility layout problem has been studied for several decades. Many solution approaches have been proposed. One approach models the problem as a mixed-integer program (MIP) in which binary (0/1) variables are used to prevent departments from overlapping with one another. Solving these MIPs is a difficult task - currently the largest problems that can be solved to optimality contain only 11 or 12 departments. Motivated by this situation, we developed a heuristic algorithm which utilizes a graph-pair representation technique to relax integer constraints. Our algorithm produces good solutions for problems considerably bigger than 12 departments. Moreover, our approach shows potentials in solving other layout problems such as multi-period or multi-floor.