A shuffled cellular evolutionary grey wolf optimizer for flexible job shop scheduling problem with tree-structure job precedence constraints

Along with the growing demands for customized products and small batch production, the flexible job shop manufacturing environment becomes increasingly popular. Efficient flexible job shop scheduling plays a crucial role in making quick responses to production orders with low volume and high variety. When producing complex assembly products that are comprised of multiple and multilevel intermediate parts organized as tree-structure Bills-Of-Materials (BOMs), jobs get restricted by hierarchical precedence constraints due to dependencies between manufactured parts. To cope with this condition, this paper formulates a flexible job shop scheduling problem with job precedence constraints (FJSSP-JPC). A novel shuffled cellular evolutionary grey wolf optimizer (SCEGWO) is proposed to solve FJSSP-JPC with the objective of minimizing makespan. Schedule solutions are encoded as elaborately designed triple-vectors involving the information of job sequencing, grouped operation sequencing and machine assignment, while the satisfactions of job precedence constraints are guaranteed by binary sort tree-based repair mechanism. In SCEGWO, each individual interacts with its topological cellular neighborhood by conducting a micro discrete variant of grey wolf optimizer (GWO), causing that the whole population is decomposed into multiple subpopulations which communicate by the neighborhood overlapping. Extensive experimental results demonstrate that the components of SCEGWO are effective and the proposed SCEGWO outperforms other competing algorithms significantly on the addressed problem. • Hybrid sequential and hierarchical precedence constraints are considered. • A novel shuffled cellular evolutionary grey wolf optimizer is proposed. • A three-vector encoding scheme and a repair mechanism are developed. • Extensive experimental studies verify the superiority of the proposed algorithm.