A Lin-Kernighan heurisitic for single row facility layout
Abstract
The single row facility layout problem (SRFLP) is the problem of arranging facilities with
given lengths on a line, while minimizing the weighted sum of the distances between all pairs
of facilities. The problem is known to be NP-hard. In this paper, we present a neighborhood
search heuristic called LK-INSERT which uses a Lin-Kernighan neighborhood structure built
on insertion neighborhoods. To the best of our knowledge this is the rst such heuristic for the
SRFLP. Our computational experiments show that LK-INSERT is competitive and improves
the best known solutions for several large sized benchmark SRFLP instances.
Collections
- Working Papers [2627]