An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints

Concentrated on the production scheduling of complex products that are assembled by multiple and multilevel manufactured parts, this paper studies the flexible job shop scheduling problem with job precedence constraints (FJSSP-JPC). Distinguished from traditional scheduling model that only considers sequential operation precedence constraints defined by process routings, FJSSP-JPC takes additional hierarchical job precedence constraints defined by Bills-of-Materials (BOMs) of final products into account. A mixed integer programming mathematical model is formulated to describe FJSSP-JPC. To represent feasible solutions that satisfy the hybrid precedence constraints, a novel three-vector encoding scheme and a job precedence repair mechanism based on binary tree are elaborated. Subsequently, this paper proposes an efficient evolutionary multi-objective grey wolf optimizer (EMOGWO) to tackle FJSSP-JPC with minimizing the objectives of makespan, maximum machine workload and total machine workload simultaneously. The algorithm involves an improved social hierarchy and a diverse leader strategy to enhance the convergence speed and population diversity separately. Statistical experiments demonstrate that EMOGWO overwhelms other competing algorithms in aspects of cardinality, convergence and diversity metrics on the majority of test instances.