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.

• Publication year

  2025

• Venue

  OPTIMA

• Publication date

  2025-10-16

• Fields of study

  Not labeled

• Identifiers
  DOI 10.1109/ICOA66896.2025.11236888
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-Objective Production Rescheduling: A Systematic Literature Review

  2024cited by this paper
• A Q-Learning based NSGA-II for dynamic flexible job shop scheduling with limited transportation resources

  2024cited by this paper
• An improved NSGA-II with local search for multi-objective integrated production and inventory scheduling problem

  2023cited by this paper
• Nondominated sorting genetic algorithm-II with Q-learning for the distributed permutation flowshop rescheduling problem

  2023cited by this paper
• A hybrid multi-objective evolutionary algorithm for solving an adaptive flexible job-shop rescheduling problem with real-time order acceptance and condition-based preventive maintenance

  2022cited by this paper
• A Comprehensive Review on NSGA-II for Multi-Objective Combinatorial Optimization Problems

  2021cited by this paper
• Multi-objective two-echelon location-distribution of non-medical products

  2020cited by this paper
• Optimization of Dynamic and Multi-Objective Flexible Job-Shop Scheduling Based on Parallel Hybrid Algorithm

  2018cited by this paper
• A hybrid multi-objective immune algorithm for predictive and reactive scheduling

  2016cited by this paper
• On using the hypervolume indicator to compare Pareto fronts: Applications to multi-criteria optimal experimental design

  2015cited by this paper
• Pareto Local Search Algorithms for Anytime Bi-objective Optimization

  2012cited by this paper
• A fast and elitist multiobjective genetic algorithm: NSGA-II

  2002cited by this paper

• No citing papers are available for this paper.