Multi-Population Backtracking Search Algorithm for Bi-Objective Multi-Product Multi-Stage Batch Scheduling with Fuzzy Processing Times: Minimizing Makespan and Maximizing Customer Satisfaction

This paper investigates the uncertain multi-product batch scheduling problem (UMBSP) with two conflicting objectives: fuzzy minimum makespan and maximum mean customer satisfaction level. A customer satisfaction criterion associated with flexible due dates is introduced to characterize the imprecise and flexible nature of scheduling information in practical manufacturing environments. To solve the multi-objective UMBSP, a novel discrete multi-objective multi-population backtracking search algorithm (MOMPBSA) is proposed. The improved discrete backtracking search algorithm integrates different evolutionary mechanisms into multiple populations to achieve a better balance between convergence accuracy and convergence speed. In addition, effective heuristic rules are employed to generate high-quality initial solutions and enhance search efficiency. Furthermore, problem-specific local search strategies are developed to further improve the accuracy and diversity of the obtained non-dominated solutions. Extensive computational experiments and simulation results demonstrate that the proposed improvement strategies significantly enhance the performance of MOMPBSA. Moreover, the ablation study demonstrates that all the proposed strategies contribute to improving the quality of the obtained Pareto solutions. Compared with two representative multi-objective scheduling optimization algorithms, the proposed MOMPBSA obtains approximate solutions in only two small-scale examples and the best solutions in all other examples, and its advantage becomes more pronounced as the instance scale increases, which verifies its effectiveness and superiority.