Harmony search algorithm (HS) cannot always avoid being trapped in local optima, and several local search algorithms have recently been used to overcome this limitation by searching the neighborhood of some solution for improved ones. However, how local search affects the performance of HS has not yet been studied systematically. Therefore, in this paper, we first propose to combine the four frequently used local search algorithms (i.e., insertion, swap and reverse operators (ISR), tabu search algorithm (TB), simulated annealing algorithm (SA), and variable neighborhood search algorithm (VNS)) with HS to obtain several harmony searches with local search algorithms (HSLSs). Then, by taking the flexible job-shop scheduling problem (FJSP) as an example and considering decoding times, we study how the parameters (e.g., harmony memory size, harmony memory considering rate, pith adjusting rate, different local search algorithms, local search frequency, and local search intensity, etc.) of HSLSs affect their performance, where the performance is evaluated by the difference rate based on decoding times. The simulation results mainly indicate that (i) as harmony memory size increases gradually, the performance of HSLS first increases rapidly and then tends to remain unchanged, and harmony memory size is not the large the better; (ii) as harmony memory considering rate increases, the performance continues to improve, while the performance of pitch adjusting rate on HSLS goes to the opposite;(iii) with the increase of local search frequency and local search intensity, the performance of HSLS-VNS and HSLS-ISR is better than the other three, respectively. Finally, more benchmark instances are also used to verify the effectiveness of the proposed algorithms. The results of this paper have certain guiding significance on how to choose local search and other parameters to improve HS for solving FJSP
