A Hybrid Meta-Heuristic to Solve Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem (FJSP) plays an important role in real production systems. FJSP enables operation processing on more than one alternative machine, and evidently, FJSP becomes a strongly NP-hard problem. Accordingly, our challenge was to develop an algorithm that can outperform the previous works in minimizing the makespan. We propose an integrated approach of hybrid genetic algorithm and simulated annealing (GA-SA) that incorporates an acceptance criterion into crossover operator, which could maintain the good characteristics of the previous generation and reduce the disruptive effects of genetic operators. Our contribution is that the hybridization of simulated annealing algorithm within a genetic framework was tested using a large number of benchmark problems (162) and yields to better performance, as opposed to other meta-heuristic algorithms. The hybrid algorithm proposed in our chapter has better solution capacity within sensible computational time.