A Lin-Kernighan Heuristic for Single Row Facility Layout

Ravi Kothari and Diptesh Ghosh ()

No WP2012-01-04, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

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 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.

Date: 2012-01-12
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/775603762012-01-04.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:11428

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().