A Lin-Kernighan Heuristic for Single Row Facility Layout
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 first 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.
Authors: | Kothari, Ravi ; Ghosh, Diptesh |
---|---|
Institutions: | Economics, Indian Institute of Management |
Saved in:
freely available
Saved in favorites
Similar items by person
-
Population Heuristics for the Corridor Allocation Problem
Ghosh, Diptesh,
-
A Competitive Genetic Algorithm for Single Row Facility Layout
Kothari, Ravi,
-
Scatter Search Algorithms for the Single Row Facility Layout Problem
Kothari, Ravi,
- More ...