Enhanced Model Formulations for Optimal Facility Layout

Hanif D. Sherali (), Barbara M. P. Fraticelli () and Russell D. Meller ()
Additional contact information
Hanif D. Sherali: Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Barbara M. P. Fraticelli: Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Russell D. Meller: Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061

Operations Research, 2003, vol. 51, issue 4, 629-644

Abstract: 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.

Keywords: Facilities/equipment planning; layout: MIP model for the rectangular facility layout problem; Programming; integer; cutting plane/facet: valid inequalities and disjunctive representations (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.4.629.16096 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:4:p:629-644

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().