Flexible job shop scheduling using hybrid differential evolution algorithms

• Hybrid differential evolution algorithms are proposed for the studied problem.
• Local search based on the critical path is embedded in the differential evolution.
• The speed-up method is presented in the local search phase.
• The proposed algorithms are very competitive with state of the art.
• Some new best known solutions for well known benchmark instances are found.

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.