An effective multi-start multi-level evolutionary local search for the flexible job-shop problem

In this paper, an improved greedy randomized adaptive search procedure (GRASP) with a multi-level evolutionary local search (mELS) paradigm is proposed to solve the Flexible Job-shop Problem (FJSP). The FJSP is a generalisation of the well-known Job-Shop Problem with the specificity of allowing an operation to be processed by any machine from a given set. The GRASP metaheuristic is used for diversification and the mELS is used for intensification. Four different neighbourhood structures are formalised. A procedure for fast estimation of the neighbourhood quality is also proposed to accelerate local search phases. The metaheuristic has been tested on several datasets from the literature. The experimental results demonstrate that the proposed GRASP-mELS has achieved significant improvements for solving FJSP from the viewpoint of both quality of solutions and computation time. A comparison among the proposed GRASP-mELS and other state-of-the-art algorithms is also provided in order to show the effectiveness and efficiency of the proposed metaheuristic.