This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Sherali, H. D. Articles by Meller, R. D. Search for Related Content

Enhanced Model Formulations for Optimal Facility Layout

Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
hanifs{at}vt.edu
hanifs{at}vt.edu
hanifs{at}vt.edu

This paper presents an improved mixed-integer programming (MIP) model and effective solution strategies for the facility layout problem and is motivated by the work of Meller et al. (1999). This class of problems seeks to determine a least-cost layout of departments having various size and area requirements within a rectangular building, and it is challenging even for small instances. The difficulty arises from the disjunctive constraints that prevent departmental overlaps and the nonlinear area constraints for each department, which existing models have failed to approximate with adequate accuracy. We develop several modeling and algorithmic enhancements that are demonstrated to produce more accurate solutions while also decreasing the solution effort required. We begin by deriving a novel polyhedral outer approximation scheme that can provide as accurate a representation of the area requirements as desired. We also design alternative methods for reducing problem symmetry, evaluate the performance of several classes of valid inequalities, explore the construction of partial convex hull representations for the disjunctive constraints, and investigate judicious branching variable selection priority schemes. The results indicate a substantial increase in the accuracy of the layout produced, while at the same time providing a dramatic reduction in computational effort. In particular, three previously unsolved test problems from the literature for which Meller et al.'s algorithm terminated prematurely after 24 cpu hours of computation (on a SUN Ultra 2 workstation with 390 MB RAM) with respective optimality gaps of 10.14%, 26.45%, and 40%, have been solved to exact optimality with reasonable effort using our proposed approach.

Subject classifications: Facilities/equipment planning, layout: MIP model for the rectangular facility layout problem; Programming, integer, cutting plane/facet: valid inequalities and disjunctive representations.
History: Received May 2001; revision received December 2001; accepted October 2002.

This article has been cited by other articles:

				M. F. Anjos and A. Vannelli A New Mathematical-Programming Framework for Facility-Layout Design INFORMS Journal on Computing, January 1, 2006; 18(1): 111 - 118. [Abstract] [PDF]