A memetic algorithm with large language model for multi-objective flexible job shop scheduling with variable speed

This paper studies the multi-objective flexible job shop scheduling problem with variable speed (MFJSP-S), where each operation selects a machine and a speed that jointly determine processing time and energy. The goal is to minimize makespan and total energy consumption (TEC), including processing and idle energy. We first present a MILP model and validate the formulation and evaluation pipeline via exact solving on small instances. For larger instances, we propose LLMMA, an LLM-assisted memetic algorithm based on non-dominated sorting. LLMMA integrates hybrid initialization with problem-tailored neighborhoods across operation sequencing, machine assignment, and speed adjustment. A budgeted intensification scheme selects local-search candidates using Pareto-layer priority and a KNN-based diversity score, balancing convergence and distribution. Following the Evolution of Heuristics (EoH) paradigm, we use an LLM to generate executable local-search strategy code, which is injected online into the memetic loop and iteratively refined using HV-based feedback on benchmark instances. Experiments on MK and DP benchmarks using HV, IGD, and Spread, together with Friedman tests, show that LLMMA generally delivers better trade-off fronts than several state-of-the-art algorithms under equal time budgets.