Scheduling distributed heterogeneous non-permutation flowshop to minimize the total weighted tardiness

Flowshop scheduling is a critical problem in manufacturing and logistics, where jobs must be processed through a series of machines in a predefined order. In distributed heterogeneous flowshop scheduling, multiple factories with varying processing capacities and resources are involved, making the scheduling problem even more complex. Non-permutation flowshops (NPFS) further complicate this by allowing job sequences to differ across stages, thus significantly expanding the solution space compared to traditional permutation flowshops. Minimizing total weighted tardiness (TWT) is a key objective as it plays a crucial role in avoiding penalties for late deliveries. In this context, this paper addresses a distributed heterogeneous non-permutation flowshop scheduling problem with the objective of minimizing TWT (DHNPFSP_TWT). The problem involves multiple factories operating as NPFS, where job processing times differ across factories for the same production stage. Given the NP-hard nature of the problem, we first proposed a Manne-based mixed-integer linear programming model and a constraint programming (CP) model for small-scale instances. To solve medium- and largescale instances efficiently, we propose a three-phase adaptive evolutionary algorithm (TAE) that combines permutation and non-permutation search strategies, along with a job allocation adjustment phase. The TAE algorithm first finds a permutation solution using NEH3_en and random generation, followed by an adaptive local search and adaptive ruin and recreate algorithm for refinement and mutation. In the non-permutation phase, a greedy insertion strategy and local search techniques explore the solution space. The job allocation adjustment phase reallocates jobs based on the factory with the highest tardiness, and the second and third phases co-evolve to improve solution quality. Additionally, we propose a hybrid algorithm (AE_CP) integrating the strengths of adaptive evolutionary algorithms and CP to further enhance search efficiency. The TAE and the AE_CP are compared against four state-of-the-art heuristics using modified benchmark sets. Experimental results demonstrate that TAE significantly outperforms the competing algorithms in terms of solution quality across various instance sizes. The effectiveness of the three-phase co-optimization strategy, including job transfers, acceleration rules, and the non-permutation phase, is also verified.