An Improved Hybrid NSGA-II Integrating Pareto-based VND for Multi-objective Rescheduling of Blocking Flow Shops

This paper addresses a bi-objective rescheduling problem in mixed blocking permutation flow shops with dynamic job arrivals, aiming to minimize both the total weighted waiting time and the average completion time deviation. A hybrid approach is proposed, combining NSGA-II with a novel Pareto-based Variable Neighborhood Descent (PB-VND) applied as a post-optimization step. Unlike classical local search, PB-VND explores sets of non-dominated neighbors in parallel, aiming to improve the quality of the Pareto front while preserving solution diversity. The current front is continuously updated at each iteration to guide the search and avoid revisiting solutions already dominated by previously discovered neighbors. Experimental results show consistent improvements in mean hypervolume across all evaluated rescheduling instances. Moreover, 19.78% of the intermediate Pareto fronts were enriched with new non-dominated solutions through this post-processing step, demonstrating the effectiveness of PB-VND in enhancing multi-objective scheduling under dynamic conditions. Potential research directions include integrating PB-VND within the evolutionary loop of NSGA-II and extending its application to other combinatorial optimization problems.