LLM Policy Induction for Heuristic Search Control: A Trace-Driven ALNS Framework
TL;DR
Experimental results demonstrate that the proposed framework consistently outperforms classical ALNS baselines and several competitive metaheuristic methods in terms of solution quality and convergence speed.
Abstract
Nowadays, large-scale combinatorial optimization problems such as Job Shop Scheduling (JSP), Flexible Job Shop Scheduling (FJSP), and Flow Shop Scheduling (FSP) are widely encountered in manufacturing, logistics, and service systems. Despite substantial progress in metaheuristic frameworks, the design of effective search control policies, including neighborhood selection, move size, acceptance criteria, and diversification strategies, remains heavily reliant on handcrafted rules and domain expertise. In this paper, we propose a trace-driven LLM-controlled Adaptive Large Neighborhood Search (ALNS) framework for scheduling problems, in which large language models (LLMs) are employed exclusively during a policy induction phase to learn high-level search control strategies from historical optimization traces. Rather than evaluating candidate solutions or directly manipulating objective functions, the LLM infers symbolic control policies that map summarized search-state features to ALNS control actions. The induced policy is then integrated into a classical ALNS solver and executed without further LLM involvement. We evaluate the proposed approach on standard benchmark instances of JSP, FJSP, and FSP. Experimental results demonstrate that the proposed framework consistently outperforms classical ALNS baselines and several competitive metaheuristic methods in terms of solution quality and convergence speed.