An Adaptive Co-Evolutionary Memetic Algorithm for a Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup and Transportation Times

Abstract

The hybrid flow shop scheduling problem (HFSP) with unrelated parallel machines (UPMs), sequence-dependent setup times (SDSTs), and inter-stage transportation times has recently emerged as a prominent research topic. To address this scheduling problem with the objective of minimizing the maximum completion time (makespan), this paper first formulates a mixed-integer linear programming (MILP) model based on the machine-position modeling idea. Exact solution analyses on small-scale instances reveal that the strong coupling effect of these triple constraints concentrates the computational bottleneck on the time-consuming proof of optimality, thereby underscoring the strongly NP-hard nature of the investigated HFSP-SDST-T problem. To efficiently solve large-scale instances, a novel adaptive co-evolutionary memetic algorithm (ACMA) is proposed. ACMA adopts a dual-population co-evolutionary framework, where a customized genetic algorithm (GA) is designed for global exploration and a Lévy flight-enhanced particle swarm optimization (PSO) improves local search capability. To dynamically balance exploration and exploitation, a Dynamic Role Allocation (DRA) mechanism is developed to adaptively reassign individuals between the two populations according to their evolutionary states. Moreover, a progressive two-stage memetic enhancement strategy is proposed to overcome premature convergence by sequentially activating deep variable neighborhood search (VNS) and a catastrophe-based diversification strategy, enabling adaptive responses to different stagnation levels. Extensive experiments, including ablation studies, comparisons with benchmark algorithms, and computational complexity analysis, are conducted on small- and large-scale instances. The results show that ACMA consistently obtains the exact optimal solutions obtained from the MILP model for small-scale instances and achieves competitive performance on large-scale complex instances. Furthermore, Wilcoxon signed-rank tests confirm the statistical significance of the performance differences, supporting the reliability of the experimental results.