MNATS: A Multi-Neighborhood Adaptive Tabu Search Algorithm for the Distributed No-Wait Flow Shop Scheduling Problem

The Distributed No-Wait Flow Shop Scheduling Problem (DNWFSP) arises in various manufacturing contexts, such as chemical production and electronic assembly, where strict no-wait constraints and multi-factory coordination are required. Solving the DNWFSP involves determining the allocation of jobs to factories and the no-wait processing sequences within each factory, making it a highly complex combinatorial problem. To address the limitations of existing methods—including poor initial solution quality, limited neighborhood exploration, and a tendency to converge prematurely—this paper proposes a Multi-Neighborhood Adaptive Tabu Search Algorithm (MNATS). The MNATS integrates a balance–lookahead NEH initializer (BL-NEH), an adaptive neighborhood local search (ANLS) strategy, and an Adaptive Tabu-Guided Perturbation (ATP) strategy. Experimental results on multiple benchmark instances demonstrate that MNATS algorithm significantly outperforms several state-of-the-art algorithms in terms of solution quality and robustness.