Abstract: In the past few years, considerable attention has been paid to the flexible job-shop scheduling problem (FJSP) due to its NP-hard nature and extensive applications in manufacturing systems. To improve the efficiency of solving FJSPs, a new discrete Lévy flight search strategy is proposed based on the standard Lévy flight, and by combining this strategy with basic genetic algorithm framework, a hybrid genetic algorithm is established. The hybrid algorithm uses a discrete Lévy flight search strategy to perform a variable step-length search on elite population of each generation, which improves the local search capability of the algorithm and enhances the diversity of the population. For comparison, some other algorithms including CS, GA, TLBO are used to conduct experiments on 54 FJSP examples with different scales. The results indicate that the proposed Lévy-GA outperform its competitions in terms of the robustness and convergence effects. Moreover, the proposed hybrid genetic algorithm is also proved to be suitable for solving large-scale FJSPs.

Key words: flexible job-shop scheduling problem (FJSP), Lévy flight search strategy, hybrid genetic algorithm