A computational study and survey of methods for the single-row facility layout problem

The single-row facility layout problem <Emphasis FontCategory="NonProportional">(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. <Emphasis FontCategory="NonProportional">(SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular departments so as to minimize the overall interaction cost. This paper compares the different modelling approaches for <Emphasis FontCategory="NonProportional">(SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerländer and Rendl to <Emphasis FontCategory="NonProportional">(SRFLP). In particular, we report optimal solutions for several <Emphasis FontCategory="NonProportional">(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 110 departments. Copyright Springer Science+Business Media, LLC 2013