Lifelong Learning of Scheduling Rules with Surrogate-assisted Genetic Programming for Dynamic Flexible Job Shop Scheduling
Authors: Luyao Zhu, Fangfang Zhang, Yi Mei, Ke Chen, Mengjie Zhang
Organizations: Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand · School of Electrical and Information Engineering, Zhengzhou University, Zhengzhou, China
Genetic programming (GP) has been widely used to learn scheduling rules for dynamic flexible job shop scheduling (DFJSS). However, trained rules tend to only generalise to tasks of similar scales and distributions, and when task characteristics change, learned rules often suffer significant performance degradation. Moreover, fine-tuning pre-trained rules on new tasks often leads to catastrophic forgetting, where prior knowledge is lost. This motivates the need for GP methods that can adapt to new tasks while preserving past knowledge, leading to a lifelong learning paradigm. However, lifelong learning in GP for DFJSS remains largely under-explored. To address this gap, this paper proposes a surrogate-assisted GP method for lifelong learning to handle sequential heterogeneous DFJSS tasks with job or batch arrivals. The framework includes three key components: an adaptive two-stage training strategy to balance plasticity and stability, a task-similarity-based weighting mechanism to regulate knowledge reuse, and an improved surrogate model with distance constraints to enhance estimation accuracy. Experimental results show that the proposed method effectively mitigates catastrophic forgetting while maintaining strong adaptability, outperforming several compared methods and demonstrating the potential of lifelong GP in dynamic scheduling environments.
Figures & tables
Fig. 1: An example of GP-evolved scheduling rules.
Fig. 2: Process of LLSGP learning from sequentially arriving tasks.
Decision Point
Rank Obtained by the Reference Rule
Rank Obtained by the Sequencing Rule
PCi
1(O1)
3
1
1(O2)
1
3
3
1(O3)
2
2
2(O1)
2
3
2(O2)
1
1
1
2(O3)
3
2
TABLE I: An example of the calculation of the behaviour vector of a sequencing rule across three decision points and each involving three candidate operations.
Fig. 3: An example of distance-constrained fitness estimation.
Task
Machines
Jobs
Utilisation
Due Date Factor
Batch Size
Distribution
Standard Discrete Job Shop with Job Arrivals [ 15 ]
10
3000
0.85
1.5
[1,1]
Uniform [1,99]
Standard Discrete Job Shop with Batch Arrivals [ 6 ]
10
3000
0.85
2.0
[10,20]
Exponential( μ=20 )
Low-Demand Small-Order Job Shop [ 46 ]
2
500
0.60
1.2
[1,9]
Gamma( k=2 , θ=25 )
Heavy-Demand Large-Order Job Shop [ 46 ]
15
3000
0.95
4.0
[20,30]
Normal( μ=80 , σ=10 )
TABLE II: Parameters of Four Designed DFJSS tasks.
Parameter
Value
Number of tasks
4
Number of generations per task
100
Population size
500
Parent selection
Tournament selection
with size 7
Number of elites
10
TABLE III: The parameter settings in GP.
Metric
Restart
Fine-tuning-5%
Fine-tuning-10%
Fine-tuning-100%
LLR-BC
LLSGP
AP
Value
69.92 (20.56) ( ↑ , 0.00)
34.75 (7.72) ( ↑ , 0.01)
43.05 (23.22) ( ↑ , 0.01)
39.36 (15.37) ( ↑ , 0.00)
34.08 (14.51) ( ↑ , 0.03)
29.75 (12.15)
Rank
5.83
2.83
4.17
3.50
2.83
1.83
AF
Value
86.68 (27.66) ( ↑ , 0.00)
40.69 (10.34) ( ↑ , 0.00)
51.66 (31.38) ( ↑ , 0.00)
40.69 (10.34) ( ↑ , 0.00)
32.68 (18.97) ( ≈ , 0.84)
34.35 (15.88)
Rank
5.83
3.00
4.33
3.67
1.83
2.33
AMF
Value
131.21 (24.69) ( ↑ , 0.00)
63.26 (15.75) ( ↑ , 0.02)
68.81 (34.10) ( ↑ , 0.00)
73.68 (25.61) ( ↑ , 0.00)
49.11 (25.64) ( ≈ , 0.54)
53.57 (27.70)
Rank
6.00
3.17
3.33
4.33
1.83
2.33
TABLE IV: Comparisons of mean (std) metrics and ranks for the compared algorithms over six training orders (30 runs each).
Fig. 4: Average test performance on different tasks during lifelong learning under the EGUN training order.
Fig. 5: Average test performance on different tasks during lifelong learning under the UGEN training order.
Metric
One-stage
Raw-surrogate
Equal-weight
Focused-weight
Proposed LLSGP
AP
Value
44.38 (11.22) ( ↑ , 0.03)
38.99 (7.43) ( ↑ , 0.04)
36.11 (9.87) ( ≈ , 0.22)
33.75 (9.41) ( ≈ , 0.22)
29.75 (12.15)
Rank
4.67
3.33
2.67
2.50
1.83
AF
Value
35.52 (14.93) ( ≈ , 0.84)
49.95 (12.75) ( ↑ , 0.04)
39.15 (10.30) ( ≈ , 0.56)
34.94 (14.43) ( ≈ , 0.84)
34.35 (15.88)
Rank
2.33
4.50
3.00
2.67
2.50
AMF
Value
55.36 (28.90) ( ≈ , 0.84)
92.41 (43.01) ( ↑ , 0.03)
57.63 (12.07) ( ≈ , 0.69)
54.36 (22.27) ( ≈ , 0.84)
53.57 (27.70)
Rank
2.00
5.00
2.67
2.83
2.50
TABLE V: Comparisons of mean (std) metrics for ablation variations over six training orders (30 runs each).
Fig. 6: Average weights of tasks across six training orders.
Task 2
Task 3
Task 4
107.5 (2.0)
207.3 (1.6)
306.8 (1.1)
TABLE VI: Average generation at which the algorithm switches from Stage 1 to Stage 2 across six training orders.
Fig. 7: Average behaviour vector distances to surrogate samples of the three previously learned tasks when learning the fourth task (EGUN order).
Fig. 8: MAE comparison between the regions within and outside the threshold across the three previously learned tasks during the training of the fourth task under the EGUN order
Restart
Fine-tuning-5%
Fine-tuning-10%
Fine-tuning-100%
LLR-BC
Proposed LLSGP
383.09 (60.36)
458.16 (89.93)
461.24 (90.10)
479.24 (92.61)
461.72 (89.12)
485.44 (99.85)
TABLE VII: Mean (std) training time (in minutes) of the algorithms across six training orders
Fig. 9: Size of best evolved scheduling rule pair across six training orders during evolutionary process
Hyper-heuristics have become a popular approach for solving dynamic flexible job shop scheduling (DFJSS) problems. They use gradient-free optimization techniques like Genetic Programming (GP) to evolve non-differentiable heuristics. However, conventional GP methods tend to converge slowly because they rely solely on evolutionary search to find good heuristics. Existing multitask GP methods can solve multiple tasks simultaneously and speed up the search by transferring knowledge across similar tasks. But they mostly exchange heuristic building blocks without truly generating heuristics conditioned on task information. In this paper, we aim to accelerate convergence and enable task-specific heuristic generation by incorporating a task-conditioned Transformer model. The Transformer works in two ways. First, it learns the distribution of elite heuristics, biasing the search toward promising regions of the heuristic space. Second, through conditional generation, it produces heuristics tailored to specific tasks, allowing the model to handle multiple scheduling tasks at once and improving overall optimization efficiency. Based on these ideas, we propose TransGP, a Task-Conditioned Transformer-Guided GP framework. This evolutionary paradigm integrates generative modeling with GP, enabling efficient multitask heuristic learning and knowledge transfer. We evaluate TransGP on a range of DFJSS scenarios. Experimental results show that TransGP consistently outperforms multitask GP baselines, widely used handcrafted heuristics, and the pure Transformer model, achieving faster convergence, superior solution quality, and enhanced robustness.
The Dynamic Flexible Job Shop Scheduling Problem (DFJSP) necessitates a trade-off between instant reaction to stochastic disturbances and global optimization of production goals. Conventional priority rules are insufficiently flexible to handle complex disruptions, whereas learning-based approaches often compromise interpretability or fail to generalize across problem scales. Although Large Language Models (LLMs) offer advanced reasoning capabilities to bridge this gap, their substantial inference latency is incompatible with the millisecond-level decision cycles of industrial control systems. To resolve this conflict, we introduce RACE-Sched, an asynchronous agent-based framework that decouples policy execution from logical reasoning via a dual-stream architecture. The Reactive Stream executes low-latency symbolic heuristics to enable real-time dispatching, while the parallel Deliberative Stream leverages an LLM to synthesize, validate, and evolve these rules. Candidate rules undergo rigorous testing in a sandbox and are deployed via atomic updates, ensuring safety without blocking the control loop. Additionally, a semantic rule repository indexes validated heuristics for retrieval-based initialization which enhances transferability across problem scales. Extensive evaluations on GEN-Bench, MK-Bench, and JMS-Bench demonstrate that RACE-Sched outperforms leading Deep Reinforcement Learning and other LLM-based baselines. This approach harmonizes real-time constraints with long-horizon reasoning to achieve superior solution quality and robust adaptation to dynamic events.
Shijie Cao, Yuan Yuan, Jing Liu
School of Computer Science and Engineering, Beihang University, Beijing 100191, China · Shenzhen Loop Area Institute, Shenzhen, China · Qingdao Research Institute, Beihang University +3
The Flexible Job Shop Scheduling Problem (FJSP) is the optimal allocation of a set of jobs to machines. Two primary challenges persist in FJSP: the unpredictable arrival of future jobs and the combinatorial complexity of the problem, rendering it intractable for conventional mixed-integer linear programming solvers. This paper proposes an event-based \gls{DRL} approach to solve FJSP with random job arrivals. Specifically, we employ the Proximal Policy Optimization algorithm and use lightweight Multi-Layer Perceptrons to train the \gls{DRL} agent for minimizing the total completion time of all jobs. We design the state representation to be directly accessible from the environment, and limit the learning agent to selecting from among a set of well-established dispatching rules. Simulations show that our \gls{DRL} approach outperforms any of the individual dispatching rules on datasets with varying heterogeneity and job arrival rates. We benchmark our \gls{DRL} against an arrival-triggered mixed-integer linear programming solution and show that our method achieves good performance especially when the datasets are heterogeneous.
Yu Tang, Muhammad Zakwan, Efe Balta +2
Centre for Artificial Intelligence, Zurich University of Applied Sciences, Switzerland · Inspire AG, Zurich, Switzerland · Automatic Control Laboratory, ETH Zurich, Switzerland