A multi-objective memetic algorithm for energy-efficient flow shop group scheduling problem with a dynamic speed-scaling mechanism
摘要
This study investigates an energy-efficient flow shop group scheduling problem that incorporates a dynamic speed-scaling mechanism, where both the sequence-dependent setup times and round-trip transportation times are considered. This problem involves three deeply coupled sub-problems: the sequence of groups, the sequence of jobs within each group, and the processing speed of each job on each machine. To the best of our knowledge, this problem has not been previously explored. A mixed integer linear programming model is first formulated to simultaneously minimize makespan and total energy consumption. To solve large-scale instances, we propose a knowledge-driven multi-objective memetic algorithm (MMA) tailored to the problem’s characteristics. The MMA incorporates a knowledge-based initialization heuristic and a speed-down strategy that reduces energy consumption without increasing the makespan. Adaptive global optimization operators are designed for hierarchical exploration. Moreover, a two-stage local search strategy, combining a co-evolutionary mechanism with a speed-up heuristic for critical operations, is introduced to enhance solution quality. A diversity mechanism is also employed to prevent premature convergence. Extensive experiments confirm the effectiveness of the proposed MMA in generating a diverse and high-quality set of Pareto-optimal solutions.