# Single Row Facility Layout Problem

# Problem Description

The single row facility layout problem (SRFLP) is an N P-hard problem that consists of finding an optimal arrangement of a set of rectangular facilities (with equal height and different lengths), placing them next to each other along a line. The SRFLP has practical applications in contexts such as arranging rooms along corridors, setting books on shelves, allocating infor- mation on magnetic disks, storing items in warehouses, or designing layouts for machines in manufacturing systems.

Formally, the SRFLP is defined as follows: let *F* = {1, 2, . . . , *n*} be a set of *n* > 2
rectangular facilities with fixed height but different lengths *l _{i}* > 0, for

*i*∈

*F*. Additionally, let

*c*=

_{ij}*c*≥ 0, for

_{ji}*i*,

*j*∈

*F*, be the weight between facilities

*i*and

*j*, which usually models some transmission cost between them. A particular solution to this problem is an ordering π = {π(1), π(2), . . . , π(

*n*)} of the facilities in

*F*, whose cost

*C*(π) is defined according to the following objective function:

where *d _{π(q)π(r)}* represents the distance between the centers of facilities π(

*q*) and π(

*r*) (i.e., located in the ordering π at positions

*q*and

*r*, respectively), and is computed as:

The optimization problem therefore consists of finding an ordering π^{⋆}
that minimizes *C*(π). Formally:

where Π* _{n}* is the set of permutations of the first

*n*positive integers.

# State of the Art Methods

The metaheuristics developed to solve the Single Row Facility Layout problem are:

**GENALGO**: a genetic algorithm described in Kothari and Ghosh (2014)**SS-P2**: a scatter search variant reported in Kothari and Ghosh (2014)**GRASP-PR**: Hybrid method that combines GRASP methodology with Path-Relinking. Rubio-Sánchez, et al. (2015)

# Instances

In this section several instance sets are described. These instance set have been used in the related literature to compare the performance of methods for the Single Row Layout Problem. Additionally, we have created new larger instances, where the facility lengths and costs were drawn from the same distributions used to generate the Anjos and sko instances:

**Anjos**: This data set consists of four groups of five instances, each of size*n*= {60, 70, 75, 80}.**Sko**: This data set is based on the Quadratic Assignment problem. In this paper we use the four groups of five instances, each of size*n*= {64, 72, 81, 100}**Amaral**: This data set consists of three instances, each of size*n*= 110.**Anjos-large**: This data set consists of eight groups of five instances, each of size n = {150, 200, 250, 300, 350, 400, 450, 500}**Sko-large**: This data set consists of eight groups of five instances, each of size n = {150, 200, 250, 300, 350, 400, 450, 500}

# Computational Experience

We performed extensive computational experiments with the 43 instances commonly used in the recent literature, and on the 40 new instances of sizes 200, 300, 400, and 500. The best values for the instances can be downloaded here.

# References

Rubio-Sánchez, M., Gallego. M., Gortázar F., Duarte A. “GRASP with path relinking for the single row facility layout problem“. Submitted to Knowledge Based Systems.

Ravi Kothari and Diptesh Ghosh. "An efficient genetic algorithm for single row facility layout". Optimization Letters, 8(2):679–690, 2014.

Ravi Kothari and Diptesh Ghosh. "A scatter search algorithm for the single row facility layout problem". Journal of Heuristics, 20(2):125–142, 2014.

Miguel F. Anjos and Ginger Yen. "Provably near-optimal solutions for very large single-row facility layout problems". Optimization Methods Software, 24(4-5):805– 817, 2009.

Miguel F. Anjos, Andrew Kennings, and Anthony Vannelli. "A semidefinite optimization approach for the single-row layout problem with unequal dimensions". Discrete Optimization, 2(2):113–122, 2005.

Andre R. S. Amaral and Adam N. Letchford. A polyhedral approach to the single row facility layout problem. Mathematical Programming, 141(1-2):453–477, 2013.