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
School of Computer Science and Engineering, Beihang University, Beijing 100191, China · Shenzhen Loop Area Institute, Shenzhen, China · Qingdao Research Institute, Beihang University +3
Centre for Artificial Intelligence, Zurich University of Applied Sciences, Switzerland · Inspire AG, Zurich, Switzerland · Automatic Control Laboratory, ETH Zurich, Switzerland