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.