Abstract
Dynamic flexible assembly flow shop scheduling with multi-product delivery is a critical combinatorial problem, characterized by kitting supply and machine flexibility. Genetic programming (GP) is widely used to automatically generate dispatching rules, enabling responsive scheduling that reduces manual effort while meeting high responsiveness demands. However, GP methods depend on fixed terminal sets and have weak interpretability.
We develop EvoDR, an evolving dispatching rules framework that leverages the semantic understanding and generation capabilities of large language models to achieve cross-domain integration of algorithm design and scheduling knowledge. Multi-stage assembly supply decisions are modeled as priority sorting of directed edges on heterogeneous graphs. A dual-expert co-evolution mechanism is implemented, where LLM-A generates code while LLM-S conducts scheduling analysis and reflection. Guided by improvements in hybrid evaluation, adaptive rules that fit dynamic features are continuously evolved.
Experimental results show that EvoDR achieves lower average tardiness than state-of-the-art approaches. In 24 scenarios with different resource configurations and disturbance levels, totaling 480 instances, it consistently outperforms expert-designed competitors, demonstrating superior robustness.
1. Problem & Motivation
In a flexible assembly flow shop, parts are processed first and then assembled into products, and a product can only be delivered once its entire item set is complete (dual kitting: structure-level kitting for assembly, delivery-level kitting for the product set). Under dynamic order arrivals, processing and assembly decisions happen asynchronously: processing wants low changeover loss and complete kits, while assembly wants to coordinate different products of the same order for consolidated delivery.
The gap. Priority dispatching rules (PDRs) are the standard real-time remedy, but designing them is expert-intensive. GP-based hyper-heuristics automate the search yet rely on a predefined terminal set, which implicitly encodes problem-specific knowledge and limits both transferability and interpretability. Existing LLM-based automated heuristic design (AHD) methods evolve rules on the code level, without an explicit notion of the multi-stage, hierarchical decision structure of the assembly supply chain.
EvoDR overview: dynamic order arrivals flow through the job buffer into a heterogeneous-graph decision model, are dispatched by an evolved PDR on event-triggered (j, m) arc ranking, and the rule itself is improved by an Initialization → Evaluation → Evolution loop.
| Paradigm | Limitation |
|---|---|
| Manual PDR design (EDD, FIFO, MWKR, ...) | Expert-intensive; single rules react poorly to changing load and disturbance levels |
| Genetic Programming / GEP | Fixed terminal set; problem knowledge baked into the search space; weak interpretability |
| LLM single-rule AHD (EoH, FunSearch, MCTS-AHD, ReEvo) | Code-level evolution only; no explicit model of multi-stage assembly supply or of scheduling semantics |
| EvoDR (Ours) | Heterogeneous-graph MDP + dual-expert co-evolution of rules and design knowledge |
2. Problem Modeling: Heterogeneous Graph and MDP
Processing jobs, assembly jobs and delivery requests are treated as nodes of a heterogeneous graph, with precedence, kitting and product-set relations as typed edges. At each event-triggered decision step t, the system ranks feasible (job, machine) arcs — i.e., joint machine assignment and job sequencing — rather than ranking jobs and machines separately. This avoids the decision-preference inconsistency between the processing stage (efficiency, complete kits) and the assembly stage (product-set coordination), where hand-crafted rule combinations tend to fail.
The dynamic problem is then cast as an MDP over this graph, where the state is the current shop-floor state plus the dynamic feature vector, the action is the selected arc, and the reward is derived from order tardiness, so that the dispatching rule is a policy defined on the graph rather than a fixed priority formula.
3. The EvoDR Framework
One iteration of EvoDR: elite-knowledge-guided initialization → hybrid evaluation (objective fitness + LLM-S semantic feedback) → feature-fitting rule evolution through four operators (C1, C2, M1, M2).
Each individual carries four fields: a textual description of the design idea, an executable code block (a cal_priority function with a fixed interface), the objective fitness cs measured by simulation on multiple instances, and the semantic evaluation ce produced by LLM-S. Evolving the description together with the code keeps the search at the design level instead of drifting into syntax mutation.
Instead of a random initial population, an elite rule is executed in the simulator, LLM-S analyses its behaviour and produces improvement suggestions, and LLM-A expands this into a structurally diverse initial population. Sampling temperatures are spread over a range so that early individuals stay conservative while later ones add diversity; the temperature of the best individual found during initialization is recorded and reused as the evolution temperature u0.
Two independent channels. The objective channel computes fitness in the simulator and is the only basis for updating the incumbent, parent selection and survival selection. The semantic channel (LLM-S) returns a structured report — advantages, limitations, actionable suggestions — that is injected into the generation prompt but never into fitness or selection. Semantic feedback therefore affects the search direction only, not how rules are ranked.
Four operators are implemented purely by prompt manipulation, so the evolutionary operators themselves are language-level and need no problem-specific primitive set:
| Operator | Mechanism | Role |
|---|---|---|
| C1: Dominance-Fusion Crossover | Two parents + "combine the advantages of the two" | Merge structural strengths into a stronger offspring |
| C2: Exploratory Crossover | Parent code + "create a completely different algorithm" | Break premature convergence, escape local optima |
| M1: Directed Optimization | Parent code + LLM-S suggestion ce | Turn natural-language suggestions into code-level refinement |
| M2: Parameter Tuning | Parent code + "identify parameters, change their settings" | Numerical refinement inside an existing logic structure |
Two prompt templates: pS feeds code, fitness and dynamic features to LLM-S along with the best/worst rules of the population; pA combines the semantic feedback ce with an operator instruction to drive LLM-A.
4. Experimental Results
| Dimension | Configuration |
|---|---|
| Instances | Real industrial data from a Chinese home-appliance manufacturer + generated instances (Poisson order arrivals, exponential inter-arrival time under load) |
| Scale factors | Machine configuration m (3×6 / 5×12), flexibility φ (0.5 / 0.7), arriving orders α (20 / 50), load factor μ (1 / 2 / 4) |
| Baselines | EDD; 8 hybrid heuristics (FIFO / MOPNR / LWKR / MWKR × SPT / EET); GP; GEP; RandSample; FunSearch; EoH; MCTS-AHD; ReEvo |
| Metric | Average tardiness (lower is better), ARI = (Tmax − Tcurrent) / Tmax |
| LLM | GPT-4o-mini (96.0% code accuracy, $0.09 per run) after comparing 5 models |
| Budget | 20 iterations, population 4–6; 200 samples for AHD comparison; decision time is millisecond-level |
On 20 instances with real industrial characteristics (10 train / 10 test), all AHD methods are compared under the same 200-sample budget and identical dynamic features:
| Method | Type | All (Avg. tardiness) | ARI ↑ | Avg. Rank |
|---|---|---|---|---|
| EDD | Manual | 6957.34 | 0.00% | 7.85 |
| GP | Traditional AHD | 6229.43 | 10.46% | 5.00 |
| GEP | Traditional AHD | 6649.56 | 4.42% | 6.35 |
| RandSample | LLM | 6009.91 | 13.62% | 4.25 |
| FunSearch | LLM | 6008.46 | 13.64% | 3.90 |
| EoH | LLM | 6074.44 | 12.69% | 3.35 |
| MCTS-AHD | LLM | 6206.53 | 10.79% | 4.95 |
| ReEvo | LLM | 6238.49 | 10.33% | 5.55 |
| EvoDR | LLM + dual expert | 5788.11 | 16.81% | 2.65 |
On the test split the gain is larger (ARI 18.63%), while GP degrades markedly on test instances — the fixed terminal set helps it fit the training set but does not transfer. Friedman test over the 20 instances rejects equality of methods (p < 0.0001); two-tailed Wilcoxon signed-rank tests put EvoDR ahead of every competitor (all p ≤ 0.0025, below the Bonferroni threshold 0.0071), winning 62–82 of 100 paired runs. Note that EvoDR is not the best method on every single instance — its advantage appears in the aggregate and in rank.
Tardiness distribution of the best PDR found by each method (5 independent design runs). Red markers: mean; black lines: median.
Convergence under a 200-sample budget. GP finds a good rule within ~70 samples but plateaus; EvoDR starts weaker and keeps improving after 100 samples, overtaking the incumbent eight times.
A single design run: beyond the 150th sample — where GP-style methods have already plateaued — the curve shows a second convergence phase (7581.21 → 7371.61), driven by LLM-S pointing to feature-level fixes such as adding a historical-performance factor or predictive processing times.
480 instances over 24 scenarios are constructed by varying machine configuration, flexibility, arriving-order volume and load factor. EvoDR is re-designed and re-tested independently for each scenario:
Condition (m-φ-α-μ) | EDD | FIFO+SPT | MWKR+EET | EvoDR |
|---|---|---|---|---|
| 3-6-0.5-20-1 | 1710.45 | 1729.20 | 2091.60 | 1117.80 |
| 3-6-0.5-50-4 | 30322.88 | 30122.07 | 37470.92 | 25278.60 |
| 3-6-0.7-50-4 | 31499.53 | 32061.02 | 35879.24 | 22108.98 |
| 5-12-0.5-50-1 | 2353.79 | 449.26 | 1676.96 | 409.58 |
| 5-12-0.7-20-1 | 975.55 | 134.31 | 705.70 | 129.94 |
| 5-12-0.7-50-4 | 6207.29 | 4818.25 | 5996.55 | 4553.07 |
| Average (24 scenarios) | 7470.74 | 6483.53 | 7943.18 | 5387.17 |
| ARI ↑ | 10.72% | 22.51% | 5.07% | 35.62% |
EvoDR attains the lowest tardiness in 19 of the 24 scenarios and the lowest average overall (ARI 35.62%). The remaining cases are mostly low-load settings where a single hybrid rule is already near-optimal, e.g. 5-12-0.7-20-1, where FIFO+SPT reaches 134.31 against EvoDR's 129.94. The gap widens as load increases: under 3-6-0.7-50-4 the best hybrid rule sits at 34045.23 while EvoDR reaches 22108.98.
Tardiness distribution of all methods across the 24 operating conditions. Traditional hybrids are highly condition-sensitive; EvoDR stays stable as μ increases.
| Variant | What is removed | Avg. tardiness | ARI ↑ |
|---|---|---|---|
| EDR-D | Dynamic features in the prompt | 1195.37 ± 55.69 | 6.08% |
| EDR-E | Elite-knowledge-guided initialization | 1434.77 ± 291.70 | −12.73% |
| EDR-C | Crossover operators (C1, C2) | 1151.20 ± 33.06 | 9.55% |
| EDR-M | Improvement operators (M1, M2) | 1185.85 ± 88.08 | 6.83% |
| EDR-F(order) | Order-level features | 1579.27 ± 227.22 | −24.08% |
| EDR-F(machine) | Machine-level features | 1140.60 ± 65.30 | 10.39% |
| EDR-F(arc) | Arc-level (graph topology) features | 1630.28 ± 54.90 | −28.09% |
| EDR-S | LLM-S semantic evaluation (hybrid evaluation) | 1272.80 ± 52.73 | 0.00% |
| EDR-S(fix) | LLM-S replaced by fixed suggestions | 1215.87 ± 101.79 | 4.47% |
| EDR-S(random) | LLM-S replaced by random suggestions | 1107.07 ± 8.49 | 13.02% |
| EvoDR | (full model) | 1084.17 ± 12.56 | 14.82% |
Feature design dominates: dropping arc (−28.09%) or order (−24.08%) features is catastrophic, while dropping machine features still leaves a competitive rule — under dual kitting constraints, topological and job-level dynamics matter far more than the processing units themselves. Elite-knowledge initialization is the second largest contributor.
The hybrid-evaluation result deserves a caveat: removing LLM-S entirely hurts (1272.80), but replacing it with random suggestions scores 1107.07, only 23 above the full model. So the benefit is not simply "semantic quality"; any clear feedback that widens the search helps. The paper therefore checks stability: with a small suggestion pool (4) random feedback stays competitive, but with an expanded pool (37) it becomes markedly unstable and degrades, whereas LLM-S's scheduling-specific feedback keeps the directed value. Random feedback is a lucky configuration, not a robust substitute.
Convergence of the random-feedback variant with a suggestion pool of 4 (left) and 37 (right): competitive when small, unstable when expanded.
| Method | All (Avg.) | Tokens | Code accuracy | Cost (USD) |
|---|---|---|---|---|
| EoH | 1297.4 | 0.32M | 87.3% | 0.131 |
| ReEvo | 1242.9 | 1.36M | 70.4% | 0.558 |
| EvoDR | 1185.1 | 0.30M / 0.16M | 89.3% | 0.123 / 0.066 |
Cost is reported as LLM-A / LLM-S. A full run costs about $0.19 in total, with LLM-S adding roughly 0.16M tokens on top of LLM-A's 0.30M. This is a one-time offline design cost: at run time the evolved rule only performs one priority ranking over candidate arcs per decision, executes in sub-milliseconds, and makes no LLM call. The honest comparison is that EvoDR costs somewhat more than EoH ($0.19 vs $0.131) and buys a much larger tardiness reduction for it.