A multi-objective multi-micro-swarm leadership hierarchy-based optimizer for uncertain flexible job shop scheduling problem with job precedence constraints

In realistic production scheduling, the processing time of operations and the due time of orders always fail to be precisely estimated as deterministic values due to fluctuating manufacturing environments and modest delay tolerance. When fabricating complex products that are assembled by multilevel parts, tree-structure dependencies between parts lead to hierarchical precedence constraints between corresponding jobs. Consequently, this paper studies an uncertain flexible job shop scheduling problem with job precedence constraints (U-FJSPJPC). Uncertain processing time and due time are represented as interval grey number and trimmed triangular fuzzy number respectively. A tardiness index indicator is devised to assess the delay extent of grey completion time relative to fuzzy due time. To solve U-FJSP-JPC with minimizing three objectives simultaneously involving interval grey makespan, interval grey total machine workload and average tardiness index, this paper elaborately designs a novel multi-objective multiple-micro-swarm leadership hierarchy-based optimization algorithm (MOM2SLHO). This algorithm adopts a two-vector encoding scheme based on job and operation sequencing and a grey active decoding scheme based on heuristic machine assignment. In MOM2SLHO, the entire search agents are divided into multiple micro-swarms in which each one conducts an independent search based on leadership hierarchy and communicates with others by specific strategies. MOM2SLHO embodies an enhanced external grid archive to store and retrieve non-dominated Pareto optimal solutions. Extensive experiments and statistical analyses demonstrate that the proposed MOM2SLHO algorithm outperforms other well-known and state-of-art algorithms significantly for solving the studied U-FJSP-JPC.

Automated summary

This paper studies an uncertain flexible job shop scheduling problem and proposes a novel multi-objective multiple-micro-swarm leadership hierarchy-based optimization algorithm to solve it, demonstrating its effectiveness through extensive experiments.