Solving the Single Row Facility Layout Problem by K-Medoids Memetic Permutation Group

— The single row facility layout problem (SRFLP) is concerned with arranging facilities along a straight line so as to minimize the sum of the products of the ﬂow costs and distances between all facility pairs. SRFLP has rich practical applications and is however NP-hard. In this paper, we ﬁrst investigate a dedicated symmetry-breaking approach based on permutation group theory for reducing the solution space of SRFLP. Relevant symmetry properties are identiﬁed through the alternating group of the original solution space or the corresponding coordinate rotation space. Then, a memetic algorithm is proposed to explore promising search regions regarding the reduced solution space. The memetic algorithm employs a problem-speciﬁc crossover operator guided by k -medoids clustering technique to pro- duce meaningful offspring solutions. The algorithm additionally uses a simulated annealing procedure to intensively exploit a given search region and a distance-and-quality based population management strategy to ensure a reasonable diversity of the population. Experimental results on commonly used benchmark instances and newly introduced large-scale instances with sizes up to 2000 facilities show that the proposed algorithm competes favorably with state-of-the-art SRFLP algorithms. It attains all but one previous best known upper bounds and discovers new upper bounds for 33 instances out of the 93 popular benchmark instances.