Optimization Online


Insertion based Lin-Kernighan heuristic for single row facility layout

Ravi Kothari(ravikothari***at***iimahd.ernet.in)
Diptesh Ghosh(diptesh***at***iimahd.ernet.in)

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 for all instances, and it improves the best known solutions for several large sized benchmark SRFLP instances.

Keywords: Facilities planning and design; Single Row Facility Layout, Lin-Kernighan Neighborhood, Insertion Neighborhood, Local search

Category 1: Applications -- Science and Engineering (Facility Planning and Design )

Citation: WP2012-01-04, Indian Institute of Management, Ahmedabad, January 2012

Download: [PDF]

Entry Submitted: 01/13/2012
Entry Accepted: 01/13/2012
Entry Last Modified: 01/13/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society