LLM-Assisted Automatic Memetic Algorithm for Lot-Streaming Hybrid Job Shop Scheduling With Variable Sublots

This study addresses the lot-streaming hybrid job shop scheduling problem with variable sublots (LHJSV), inspired by a real-world aircraft tooling shop. A computational model is developed to represent the complex scheduling processes of the tooling shop. To solve this problem, we propose an automatic memetic algorithm enhanced by a heuristic designed with the assistance of a large language model (LLM). The approach is designed as follows: first, a memetic computing framework with automated algorithmic design is proposed for LHJSV. Second, a cooperative evolutionary heuristic framework based on problem decomposition is introduced, enabling the LLM to comprehend the LHJSV characteristics and generate feasible algorithms. Third, problem-specific prompts for LHJSV are carefully designed to guide the LLM. To evaluate the effectiveness of the proposed method, 20 benchmark instances derived from the Taillard dataset and a real-world case involving 575 operations are utilized. The proposed algorithm is compared against three swarm-based algorithms, an end-to-end method, and an LLM-based algorithm. Experimental results demonstrate that our method outperforms the compared algorithms on 85% of benchmark instances and exhibits significant superiority in real-world scenarios.