Application of Grey Wolf Optimization for Solving Combinatorial Problems: Job Shop and Flexible Job Shop Scheduling Cases

Abstract

Grey wolf optimization (GWO) algorithm is a new population-oriented intelligence algorithm, which is originally proposed to solve continuous optimization problems inspired from the social hierarchy and hunting behaviors of grey wolves. It has been proved that GWO can provide competitive results compared with some well-known meta-heuristics. This paper aims to employ the GWO to deal with two combinatorial optimization problems in the manufacturing field: job shop and flexible job shop scheduling cases. The effectiveness of GWO algorithm on the two problems can give an idea about its possible application on solving other scheduling problems. For the discrete characteristics of the scheduling solutions, we developed a kind of discrete GWO algorithm with the objective of minimizing the maximum completion time (makespan). In the proposed algorithm, searching operator is designed based on the crossover operation to maintain the algorithm work directly in a discrete domain. Then an adaptive mutation method is introduced to keep the population diversity and avoid premature convergence. In addition, a variable neighborhood search method is embedded to further enhance the exploration. To evaluate the effectiveness, the discrete GWO algorithm is compared with other published algorithms in the literature for the two scheduling cases. Experimental results demonstrate that our algorithm outperforms other algorithms for the scheduling problems under study.

Keywords

• Job shop
• flexible job shop
• makespan
• discrete grey wolf optimization
• genetic operator
• variable neighborhood search