A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problems

Job shop scheduling problems (JSSPs) are intractable combinatorial optimization problems and have been solved by numerous researchers over the last couple of decades, however, their solution still needs improvement. In this paper, a Hybrid Evolution Strategies-Simulated Annealing (HES-SA) algorithm is proposed for minimizing the makespan of JSSPs. The initial solution is randomly generated in the Evolution Strategies (ES) algorithm. Since mutation is the main source of genetic variation, and the performance of the ES algorithm relies on the mutation operator, multi-mutation operators are used in this paper i.e. a random number between 1 and 4 is generated and based on that number, the value used is either swap mutation, insertion mutation, scrambled mutation, or inversion mutation. For reproduction (1 + 9)-ES is used, hence nine offspring are randomly generated from one parent. The ES algorithm often gets trapped in local minima and suffers from premature convergence, hence it is combined with the Simulated Annealing (SA) algorithm, which helps to avoid local minima and increases the local search ability of the Hybrid HES-SA algorithm. In the SA algorithm, an insertion mutation is used and the initial temperature is set at 0.95, which is then gradually reduced for finding good solutions in the neighborhood. The HES-SA algorithm is tested on Fisher, Lawrence, and Yamada benchmark job shop problems and compared with other famous available techniques using the Wilcoxon signed rank test and Friedman test. The computational results show that HES-SA algorithm performs better in terms of makespan values as compared to other famous techniques.