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

Yavuz A. Bozer, Chi Tai Wang

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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.

Original languageEnglish
Pages (from-to)382-391
Number of pages10
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - 16 Apr 2012


  • Facilities planning and design
  • Graph-pair representation
  • Heuristics
  • Integer programming
  • Simulated annealing


Dive into the research topics of 'A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem'. Together they form a unique fingerprint.

Cite this