Optimizing 2-opt-based heuristics on GPU for solving the single-row facility layout problem

Abstract The optimization of most combinatorial problems is NP-hard, which can be solved by heuristic algorithms to obtain approximately optimal solutions, especially for large-scale problems. Many heuristic algorithms can apply the 2-opt local search to find better solutions. In complete 2-opt local search, every valid neighboring solutions of swapping mechanism will be compared, which is very time consuming especially when a sequential algorithm is adopted. Nowadays, graphic processing units (GPUs) have evolved into powerful and flexible parallel computation platforms that have been widely used to accelerate the solving of NP-hard problems. Therefore, in this study, we focus on how to use GPUs to solve the single-row facility layout problem (SRFLP) with the 2-opt-based simulated annealing (SA) heuristic algorithm. As far as we know, this study is the first to solve SRFLP by using a GPU. After analyzing the fitness function and the move gains calculation between parent and child solutions, we propose a prefix-sum formula table to eliminate a large amount of replicated computation. To calculate move gains for the 2-opt local search during each iteration, many GPU threads are created and they construct and lookup the table in parallel. According to experimental results, if the prefix-sum formula table is not adopted, the GPU version outperforms the sequential CPU counterpart with the best speedup of 123. However, if the table is used in the GPU version, the best speedup can reach up to 3208. Because the proposed parallelization approach with the prefix-sum formula table is based on the features of the 2-opt local search and the SRFLP fitness function, it can be applied to any 2-opt-based heuristic algorithm for solving SRFLP even though the SA algorithm is used in this study.