An Exact Approach to the One-Dimensional Facility Layout Problem

André R. S. Amaral ()
Additional contact information
André R. S. Amaral: Departamento de Informática, Universidade Federal do Espírito Santo (UFES), Vitória, ES 29060-970, Brazil

Operations Research, 2008, vol. 56, issue 4, 1026-1033

Abstract: The one-dimensional facility layout problem is concerned with arranging n departments of given lengths on a line, while minimizing the weighted sum of the distances between all pairs of departments. The problem is NP-hard because it is a generalization of the minimum linear arrangement problem. In this paper, a 0-1 quadratic programming model consisting of only O( n 2 ) 0-1 variables is proposed for the problem. Subsequently, this model is cast as an equivalent mixed-integer program and then reduced by preprocessing. Next, additional redundant constraints are introduced and linearized in a higher space to achieve an equivalent mixed 0-1 linear program, whose continuous relaxation provides an approximation of the convex hull of solutions to the quadratic program. It is shown that the resulting mixed 0-1 linear program is more efficient than previously published mixed-integer formulations. In the computational results, several problem instances taken from the literature were efficiently solved to optimality. Moreover, it is now possible to efficiently solve problems of a larger size.

Keywords: facilities/equipment planning; layout; programming; integer (search for similar items in EconPapers)
Date: 2008
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.1080.0548 (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:56:y:2008:i:4:p:1026-1033

Access Statistics for this article

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