NS4S: Neighborhood Search for Scheduling Problems Via Large Language Models

1 Introduction

Job shop scheduling problem (JSP) is one of the most fundamental and extensively studied scheduling problems in combinatorial optimization, with significant applications in modern intelligent manufacturing systems and transportation logistics. The problem involves scheduling a set of jobs J = {J1, J2, ..., Jn}, where each job Ji consists of Ni operations

∗Corresponding author

(Oi1,Oi2, ...,OiNi ) that must be processed sequentially on a set of machines M = {M1,M2, ...,Mm} [Iklassov et al., 2023]. Each operation Oij must be processed on a specified machine with processing time PTij. In the flexible job shop scheduling problem (FJSP), each operation can be processed on any machine from its candidate machine set Mij ⊆ M with machine-dependent processing time PTijk [Yuan et al., 2023]. For FJSP with sequence dependent setup time (FJSPSDST), each operation requires setup time STijk before processing, which depends on its machine predecessor [Oddi et al., 2011]. All processing times and setup times are predetermined, and the objective is to minimize the maximum completion time (makespan) of all jobs.

The optimization of JSPs focuses on determining optimal operation sequences and processing times across multiple machines while considering various operational constraints. These scheduling problems are crucial in production planning and control, as they encompass complex aspects of resource allocation, task sequencing, and process optimization. Effective scheduling algorithms can significantly impact manufacturing performance by improving production efficiency, reducing operational costs, and minimizing production cycles. While the classical JSP focuses on fixed machine assignments, its variants such as FJSP and FJSP-SDST introduce additional complexity through flexible machine routing and sequence-dependent setup considerations, making them particularly relevant for modern manufacturing environments.

These scheduling problems belong to the class of NPhard optimization problems, where computational complexity grows exponentially with problem size [Tian et al., 2024]. While exact methods can guarantee optimal solutions, they become computationally intractable for large-scale instances, rendering them impractical for industrial applications. Although rule-based heuristics can rapidly generate feasible solutions, they often fail to provide high-quality solutions [Guo et al., 2024]. Metaheuristics have thus emerged as the predominant research direction in scheduling optimization, offering an effective balance between solution quality and computational efficiency [Yao et al., 2024].

Large Language Models (LLMs) offer several compelling advantages for addressing scheduling problems. Their sophisticated reasoning capabilities enable comprehensive understanding of complex scheduling constraints and their intricate interactions. Furthermore, LLMs excel at learning from historical experiences and identifying patterns, capabilities that are essential for developing effective heuristic search strategies. Their ability to process and interpret natural language descriptions of problems and objectives facilitates more flexible and adaptable algorithm design. These characteristics position LLMs as particularly promising tools for addressing challenging scheduling optimization problems.

Recent research has demonstrated the potential of Large Language Models in automating algorithm generation for combinatorial optimization problems [Romera-Paredes et al., 2024; Liu et al., 2024a; Liu et al., ; Zeng et al., ]. However, current LLMs-based methodologies exhibit several critical limitations in addressing scheduling problems: (1) The predominant approach of generating complete algorithms directly [Romera-Paredes et al., 2024; Liu et al., 2024a; Liu et al., ; Zeng et al., ; Ye et al., 2024] often proves inadequate for problems with complex constraints such as JSP, failing to maintain solution quality; (2) The inherent hallucination phenomenon in LLMs may produce unreliable or invalid outputs, potentially compromising algorithmic performance;

To address these limitations, we propose a novel LLMsbased neighborhood search framework that synergistically combines the strengths of LLMs and traditional local search methodologies. Instead of attempting to generate complete algorithms directly, our approach utilizes LLMs to guide neighborhood selection in local search, thereby maintaining solution feasibility while enhancing solution quality. Additionally, we introduce a verification evolutionary framework that systematically validates LLMs-generated suggestions and provides structured feedback, analogous to gradient information in deep learning, enabling progressive improvement in heuristic generation. Furthermore, the proposed LLMs-guided neighborhood search framework (NS4S) can be directly applied to other metaheuristics or even extended problems without manual parameter tuning, demonstrating strong generalization capability.

2 Literature Review

2.1 Heuristic Methods

Traditional methods for solving the JSP can be classified into heuristics and metaheuristics. Heuristics gradually construct a complete solution from an empty one that does not contain any operations, whereas metaheuristics usually perform improvement based on a complete feasible solution. In tackling the job shop scheduling problem, heuristics mostly rely on priority dispatching rules such as shortest processing time (SPT), first in first out (FIFO), most work remaining (MWKR) [Sels et al., 2012], and so on. For JSP, prominent metaheuristic approaches include evolutionary algorithm [Pan et al., 2021], particle swarm algorithm [Fontes et al., 2023], and memetic algorithm [Sun et al., 2023a]. In the context of FJSP, popular algorithms include the Jaya algorithm [Caldeira and Gnanavelbabu, 2019], hybrid search algorithm [Xie et al., 2023], and genetic algorithm [Sun et al., 2023b]. For solving FJSP-SDST, common strategies involve hybrid algorithm [Oddi et al., 2011], tabu search [Gonz´alez et al., 2013], and genetic algorithm [Gonz´alez et al., 2013].

2.2 Learning-basedMethods

With the development of machine learning theory, the methods based on deep learning have demonstrated their ability to tackle complex problems in the field of computer vision and combinatorial optimization. Chen et al. [2020] proposed a self-learning genetic algorithm by integrating reinforcement learning into genetic algorithms. Their algorithm can adaptively adjust the execution frequency of the Sarsa and Q-learning algorithms based on the features of the current search region to guarantee the quality of solutions. In order to reduce the reliance on expert knowledge for priority dispatching rules, Zhang et al. [2020] introduced an end-to-end deep reinforcement learning approach, which involves utilizing a graph neural network to extract features from incomplete solutions rather than commonly using complete feasible solutions. Finally, the policy network model outputs a dispatching rule suitable for the current state. Moreover, experimental results showed that their method also exhibits good generalization capabilities. Zhang et al. [2023] combined deep reinforcement learning with multi-agent systems to propose the deepMAG framework. In deepMAG, each agent has its own optimization objective. Additionally, neighboring agents can collaborate with each other by executing a shared action. Experimental results indicate that this collaborative approach can improve the algorithm's efficiency. Yuan et al. [2023] proposed a deep reinforcement learning-based method by utilizing graph-heterogeneous networks for feature embedding and modeled JSP as a standard Markov decision process.

2.3 Automatic Heuristic Design

Traditional automated heuristic design is commonly referred to as Hyper-heuristics, which typically involve the combination of various simple heuristic rules or select the best performing heuristic from a predefined set [Ye et al., 2024]. In recent years, significant advancements have been made in natural language generation using LLMs. Consequently, some researchers have attempted to apply LLMs to generate entire algorithms and codes. DeepMind team [Romera-Paredes et al., 2024] utilized a pre-trained large language model to generate heuristics for the cap set problem and the online packing problem, which led to new constructions in the cap set problem, breaking previous world records. In order to tackle black-box optimization problems, Liu et al. [2024c] embedded LLMs into a Bayesian optimization framework, enabling the LLMs to generate and evaluate feasible solutions based on context.

However, when the problem constraints exhibit high complexity, this direct generation of complete algorithms cannot guarantee the quality of solutions. Zhuang et al. [2024] employed LLMs to generate the cost function for specific tasks and integrated it with A* algorithm to effectively prune the search tree, achieving a trade-off between exploration and exploitation. Liu et al. [2024a] utilized LLMs to generate several heuristics for specific tasks and enhance the generated heuristics through selection, crossover, and mutation operations. To further improve the performance of heuristics, they performed parameter tuning and strategy optimization on the generated heuristics at different stages.

Algorithm 1 The main framework of the NS4S algorithm

Input: JSP Instance

Output: the best solution found so far S∗

• 1: S∗ ←S ← Init(),
• 2: f ∗ ←S.makespan
• 3: while stopping condition is not met do
• 4: move(o∗ , k) ←LLMGuidedNeighborEval(S)
• /*Section 3.2*/
• 5: S ←- S ⊕move(o∗ , k)
• 6: f ←S.makespan
• 7: WeightUpdateByLLMs() /*Section 3.3*/
• 8: if f ∗ > f then
• 9: S∗ ← S, f ∗ ← f
• 10: end if
• 11: end while
• 12: Return S∗

3 LLMs-guided Neighborhood Search

3.1 Overall Framework

In this section, we present a comprehensive framework that leverages LLMs to guide neighborhood search in solving classical scheduling problems. The framework's primary innovation lies in its utilization of LLMs to direct the neighborhood search process through dynamic weight adjustments, effectively steering the search towards promising regions of the solution space.

The main framework of our algorithm, detailed in Algorithm 1, comprises three fundamental components:

• An LLMs-guided neighborhood evaluation strategy that employs operation weights to assess move quality
• A verification-based evolutionary framework (VeEvo) that generates and refines high-quality weight adjustment heuristics
• A neighborhood search process that integrates these components to systematically explore the solution space

The algorithm begins by constructing an initial feasible solution through random assignment of operations to candidate machines with uniform probability (line 1). Solutions S∗ and S represent the global best and current solutions respectively, with their corresponding objective values denoted by f ∗ and f (line 2). The algorithm then iteratively applies a series of moves to improve solution quality until meeting the termination criterion (lines 3-11).

Specifically, the proposed LLMs-guided neighborhood evaluation (LNE) strategy evaluates potential neighborhood moves of the incumbent solution to identify the most promising move (line 4). The selected move is then executed to obtain a new solution (line 5), where move(o∗ , k) denotes the relocation of operation o∗ to position k. Subsequently, the weights of affected operations are updated based on the resulting changes in makespan (line 7), with the update heuristic generated by the proposed VeEvo framework. The bestfound solution is updated when improvements are discovered (lines 8-10).

3.2 Neighborhood Structure and Evaluation

The design of neighborhood structure and evaluation strategy plays a pivotal role in determining the effectiveness of neighborhood search algorithms. While we adopt the established neighborhood structure from Ding et al. [2019], we propose a novel approach to performmove evaluation. Traditional local search methods typically evaluate all feasible neighborhood moves and select the one yielding the best evaluation value. Although this greedy strategy facilitates rapid convergence, it frequently leads to entrapment in local optima. To overcome this limitation, we introduce an LLMs-guided neighborhood evaluation (LNE) strategy that incorporates dynamically adjusted operation weights, learned through LLMs evolution, to guide the search process more effectively.

Consider a sequence of operations O1,O2, . . . ,Ok processed on the same machine in JSP. When evaluating the insertion of operation O1 after operation Ok, the evaluation metric is computed as follows (the move with the best F will be selected and performed at next iteration):

Here, W(i) represents the LLMs-guided weight component for operation i, pi denotes its processing time, while Ri and Qi indicate the earliest start time and the length of the longest path from operation i to the terminating operation prior to the move, respectively. The function CLIP(x, 1) constrains values to the interval [0,1], ti counts the iterations since operation i was last moved, and N represents the mean operation count across all jobs. To enhance exploration, rand(N) generates a random integer in the range [1,N]. The weight wi, initialized to 0, is dynamically updated using heuristics derived from our VeEvo framework.

This LLMs-guided evaluation strategy has several significant advantages: (1) It allows the search to escape from local optima by dynamically adjusting operation weights based on LLMs-generated heuristics. (2) The weights provide a form of learning that captures problem-specific knowledge through the search process. (3) The randomization factor helps to maintain diversity in the search process while still being guided by the learned weights.

According to Equations (1) and (2), the weights of operations can significantly impact move evaluation and influence the selection of neighboring moves. The VeEvo framework is employed to generate high-quality weight adjustment strategies that can effectively guide the search towards promising regions.

3.3 LLMs-basedWeight Adjustment

In order to employ a robust mechanism for weight adjustment to effectively utilize LLMs for search guidance, we introduce a verification-based evolutionary framework (VeEvo) for generating high-quality weight adjustment strategies. A fundamental challenge in leveraging LLMs for this purpose stems from their susceptibility to hallucination [Xu et al., 2024; Banerjee et al., 2024; Liu et al., 2024b; Li et al., 2024], which can result in unreliable or counterproductive outputs. While existing LLMs-based evolutionary algorithms often assume output reliability, this assumption may lead to the exploration of unpromising search spaces. Our VeEvo framework addresses this challenge through a systematic approach to verification and evolutionary refinement.

The architecture of VeEvo is illustrated in Figure 1. The framework's effectiveness stems from three key mechanisms: (1) learning-based adaptation that enables continuous strategy refinement through evolutionary feedback, (2) systematic verification that ensures the reliability of LLMsgenerated strategies through empirical validation, and (3) dynamic knowledge base optimization that facilitates continuous learning through systematic feedback mechanisms and comprehensive experience integration.

VeEvo adopts a methodology analogous to genetic programming in evolutionary computation. Following Romera et al. [2024], the framework evolves individual heuristic methods rather than problem solutions as in traditional genetic programming. The framework comprises the following essential components:

Initialization: The population is initialized through LLMs-generated heuristics based on carefully crafted prompts containing task descriptions, heuristic definitions, and illustrative examples. Generated heuristics undergo validation to eliminate invalid candidates, followed by evaluation and ranking based on their fitness values.

Suggestion Generation: The framework processes heuristic codes sequentially through the LLMs to generate natural language suggestions, which serve as gradient-like information to guide evolutionary crossover. To mitigate the impact of LLMs' uncertainty, suggestions for low-performing individuals (bottom 50% by fitness) are labeled as "Unlabeled" (e.g., "# Unlabeled Suggestion: [Unlabeled] Increase weight for moved operations, decrease for unmoved with conditions favoring current optimization goal"). These Unlabeled suggestions undergo additional verification.

Verification Process: Low-performing individuals and their associated suggestions are processed by the LLMs to generate improved heuristics. The new heuristics undergo evaluation and comparison with their predecessors. Superior performance results in a "Good suggestion" label, while inferior performance yields a "Bad suggestion" label (e.g., "# Good Suggestion: [High Quality] Increase weight for moved operations..."). These quality indicators inform subsequent evolutionary operations.

Crossover Operation: The LLMs generates offspring code based on parent codes, suggestions, and their corresponding quality labels. Rather than discarding ineffective suggestions, they are retained with "bad suggestion" labels, as they provide valuable negative gradient information for the learning process.

Memory Mechanism: VeEvo maintains an evolving knowledge base through continuous reflection on suggestion effectiveness. The framework accumulates expertise such as "Penalize stagnation and prioritize diverse solutions. Remember, non-negative weights are crucial for algorithm stability". The LLMs updates this knowledge base by processing new suggestions and their quality labels alongside existing memories, with "bad suggestion" labels reducing the acceptance probability of similar ineffective strategies.

Mutation Operation: The framework leverages the bestperforming individual and accumulated memories to guide the LLMs in generating diverse variants. These new individuals, combined with crossover-generated offspring, form the population of the next generation.

During training, VeEvo iteratively executes these processes to enhance population quality, using average objective values across randomly generated instances as fitness metrics. In the testing phase, the best-evolved heuristic is integrated directly into Algorithm 1 (Line 7), eliminating the need for further LLMs interaction during execution.

4 Experiments and Analysis

4.1 Experimental Protocol

Benchmark Datasets: To evaluate the efficacy of the proposed NS4S algorithm, we conducted comprehensive experiments across three classical scheduling problems: JSP, FJSP, and FJSP-SDST. For JSP, we utilized the TA and DMU benchmark instances, comprising 160 instances that represent the most challenging publicly available test cases. For FJSP, we employed the BR, HU, and Vdata benchmark suites, encompassing 169 diverse instances. For FJSP-SDST, we employed the SDST-Hudata benchmark set, containing 20 instances of varying complexity.

Baseline Algorithms: Our comparative analysis encompasses three categories of baseline algorithms:

1) Priority Dispatch Rules (PDRs): Following Sels et al. [2012], we selected widely-adopted heuristics including Shortest Processing Time (SPT), Minimum Ratio of Flow Due Date to Most Work Remaining (FDD/WKR), Most Work Remaining (MWKR), Most Operations Remaining (MOPNR), First In First Out (FIFO), and machine with Earliest End Time (EET).

2) State-of-the-art Metaheuristics: We incorporated advanced algorithms including Improved Jaya Algorithm (IJA) [Caldeira and Gnanavelbabu, 2019], Regular GA (RegGA) [Rooyani and Defersha, 2019], Two Stage Genetic Algorithm (2SGA) [Rooyani and Defersha, 2019], Self-learning Genetic Algorithm (SLGA) [Chen et al., 2020], Iterative Flattening Search (IFS) [Oddi et al., 2011], Tabu Search (TS) [Gonz´alez et al., 2013], Genetic Algorithm (GA) [Gonz´alez et al., 2013], and Memetic Algorithm (MA) [Gonz´alez et al., 2013].

3) Learning-based Methods: We included contemporary approaches such as Learning to Dispatch (L2D) [Zhang et al., 2020], Reinforced Adaptive Staircase Curriculum Learning (RASCL) [Iklassov et al., 2023], and deep reinforcement learning-based methods from [Yuan et al., 2024; Song et al., 2022; Lei et al., 2022], denoted as EYRL, WSRL, and LKRL, respectively.

Experimental Settings: Our implementation combines Python for the VeEvo framework and C++ for the neighborhood search algorithm, executed on a single CPU E5-2697v3. To ensure fair comparison with Ye et al. [2024], we configured VeEvo with a population size of 10 and the maximum evaluations of 100. We imposed cutoff times of 10 seconds for JSP and FJSP, and 30 seconds for FJSP-SDST.

To mitigate implementation-dependent variations, we adopted the computer-independent CPU time normalization methodology from Sels et al. [2024]. Reference results for JSP were cited from Iklassov et al. [2023] and Yuan et al. [2023], while FJSP and FJSP-SDST results were obtained fromYuan et al. [2024] and Gonzalez et al. [2013].

For performance evaluation, we employed the relative percentage deviation (RPD), also known as the optimality gap, following Yuan et al. [2023]:

where C ′max represents the best makespan achieved by the reference algorithm, and C ∗max denotes the optimal or bestknown solution. In the tables, the best performance across all algorithms are indicated in bold, while asterisks (*) denote new upper bounds established by our approach.

4.2 Experimental Results

JSP Performance Analysis: As evidenced in Table 1, our approach demonstrates substantial improvement over existing methods. While RASCL achieves a notable average gap of 10.46% on the TA instances, surpassing other rule-based heuristics and deep learning methods, NS4S significantly reduces this gap to 1.35%. This improvement indicates the effectiveness of our LLMs-based neighborhood approach in navigating complex solution spaces.

The integration of LLMs capabilities proves particularly effective, as demonstrated by the performance on DMU instances (Table 2). The GPT-4-based variant achieves an average gap of 4.55%, substantially outperforming RASCL's 18.85%. Notably, this improvement is achieved without explicit weight update direction instructions in the initial prompts, highlighting VeEvo's ability to learn effective strategies through self-verification and evolutionary refinement.

FJSP Performance Analysis: Results presented in Table 3 reveal the balanced performance characteristics of our approach. While genetic programming-based algorithms achieve high solution quality at the cost of substantial computation time, and rule-based heuristics offer rapid but suboptimal solutions, NS4S strikes an optimal balance. It outperforms reinforcement learning approaches like EYRL, WSRL, and LKRL in terms of solution quality while maintaining comparable computational efficiency. The GPT-4 variant demonstrates superior solution quality across all benchmark sets, though with moderately increased computation time.

FJSP-SDST Performance Analysis: The results in Table 4 underscore the robustness of our approach in handling complex constraints. NS4S not only surpasses the Memetic Algorithm (MA) in terms of both solution quality and computational efficiency but also establishes nine new upper bounds across the benchmark instances 1 . Specifically, the GPT-3.5 variant established records on instances la06, la07, la09, la10, and la12, while the GPT-4 variant achieved breakthroughs on la06, la09, la11, la13, la14, and la15.

4.3 Analysis and Discussion

To evaluate the importance of each algorithmic component, we conducted ablation studies on the four most challenging instances from the SVW benchmark. We compared NS4S against variants lacking specific components: verification mechanism (w/o verification), LLMs-guided neighborhood evaluation (w/o LNE), VeEvo framework (replaced with ReEvo [Ye et al., 2024]), and expert-designed weight adjustment heuristics (Human version).

1 https://github.com/Zoommy/NS4S

As illustrated in Figure 2, the variant without LNE exhibits significantly slower improvement rates, highlighting the crucial role of LLMs-guided neighborhood evaluation in efficient solution space exploration. While the variants without verification, without VeEvo, and the Human version show similar convergence patterns, they consistently achieve inferior solutions compared to the complete NS4S framework. The full NS4S implementation's ability to obtain superior solutions with reduced computational time validates the synergistic benefits of integrating these components.

5 Conclusion

This paper presents a novel LLMs-based neighborhood search method that leverages Large Language Models to address classical scheduling problems including JSP, FJSP, and FJSP-SDST. Our primary contributions encompass three key innovations: First, we introduce an LLMs-guided neighborhood evaluation strategy that employs dynamic weight adjustments to effectively guide the search process through complex solution spaces. Second, we develop a verificationbased evolutionary framework (VeEvo) that systematically mitigates the impact of LLMs hallucinations through rigorous validation of generated heuristics. Third, we demonstrate how the integration of LLMs-generated weight adjustment strategies can effectively steer the search towards promising regions of the solution space.

Comprehensive experimental evaluation across three classical scheduling problems, encompassing 349 benchmark instances, demonstrates the superiority of our approach over existing state-of-the-art methods. For the Job Shop Scheduling Problem, our algorithm achieves a remarkable reduction in average optimality gap from 10.46% to 1.35% on Taillard's instances. In the context of FJSP, we further reduce the average optimality gap from 13.24% to 0.05% on Brandimarte's instances. Most notably, for the FJSP-SDST, our approach establishes nine new upper bounds.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 62472189, 62402191, and 62202192, the Special Project for Knowledge Innovation of Hubei Province under Grant 2022013301015175, and Interdiciplinary Research Program of Hust 5003300129.