Optimization Online


A Computational Study and Survey of Methods for the Single-Row Facility Layout Problem

Philipp Hungerländer (philipp.hungerlaender***at***uni-klu.ac.at)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)

Abstract: The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular facilities so as to minimize the overall interaction cost. This paper compares the different modelling approaches for (SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerlšnder and Rendl to (SRFLP). In particular, we report optimal solutions for several (SRFLP) instances from the literature with up to 42 departments that remained unsolved so far. Secondly we significantly reduce the best known gaps and running times for large instances with up to 100 departments.

Keywords: Single-row Facility Layout, Space Allocation, Semidefinite Optimization, Combinatorial Optimization

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Category 3: Applications -- Science and Engineering (VLSI layout )

Citation: Technical Report, Alpen-Adria-Universitaet Klagenfurt

Download: [PDF]

Entry Submitted: 05/11/2011
Entry Accepted: 05/11/2011
Entry Last Modified: 04/17/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society