A Multiple-Objective Memetic Algorithm for the Energy- Efficient Scheduling of Distributed Assembly Flow Shops

In this paper, a Multiple-Objective Memetic Algorithm (MOMA) is proposed to address the Energy-Efficient Distributed Assembly Permutation Flow-Shop Scheduling Problem (EEDAPFSP) by explicitly exploiting the structural and objective symmetries inherent in the scheduling process, with the dual objectives of minimizing the maximum completion time (makespan) and total energy consumption (TEC). The EEDAPFSP is a complex NP-hard optimization problem in modern sustainable manufacturing that balances production efficiency and environmental sustainability. During the global search phase, a symmetry-preserving dual-search framework is constructed, in which diverse and potential regions in the solution space are explored by symmetrically generating time-dominant product sub-sequences (TDPSs) and energy-dominant product sub-sequences (EDPSs) in the individuals of each iteration, enabling complementary exploration from time- and energy-oriented perspectives. This is accomplished through the incorporation of a variable-weight metric technique and a first product fixed strategy into an estimation distributed algorithm-based hyper-heuristic (EDAHH), so as to maintain a balanced and symmetric probabilistic modeling of decision patterns with respect to the makespan and energy consumption. In the local search phase, two problem-specific designed neighborhood structures are proposed to refine the job sequences corresponding to the TDPS and EDPS in the superior sub-population, effectively reducing both the makespan and TEC. A box-level ε dominance technique based on the crowding distance is proposed for Pareto archive updating. Additionally, an energy-saving strategy is embedded throughout the algorithm, incorporating three mechanisms—job processing delay, machine shutdown and restart control, and speed regulation—to further optimize TEC during both the global and local search phases. Finally, extensive computational experiments are carried out, and the results demonstrate that the MOMA achieves significantly better performance in terms of the inverted generational distance (IGD) and the quality metric ρ compared with state-of-the-art algorithms. The resulting Pareto front of non-dominated solutions provides a comprehensive set of trade-offs between energy consumption and the makespan, offering decision makers flexible and efficient scheduling options.