Scatter search algorithms for the single row facility layout problem

Abstract

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, with the objective of minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard and research has focused on heuristics to solve large instances of the problem. In this paper we present four scatter search algorithms to solve large sized SRFLP instances. Our computational experiments show that these algorithms generate better solutions to 26 of the 43 large sized benchmark SRFLP instances than were previously known in the literature. In the other 17 instances they output the best solutions previously known in the literature.