An Exact Approach to the One-Dimensional Facility Layout Problem
Author:
- 1 August 2008
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 56 (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(n2) 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
This publication has 31 references indexed in Scilit:
- On the exact solution of a facility layout problemEuropean Journal of Operational Research, 2006
- A semidefinite optimization approach for the single-row layout problem with unequal dimensionsDiscrete Optimization, 2005
- An ant algorithm for the single row layout problem in flexible manufacturing systemsComputers & Operations Research, 2005
- A new heuristic procedure for the single-row facility layout problemInternational Journal of Computer Integrated Manufacturing, 2001
- A heuristic procedure for the single-row facility layout problemEuropean Journal of Operational Research, 1995
- A hierarchy of relaxations and convex hull characterizations for mixed-integer zero—one programming problemsDiscrete Applied Mathematics, 1994
- Experimental analysis of simulated annealing based algorithms for the layout problemEuropean Journal of Operational Research, 1992
- Efficient models for the facility layout problemEuropean Journal of Operational Research, 1991
- Methods for the one-dimensional space allocation problemComputers & Operations Research, 1990
- Outline of an algorithm for integer solutions to linear programsBulletin of the American Mathematical Society, 1958