Tabu Search for the Single Row Facility Layout Problem Using Exhaustive 2-Opt and Insertion Neighborhoods

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 NP-hard. In this paper, two tabu search implementations are presented one involving an exhaustive search of the 2-opt neighbourhood and the other involving an exhaustive search of the insertion neighbourhood. Techniques to significantly speed up the search of the two neighbourhoods are given. Computational experiments show that the speed up techniques are effective, and tabu search implementations are competitive. Our tabu search implementations improved several previously known best solutions for large sized benchmark SRFLP instances. [W.P. No. 2012-01-03]. URL:[http://www.iimahd.ernet.in/assets/snippets/workingpaperpdf/7520037992012-01-03.pdf].