4.7 Article

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

Journal

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
Volume 27, Issue 2, Pages 251-265

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2022.3165987

Keywords

Clustering algorithms; Metaheuristics; Simulated annealing; Layout; Search problems; Memetics; Statistics; k-medoids clustering; memetic search; permutation group; simulated annealing; single-row facility layout

Ask authors/readers for more resources

This article investigates a symmetry-breaking approach based on the permutation group theory and proposes a memetic algorithm to solve the single-row facility layout problem (SRFLP). The algorithm uses a problem-specific crossover operator and a simulated annealing procedure to generate meaningful offspring solutions. Experimental results show that the algorithm performs well on benchmark and large-scale instances.
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 flow costs and distances among all facility pairs. SRFLP has rich practical applications and is however NP-hard. In this article, we first investigate a dedicated symmetry-breaking approach based on the permutation group theory for reducing the solution space of SRFLP. Relevant symmetry properties are identified 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-specific crossover operator guided by ${k}$ -medoids clustering technique to produce 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 (BKS) and discovers new upper bounds for 33 instances out of the 93 popular benchmark instances.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available