An Improved Multi-Objective Memetic Algorithm with Q-Learning for Distributed Hybrid Flow Shop Considering Sequence-Dependent Setup Times

Most multi-objective studies on distributed hybrid flow shops that include tardiness-related objectives focus solely on optimizing makespan alongside a single tardiness objective. However, in real-world scenarios with strict contractual deadlines or high penalty costs for delays, minimizing both total tardiness and the number of tardy jobs becomes critically important. This paper addresses this gap by prioritizing tardiness-related objectives while simultaneously optimizing makespan, total tardiness, and the number of tardy jobs. It investigates a distributed hybrid flow shop scheduling problem (DHFSP), which has some symmetries on machines. We propose an improved multi-objective memetic algorithm incorporating Q-learning (IMOMA-QL) to solve this problem, featuring (1) a hybrid initialization method that generates high-quality, diverse solutions by balancing all three objectives; (2) a multi-factory SB2OX crossover operator preserving high-performance job sequences across factories; (3) six problem-specific neighborhood structures for efficient solution space exploration; and (4) a Q-learning-guided variable neighborhood search that adaptively selects neighborhood structures. Based on extensive numerical experiments across 100 generated instances and a comprehensive comparison with four comparative algorithms, the proposed IMOMA demonstrates its effectiveness and proves to be a competitive method for solving the DHFSP.