A MULTI-START LOCAL SEARCH ALGORITHM FOR THE SINGLE ROW FACILITY LAYOUT PROBLEM

The single row facility layout problem (SRFLP) is an NP-hard problem of arranging facilities with given lengths on a line, while minimizing the total cost associated with the flows between all pairs of facilities. In this paper, we present a multi-start local search algorithm to solve the SRFLP. A diversification generator based on a probability function is proposed to construct good quality and diverse multiple starting solutions. A fast local search including first-improvement procedure and fast evaluation technique is adopted to enhance the exploitation ability. An efficient restarting mechanism is applied to exploiting the potential search space. Computational experiments show that the proposed algorithm is competitive with other heuristics for solving the SRFLP.