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 Google Scholar Google Scholar Articles by Amaral, A. R. S. Search for Related Content

An Exact Approach to the One-Dimensional Facility Layout Problem

Departamento de Informática, Universidade Federal do Espírito Santo (UFES), Vitória, ES 29060-970, Brazil
amaral{at}inf.ufes.br

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²) 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.

Subject classifications: facilities/equipment planning; layout; programming; integer.
History: Received June 2005; revision received May 2006; accepted April 2007.