Optimal facility layout design

The facility layout problem (FLP) is a fundamental optimization problem encountered in many manufacturing and service organizations. Montreuil introduced a mixed integer programming (MIP) model for FLP that has been used as the basis for several rounding heuristics. However, no further attempt has been made to solve this MIP optimally. In fact, though this MIP only has 2n(n − 1) 0–1 variables, it is very difficult to solve even for instances with n approximate to 5 departments. In this paper we reformulate Montreuil's model by redefining his binary variables and tightening the department area constraints. Based on the acyclic subgraph structure underlying our model, we propose some general classes of valid inequalities. Using these inequalities in a branch-and-bound algorithm, we have been able to moderately increase the range of solvable problems. We are, however, still unable to solve problems large enough to be of practical interest. The disjunctive constraint structure underlying our FLP model is common to several other ordering/arrangement problems; e.g., circuit layout design, multidimensional orthogonal packing and multiple resource constrained scheduling problems. Thus, a better understanding of the polyhedral structure of this difficult class of MIPs would be valuable for a number of applications.