Tabu search and iterated local search for the cyclic bottleneck assignment problem

This problem has been shown to be NP-hard. Consequently, we present two algorithms that can be used to solve the problem efficiently. One algorithm is based on the Tabu search method, and the other follows an iterated local search scheme. We evaluate our algorithms on 470 benchmark instances and 470 newly generated instances, and compare them with available metaheuristics and commercial solver CPLEX. The computational results for most of our problem instances show that our proposed approaches achieve excellent performance. Our algorithms outperform existing approaches and CPLEX. The tabu search approach works slightly better than the iterated local search approach.