Application of Levy flight-based harmony search algorithm for the flexible job shop scheduling

Abstract

Abstract The Flexible Job Shop Scheduling Problem (FJSP) is an extension of the classical job shop scheduling problem, which is characterized by the fact that each process can be processed on multiple candidate machines, and needs to solve the two subproblems of machine allocation and process sequencing simultaneously. Since FJSP is an NP-hard problem, its complexity and multi-objective characteristics make the traditional exact methods inefficient. At the same time, the existing intelligent optimization algorithms are prone to falling into local optimums, which makes it difficult to balance global exploration and local exploitation capabilities. To this end, this study proposed a Levy flight-based Harmony Search algorithm (LHS), which effectively avoids premature convergence by dynamically and adaptively adjusting the Harmony Memory Considering Rate (HMCR), the probability of Pitch Adjusting Rate (PAR), and the arbitrary distance Bandwidth(BW), and by introducing a Levy flight mechanism to perturb the parameters to broaden the search space and enhance the diversity of the population. We validate the experiments using 8 × 8, 10 × 10, and 10 benchmark instances proposed by Brandimarte in the literature, and the experimental results show that the Harmony search algorithm based on Levy flight outperforms the other comparative algorithms in terms of the solution quality and the convergence speed, demonstrating the effectiveness of its solution for FJSP.