An effective shuffled frog-leaping algorithm for the flexible job-shop scheduling problem

摘要

As an extension of the classic job-shop scheduling problem (JSP), the flexible job-shop (FJSP) is NP-hard and has a wide application background. In this paper, a shuffled frog-leaping algorithm (SFLA) based algorithm is proposed for solving the FJSP. First, the SFLA employs a hybrid encoding scheme in which two sequences are used to illustrate both operation order sequence and machines assignment. Second, a special bi-Ievel crossover scheme as a local search scheme based on the critical path is incorporated in the framework of the memetic search. The searching ability of the modified SFLA can be well balanced between exploration and exploitation. Furthermore, the influence of the parameter setting is also investigated and suitable parameters are suggested. Numerical simulation and comparisons based on the well-known benchmark problems indicates the effectiveness of the SFLA for solving the problem.