A Hybrid Search Using Genetic Algorithms and Random-Restart Hill-Climbing for Flexible Job Shop Scheduling Instances with High Flexibility

Abstract

This work presents a novel hybrid algorithm called GA-RRHC based on genetic algorithms (GAs) and a random-restart hill-climbing (RRHC) algorithm for the optimization of the flexible job shop scheduling problem (FJSSP) with high flexibility (where every operation can be completed by a high number of machines). In particular, different GA crossover and simple mutation operators are used with a cellular automata (CA)-inspired neighborhood to perform global search. This method is refined with a local search based on RRHC, making computational implementation easy. The novel point is obtained by applying the CA-type neighborhood and hybridizing the aforementioned two techniques in the GA-RRHC, which is simple to understand and implement. The GA-RRHC is tested by taking four banks of experiments widely used in the literature and comparing their results with six recent algorithms using relative percentage deviation (RPD) and Friedman tests. The experiments demonstrate that the GA-RRHC is a competitive method compared with other recent algorithms for instances of the FJSSP with high flexibility. The GA-RRHC was implemented in Matlab and is available on Github.

Keywords

• flexible job shop scheduling instances
• genetic operators
• local search methods
• cellular automata