Automated Scheduling Heuristic Generation and Evaluation via Large Language Model

What the paper says

Scheduling is pivotal in manufacturing, significantly impacting production efficiency, cost optimization, and delivery performance. Due to the complexity of modern manufacturing systems, heuristics are widely adopted for their computational efficiency and interpretability. However, crafting effective heuristics is labor-intensive, necessitating substantial domain expertise and iterative trial-and-error processes. Leveraging the advanced capabilities of Large Language Models (LLMs) in code generation and natural language processing, this paper proposes a Language Scheduling Heuristic (LSH) that harnesses pre-trained LLMs to automatically construct scheduling heuristics without human intervention. The key innovation of LSH lies in its integration of three core components: 1) an LLM module that generates candidate heuristics through specific prompts; 2) an evaluation module that assesses heuristic performance based on a predefined evaluation dataset; and 3) an evolutionary module grounded in an evolutionary paradigm to effectively search for promising heuristics. This synergy enables the automated discovery of high-quality heuristics. On benchmarks for Flow Shop Scheduling Problem (FSP), Job Shop Scheduling Problem (JSP), and Open Shop Scheduling Problem (OSP), our framework demonstrates a powerful capability for automated heuristic generation, leading to solutions that outperform established methods.