PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic programming via large language models with population self-evolution for dynamic fuzzy job shop scheduling problem

Jin Huang, Qihao Liu, Xinyu Li, Liang Gao, Yue Teng

arXiv:2410.22657v2cs.NE

TL;DR

DFJSSP scheduling must contend with fuzzy processing times and HDRs that can be scenario-sensitive. This paper proposes LLM-based SeEvo with a teacher-student mechanism that uses historical time deviations to generate robust HDRs. The authors report advantages over established methods in static generalization and most dynamic fuzzy cases.

  • Problem

    DFJSSP involves fuzzy processing times that leave decision-makers without actual-time information, while HDR performance is scenario-sensitive and customization often relies on expert knowledge.

    Source: §I · p. 1

  • Method

    SeEvo uses LLM-based population self-evolution and a teacher-student mechanism in which the student learns from historical deviations between planned and actual processing times.

    Source: §I · p. 2, §III · p. 4

  • Results

    SeEvo outperforms commonly used HDRs, GP, GEP, and DRL methods in static generalization, shows substantial advantages in most dynamic fuzzy cases, and notable advantages for tardiness optimization.

    Source: §VI · p. 12

  • Takeaways & Limitations

    The authors conclude that SeEvo generalizes across unseen and dynamic DFJSSP scenarios while addressing fuzzy impacts through historical deviation trends.

    Source: §I · p. 2, §VI · p. 12

    The study uses costly external LLM API calls and only a single HDR in dynamic cases, which limits performance relative to static cases.

    Source: §VI · p. 12

Abstract

from arXiv · show

Heuristic dispatching rules (HDRs) are widely used for solving the dynamic fuzzy job shop scheduling problem (DFJSSP). However, their performance is highly sensitive to specific scenarios and often necessitates expert customization. To overcome this, automated design methods like genetic programming (GP) and gene expression programming (GEP) have been proposed. Despite their success, these methods face challenges, such as high randomness in the search process. Recently, the combination of large language models (LLMs) with evolutionary algorithms has opened new possibilities for prompt engineering and automated algorithm design. To improve the ability of LLMs in automatic HDR design, this paper introduces a novel population self-evolutionary (SeEvo) framework, which draws inspiration from the self-reflective design strategies employed by human experts. Notably, this framework employs a novel teacher-student learning mechanism, allowing the LLM (student) to generate robust HDRs. Guided by a teacher model with complete knowledge of actual processing times, the student learns to infer fuzzy uncertainties from historical deviations, enabling it to effectively anticipate and adapt to fuzzy impacts. Experimental results demonstrate that SeEvo significantly outperforms GP, GEP, deep reinforcement learning (DRL) methods, and more than ten commonly used HDRs from the literature, particularly in previously unseen and dynamic scenarios.

I. INTRODUCTION

Dynamic uncertainty makes DFJSSP difficult to solve with rules that need scenario-specific customization. The paper motivates LLM-based evolutionary design as a way to generate robust HDRs and improve their generalization.

A. Related Works of Fuzzy Job Shop Scheduling Problem

  • Exact methods can be computationally infeasible on large static JSSP instances, while metaheuristics are used for larger problems and face challenges in highly dynamic settings.The related work also identifies scenario sensitivity and expert customization as limitations of HDRs.Source: §I · p. 1, A. Related Works of Fuzzy Job Shop… · p. 2

I. INTRODUCTION

  • Dynamic events and fuzzy processing times make real-world scheduling nonstatic, while HDR design has traditionally required expert knowledge and trial-and-error.GP and GEP automate HDR discovery, but the related work notes challenges with search-space size and generalization to unseen instances.Source: §I · p. 1, A. Related Works of Fuzzy Job Shop… · p. 2

A. Related Works of Fuzzy Job Shop Scheduling Problem

  • HDRs are valued for responsiveness, while DRL can learn scheduling policies through interaction and is described as suited to fast-paced settings.The related work distinguishes rule-selection DRL from end-to-end DRL and notes that end-to-end approaches require manual reward, action-space, and state-representation design.Source: §I · p. 1, A. Related Works of Fuzzy Job Shop… · p. 2

I. INTRODUCTION

  • DFJSSP methods often react to processing-time deviations as dynamic events rather than proactively designing robust schedules under incomplete information.The paper frames this as a decision-making problem in which uncertainty effects must be inferred and anticipated.Source: §I · p. 2
  • LLM-based SeEvo is proposed to design HDRs for DFJSSP, with robustness learned from planned-versus-actual processing-time gaps and evaluation against HDRs, GP, GEP, and DRL.The authors report superior generalization across unseen and dynamic DFJSSP.Source: §I · p. 2

B. Automatic Algorithm Design with LLMs

LLMs expand automatic algorithm design from selecting predefined components to generating heuristic logic. This paper addresses the limited application of LLM-based approaches to complex DFJSSP and their slow iterative evolution.

B. Automatic Algorithm Design with LLMs

  • LLMs can generate a heuristic’s internal logic, moving hyper-heuristic design beyond selecting among predefined components.Traditional GP and GEP evolve algorithms from a predefined component set, whereas LLM-based design may require only a function signature.Source: B. Automatic Algorithm Design with LLMs · p. 3
  • LLM-evolution methods have been applied to combinatorial optimization, including TSP and online BPP, but their use in more complex DFJSSP remains limited.The related work describes LLM-based heuristic evolution for TSP and online BPP.Source: B. Automatic Algorithm Design with LLMs · p. 3
  • ReEvo’s reflection strategies were developed for static problems and do not distinguish training from test sets, while DFJSSP adds fuzzy times and dynamic events.The paper identifies population self-evolution as a further aspect not fully explored by ReEvo.Source: B. Automatic Algorithm Design with LLMs · p. 3
  • Lengthy LLM-based evolution, typically taking tens of minutes, can be impractical when workshop conditions change within minutes.The proposed framework introduces a knowledge-distillation perspective for rapid response.Source: B. Automatic Algorithm Design with LLMs · p. 3

III. FRAMEWORK OF LANGUAGE-HEURISTIC-BASED DFJSSP

The framework separates self-evolution from online application and trains an LLM-generated HDR population in a simulation environment. It uses historical processing-time deviations and reflection strategies to improve generated rules.

III. FRAMEWORK OF LANGUAGE-HEURISTIC-BASED DFJSSP

  • The framework has self-evolution and online-application stages, with a job-shop simulation handling random arrivals, fuzzy processing times, and machine breakdowns.During self-evolution, incoming-job statistics inform LLM-generated HDRs used for job sequencing.Source: §III · pp. 3–4
  • A teacher-student mechanism gives the simulation environment access to actual processing times while the LLM student observes planned times and other state information.The student uses historical deviations to anticipate fuzzy uncertainty.Source: §III · p. 4
  • The ema feature tracks historical deviation trends and feeds them into the LLM prompt so generated HDRs can account for future time fluctuations.The smoothing update uses the latest relative deviation and an adjustment coefficient; the updated factor maps to time-related metrics.Source: §III · p. 4
  • After self-evolution, the online phase applies the best generated HDRs; the reported experiment uses 20 selected training cases and gives a 100-job, 20-machine example solved within 40 seconds.The framework reports producing high-quality HDRs after one self-evolution iteration.Source: §III · p. 4

IV. LANGUAGE-HEURISTIC-BASED POPULATION SELF-EVOLUTION METHOD

  • SeEvo improves population exploration through individual co-evolution, individual self-evolution, and collective evolution reflection strategies.Its language-driven process uses LLMs to generate guiding prompts and heuristic code segments that are iteratively refined.Source: §III · p. 4, §IV · p. 4

A. Individual Encoding and Initialization

SeEvo initializes a population of LLM-generated HDR code fragments and iteratively evaluates and evolves them. Its co-evolution reflection compares two rules and guides crossover.

A. Individual Encoding and Initialization

  • SeEvo individuals are HDR code fragments with required function names and inputs and outputs, but no fixed-length encoding or predefined function set.The LLM prompt generator uses seed heuristics and instructions to initialize the population.Source: A. Individual Encoding and… · p. 4

B. The Reflection-Evolution Loop

  • The reflection-evolution loop evaluates individuals and uses three reflection mechanisms and three evolution operators to refine candidates.These mechanisms are presented as the orchestration of the iterative evolution process.Source: B. The Reflection-Evolution Loop · p. 4

1) Individual Co-Evolution Reflection (Rco):

  • Co-evolution reflection compares two randomly selected HDRs and their performance metrics, producing Rco as guidance for crossover.The reflection is generated from the two parent individuals and their performance disparity.Source: 1) Individual Co-Evolution Reflection… · pp. 4–5

2) Individual Self-Evolution Reflection (Rself):

SeEvo reflects on offspring performance to guide individual refinement, then consolidates local reflections into memory that guides later evolution operators.

2) Individual Self-Evolution Reflection (Rself):

  • When offspring performance does not improve, Rself analyzes failure to prevent recurring errors; when it improves, the reflection reinforces successful strategies.The performance differential compares each offspring with its corresponding parent and informs refinement within crossover.Source: 2) Individual Self-Evolution… · p. 5

3) Collective Evolution Reflection (Rcoll):

  • At each generation’s conclusion, local reflections are synthesized with prior-generation memory into collective evolutionary knowledge that guides subsequent operators.The collective reflection set contains the generation’s local insights.Source: 3) Collective Evolution Reflection… · p. 5

4) Crossover:

Crossover combines complementary parent strategies and then refines each offspring using individual and collective reflections.

4) Crossover:

  • Co-Evolution Crossover takes two parent HDRs, their co-evolution reflection, and collective wisdom as guidance for offspring generation.The dual guidance supports strategy-level reasoning that synthesizes complementary strengths from both parents.Source: 4) Crossover · p. 5
  • Self-Evolution then refines each co-evolution offspring using its parent, the self-evolution reflection, and collective memory.This is the second stage of the crossover operator.Source: 4) Crossover · p. 5
  • The two-stage crossover learns from successful and failed attempts through reflection-guided refinement of offspring.The crossover operator performs semantic fusion guided by local and global reflections.Source: 4) Crossover · p. 5

5) Mutation:

SeEvo uses collective evolutionary knowledge to modify elite HDRs, evaluates rules on scheduling objectives, and feeds generated reflections back into later operators.

5) Mutation:

  • Mutation uses collective memory to guide strategic modifications of elite HDRs, grounding exploration in accumulated evolutionary knowledge.The paper characterizes this as knowledge-driven exploration rather than random perturbation alone.Source: 5) Mutation · pp. 5–6

6) Individual Evaluation:

  • Each HDR is evaluated on makespan and tardiness minimization to refine the population toward optimal solutions.The detailed evaluation design is provided in the supplement.Source: 6) Individual Evaluation · p. 6

C. The SeEvo Algorithm Framework

  • Algorithm 1’s loop generates and collects reflections, synthesizes them, and feeds them into crossover and mutation in the next generation.The pseudocode is provided in the supplementary material.Source: C. The SeEvo Algorithm Framework · p. 6

A. Experimental Setup

  • Experiments compare SeEvo with GP, GEP, more than ten HDRs, and end-to-end DRL across static TA/DMU benchmarks and simulated dynamic scenarios.Dynamic scenarios include order variations, machine breakdowns, and fuzzy processing times; makespan and tardiness are evaluated.Source: A. Experimental Setup · p. 6
  • Training cases span static instances of 20–100 jobs and 10–20 machines and dynamic batches with breakdowns and gamma-distributed processing-time noise.Dynamic cases use 5–20 machines, 1–2 breakdowns, and 20–50 jobs per batch; the study uses 20 training cases and replaces one after each iteration.Source: A. Experimental Setup · p. 6

B. Parameter Selection for the SeEvo Method

A Taguchi experiment selected SeEvo’s parameter settings using average makespan, while constraining population and iteration sizes to balance performance and API costs.

B. Parameter Selection for the SeEvo Method

  • The Taguchi design varied population size, maximum iterations, mutation rate, and LLM temperature across three candidate values each.Each combination was evaluated three times across four training cases.Source: B. Parameter Selection for the SeEvo… · p. 6
  • Population size 20, maximum iterations 20, mutation rate 0.9, and LLM temperature 1.0 were selected as the optimal combination.The selection was based on average makespan in an L9 orthogonal-array experiment.Source: B. Parameter Selection for the SeEvo… · p. 6, Figure 3 · p. 7
  • Population and iteration sizes were intentionally constrained to balance performance improvements against LLM API-call costs.Reducing computational costs while maintaining high-quality dynamic scheduling results is identified as future work.Source: B. Parameter Selection for the SeEvo… · p. 7

C. Generalization

On static TA and DMU benchmarks, SeEvo generalizes across test cases and problem sizes; in dynamic makespan tests, it keeps the relative gap small despite fuzzy processing times and shop-floor disruptions.

C. Generalization

  • On DMU, SeEvo ranked first in 14 of 16 cases and second in the other two, while mean makespans by problem size also favored SeEvo over alternatives.The second-place differences were minimal, including one unit behind in DMU29.Source: C. Generalization · p. 7, Table II · p. 8, Table III · p. 8
  • On TA, SeEvo outperformed other approaches in 13 of 16 cases and ranked second in the remaining three.The TA evaluation also reports arithmetic mean makespans by problem size.Source: C. Generalization · p. 7, Table IV · p. 8, Table V · p. 9
  • Across DMU and TA, gpt-4.1-mini performed best among the three LLMs, followed by DeepSeek-V3 and Qwen-Turbo.On 100-job, 20-machine tests, Qwen-Turbo and gpt-4.1-mini took 40 and 42 seconds, while DeepSeek-V3 took 122 seconds and had approximately one-third of gpt-4.1-mini’s API cost.Source: C. Generalization · p. 7
  • A gap remains between SeEvo’s results and optimal solutions on the static benchmark cases.The paper identifies this as a remaining limitation and proposes local LLMs and vector databases as possible future directions.Source: C. Generalization · p. 7

D. Performance Evaluation in Dynamic Cases for Makespan Optimization

  • The maximum dynamic makespan gap ratio was 5%, and it remained below 1% in most cases.The evaluation included fuzzy processing times, random order arrivals, and machine breakdowns; the gap compares each method with the best result among 14 methods for that case.Source: D. Performance Evaluation in Dynamic… · pp. 7, 9
  • The method’s dynamic performance is attributed to domain knowledge and training on 20 randomly sized order batches, alongside three reflection-based evolution strategies.The strategies are individual co-evolution, individual self-evolution, and collective evolution reflection.Source: D. Performance Evaluation in Dynamic… · p. 9

E. Performance Evaluation in Dynamic Cases for Tradiness Optimization

In dynamic tardiness tests, SeEvo achieved small relative gaps against the best results among the compared methods. The evaluation used deliberately short due dates, which the authors note differ from the more dynamic due dates typical in manufacturing.

E. Performance Evaluation in Dynamic Cases for Tradiness Optimization

F. Ablation Study

The ablations compare SeEvo with a version lacking individual self-evolution and examine its training behavior, generalization, and implementation trade-offs. SeEvo’s advantage over ReEvo is most evident on complex training cases, while the paper cautions that scheduling-method performance depends on the scenario.

F. Ablation Study

  • Removing individual self-evolution produces ReEvo, which is compared with SeEvo for exploration, exploitation, and generalization.Both methods are assessed over 50 iterations on static training datasets before generalization testing.Source: F. Ablation Study · p. 9
  • Across both training datasets, LLM-based methods significantly outperform GP/GEP, and SeEvo variants consistently outperform ReEvo counterparts mid-to-late; on complex DMU, their curves show limited overlap after 15–20 validation iterations.Each method was independently executed 10 times, and shaded areas show standard deviations.Source: F. Ablation Study · p. 9
  • Figures 4 and 5 present gap ratios across scheduling methods for makespan and tardiness optimization, respectively.Source: Figure 4 · p. 10, Figure 5 · p. 10
  • On TA generalization sets of 30 jobs × 20 machines and 50 jobs × 20 machines, SeEvo outperformed ReEvo and two end-to-end DRL methods.The tested objective was minimizing completion time.Source: F. Ablation Study · p. 11, Table VI · p. 11
  • Most generated rules from GPT-4.1-mini, GP, and GEP have O(n) complexity; some DeepSeek-V3 rules are O(n^2), while a GP rule’s nesting raises overhead and limits interpretability.The paper characterizes SeEvo-generated rules as efficient and more logical, and says SeEvo does not rely on high-end GPUs, unlike the cited DRL methods.Source: F. Ablation Study · p. 11
  • The authors caution that no scheduling method is absolutely superior across all scenarios; performance depends on each case’s characteristics.Source: F. Ablation Study · p. 11
  • Figure 7 presents the EMA-feature ablation in terms of gap-ratio distribution and stability.Source: Figure 7 · p. 11

VI. CONCLUSION AND FUTURE WORK

The paper proposes SeEvo, an LLM-based evolutionary framework for automatic HDR design in DFJSSP. It reports advantages across static and dynamic fuzzy-processing-time cases, while noting limitations in API use and the single-HDR dynamic setting.

VI. CONCLUSION AND FUTURE WORK

  • SeEvo outperformed commonly used HDRs, GP, GEP, and DRL methods in static generalization, showed advantages in most dynamic fuzzy-processing-time cases, and had notable advantages for tardiness optimization.The paper’s primary focus is makespan optimization.Source: §VI · pp. 11–12
  • SeEvo uses an LLM to generate adaptive HDRs, with an EMA feature tracking historical uncertainty trends so rules can anticipate processing-time deviations.The framework was evaluated in static and dynamic fuzzy-processing-time case studies.Source: §VI · pp. 11–12
  • The authors identify costly external LLM API calls, no direct DFJSSP fine-tuning, and using only one HDR in dynamic cases as limitations.Future work includes local LLM deployment and fine-tuning, graph-based HDR selection, and combining multiple HDRs for dynamic environments.Source: §VI · p. 12

Related papers

Loading 2410.22657v2…