Grey Wolf Optimizer with Multi Step Crossover for Bi-objective Job Shop Scheduling Problem

In this article, a meta-heuristic based on Grey Wolf Optimizer is developed to solve a Bi-objective Job Shop Scheduling Problem (BJSSP). JS SP is NP-hard problem and a generalization of other scheduling and combinatorial optimization problems. Exploring new solution methods can bring improvements in numerous applications of JSSP in diverse domains and other scheduling issues. The objectives considered in this study are Makespan (C-max) and Mean Flow Time (MFT). In addition, precedence constraints are taken into account to find compromise solutions optimizing the two criteria simultaneously. The developed meta-heuristic is supported by two proposed local search mechanisms. The first one is based on the simulated annealing paradigm to improving the current non-dominated solutions set in its neighborhood. The second one is used to balance between exploitation by Non-dominated Multi Step Crossover operator (NMSX), and exploration by Nondominated Multi Step Mutation operator (NMSM) in the search space. Comparisons are made with three well-known algorithms: Non-dominated Sorting Genetic Algorithm NSGA-II [13], Pareto Archived Simulated Annealing PASA [7] and Hybrid Genetic Algorithm HGA [9]. The experimental results suggest the efficiency of the proposed algorithm to solving the BJSSP.