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_ji ≥ 0, for 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.