Surrogate-Assisted Genetic Programming with Phenotypic Characterisation in Dynamic Multi-Mode Project Scheduling

Yuan Tian; Yi Mei; Mengjie Zhang

cs.NESep 13, 2026

Surrogate-Assisted Genetic Programming with Phenotypic Characterisation in Dynamic Multi-Mode Project Scheduling

Authors: Yuan Tian, Yi Mei, Mengjie Zhang

Organizations: Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, New Zealand

Abstract

Dynamic multi-mode resource-constrained project scheduling requires decisions to be made under precedence constraints, limited resources, multiple execution modes, and uncertain activity durations. Genetic programming (GP) can automatically evolve heuristic rules for such problems, but its simulation-based fitness evaluation is computationally expensive. This study investigates phenotypic characterisation (PC) in surrogate-assisted GP to evolve higher-quality scheduling heuristics under a fixed budget of full simulation-based fitness evaluations. A key question is how GP individuals should be encoded into phenotypic characterisations to support effective fitness estimation. To answer this question, three PC encoding schemes with different levels of information richness are designed: priority-value encoding, which preserves raw rule outputs; rank encoding, which captures candidate ordering; and binary encoding, which represents final scheduling decisions. These encodings are combined with different distance metrics to measure behavioural similarity between GP individuals. The experimental results show that binary encoding with Euclidean distance provides the most effective and robust surrogate guidance. Further analyses show that surrogate estimation accuracy alone does not fully explain the performance differences. The PC representation also determines how effectively phenotypically redundant offspring are removed and how much behavioural diversity is retained after preselection. Ablation experiments further demonstrate that duplicate removal and surrogate preselection provide complementary benefits, with their combination producing the largest improvement. These findings highlight that effective surrogate-assisted GP depends not only on identifying promising offspring, but also on controlling redundancy and preserving useful diversity during evolutionary search.

Figures & tables

Fig. 1: Precedence graph of the DMRCPSP example.

Activity $i$	Mode	$\hat{d}_{i,m}$	$d^{\text{min}}_{i,m}$	$d^{\text{max}}_{i,m}$	R1	R2
1	1	0	0	0	0	0
2	1	5	3	7	10	9
	2	7	5	8	6	4
3	1	4	3	7	7	0
	2	6	5	7	5	0
4	1	4	3	6	9	6

TABLE I: Activity-mode information of the example, including duration estimates and renewable resource requirements.

Fig. 2: A feasible schedule for the illustrative example.

Fig. 3: Overall framework of the surrogate-assisted GP algorithm.

Fig. 4: An example of a GP individual consisting of two tree-based heuristic rules for DMRCPSP.

Fig. 5: Flowchart of the heuristic-guided scheduling procedure for DMRCPSP. The dashed region represents the activity group selection process guided by the two tree-based heuristic rules.

Fig. 6: Decision situation collection process.

Fig. 7: Example of activity-mode subset selection encoding using various schemes.

Fig. 8: Example of activity group selection encoding using various schemes.

Fig. 9: Phenotypic characterisation vector generation.

Encoding Scheme	Distance Metric
Priority value	Euclidean, Pearson
Rank	Euclidean, Kendall tau, Spearman
Binary	Euclidean

TABLE II: Distance metrics for the encoding schemes.

Parameter	Value
Population size	1000
Number of generations	100
Method for initialising population	ramped-half-and-half
Initial minimum/maximum depth	2 / 6
Elitism	10
Maximal program depth	8

TABLE III: The parameter settings of GP.

Category	Notation	Description
Time	EST	Earliest Start Time
	EFT	Earliest Finish Time
	LST	Latest Start Time
	LFT	Latest Finish Time
	Duration	Expected Duration
	MinDuration	Optimistic Duration

TABLE IV: Terminal set.

$\lambda_{\text{off}}$	Scenario	GP	Value		Rank			Binary
			Pearson	Euclidean	Kendall	Spearman	Euclidean	Euclidean
2	<0.75/R12>	1.724±0.013	1.716±0.015	1.710±0.012	1.708±0.009	1.710±0.010	1.711±0.014	1.704±0.011
			( $\uparrow$ )	( $\uparrow$ )( $\approx$ )	( $\uparrow$ )( $\uparrow$ )( $\approx$ )	( $\uparrow$ )( $\uparrow$ )( $\approx$ )( $\approx$ )	( $\uparrow$ )( $\approx$ )( $\approx$ )( $\approx$ )( $\approx$ )	( $\uparrow$ )( $\uparrow$ )( $\uparrow$ )( $\approx$ )( $\approx$ )( $\uparrow$ )
	<0.5/R12>	1.691±0.011	1.682±0.017	1.680±0.016	1.677±0.016	1.676±0.015	1.679±0.017	1.671±0.015
			( $\uparrow$ )	( $\uparrow$ )( $\approx$ )	( $\uparrow$ )( $\approx$ )( $\approx$ )	( $\uparrow$ )( $\approx$ )( $\approx$ )( $\approx$ )	( $\uparrow$ )( $\approx$ )( $\approx$ )( $\approx$ )( $\approx$ )	( $\uparrow$ )( $\uparrow$ )( $\uparrow$ )( $\approx$ )( $\uparrow$ )( $\uparrow$ )
	<0.25/R12>	1.710±0.016	1.712±0.019	1.703±0.014	1.699±0.015	1.699±0.014	1.708±0.013	1.692±0.014

TABLE V: Mean (standard deviation) of the objective values on the test set obtained by GP and surrogate-assisted GP variants from 30 independent runs.

Fig. 10: Convergence curves of algorithms with offspring generation multiplier value of 4 over 30 independent runs.

Fig. 11: Training fitness distribution of the GP and the surrogate-assisted GP variants when

\lambda_{\text{off}}=4

across generations over 30 independent runs.

$\lambda_{\text{off}}$	Scenario	<0.75/R12>			<0.5/R12>			<0.25/R12>
	Algorithm	Real Eval.	PC Gen.	Surr. Est.	Real Eval.	PC Gen.	Surr. Est.	Real Eval.	PC Gen.	Surr. Est.
2	SGP-Binary-Euclidean	401.22	11.93	0.24	819.37	33.31	0.28	936.53	15.14	0.25
	SGP-Rank-Kendall	378.40	14.31	1.96	754.60	28.85	22.85	1162.31	15.92	4.07
	SGP-Rank-Spearman	349.65	12.83	4.20	634.82	28.30	8.83	938.37	15.65	5.70
	SGP-Rank-Euclidean	411.17	14.12	0.30	790.67	34.84	0.32	1153.11	18.94	0.32
	SGP-Value-Pearson	342.78	12.26	0.74	715.75	27.13	0.90	1012.03	16.07	0.92

TABLE VI: Mean runtime of real evaluation, PC vector generation and surrogate estimation per generation in seconds.

Fig. 12: Mean Spearman correlation between true and estimated offspring fitness across generations over 30 independent runs.

Fig. 13: An illustrative example of true versus estimated fitness from one sampled offspring set at Generation 0 for <0.75/R12>.

Fig. 14: Ratio of true top-1000 offspring identified by different encoding-distance combinations across generations.

Fig. 15: Number of duplicate intermediate offspring removed across generations.

Fig. 16: Normalised average nearest distance between intermediate offspring after duplicate removal.

Fig. 17: Normalised average nearest distance between intermediate offspring after duplicate removal and surrogate preselection.

	Scenario
Algorithm	<0.75/R12>	<0.5/R12>	<0.25/R12>
GP	1.724±0.013	1.691±0.011	1.710±0.016
GP + Duplicate Removal	1.715±0.011	1.683±0.012	1.705±0.015
	( $\uparrow$ )	( $\uparrow$ )	( $\approx$ )
GP + Surrogate Preselection	1.722±0.014	1.687±0.012	1.715±0.020
	( $\approx$ )( $\downarrow$ )	( $\approx$ )( $\approx$ )	( $\approx$ )( $\downarrow$ )

TABLE VII: Mean (standard deviation) objective values on the test set of the ablation variants over 30 independent runs. Binary PC encoding, Euclidean distance and

\lambda_{\text{off}}=4

are used.

Fig. 18: Convergence curves for the ablation study of duplicate removal and preselection with

\lambda_{\text{off}}=4

over 30 independent runs.

Resource-Constrained Project Scheduling

See all 10 papers

Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling
Mar 17, 2026Yuan Tian, Yi Mei, Mengjie ZhangResource-Constrained Project Scheduling Genetic Programming
Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand
Guiding Large Language Models with Genetic Programming-Evolved Heuristic Knowledge for Dynamic Multi-Mode Project Scheduling
Jul 30, 2026Yuan Tian, Yi Mei, Mengjie ZhangResource-Constrained Project Scheduling Large Language Model-Guided Optimization
Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand
Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling
Mar 9, 2026Junhua Xue, Yuning Chen, Mingyan Shao +3Genetic Programming Automated Heuristic Design

Mar 17, 2026J/K move · Enter open · S save

Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

Yuan Tian, Yi Mei, Mengjie Zhang

Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand

Resource-Constrained Project Scheduling Genetic Programming Combinatorial Optimization Surrogate-Assisted Optimization Surrogate Modeling

Open paper AskPDF arXiv

The dynamic multi-mode resource-constrained project scheduling problem (DMRCPSP) is of practical importance, as it requires making real-time decisions under changing project states and resource availability. Genetic Programming (GP) has been shown to effectively evolve heuristic rules for such decision-making tasks; however, the evolutionary process typically relies on a large number of simulation-based fitness evaluations, resulting in high computational cost. Surrogate models offer a promising solution to reduce evaluation cost, but their application to GP requires problem-specific phenotypic characterisation (PC) schemes of heuristic rules. There is currently a lack of suitable PC schemes for GP applied to DMRCPSP. This paper proposes a rank-based PC scheme derived from heuristic-driven ordering of eligible activity-mode pairs and activity groups in decision situations. The resulting PC vectors enable a surrogate model to estimate the fitness of unevaluated GP individuals. Based on this scheme, a surrogate-assisted GP algorithm is developed. Experimental results demonstrate that the proposed surrogate-assisted GP can identify high-quality heuristic rules consistently earlier than the state-of-the-art GP approach for DMRCPSP, while introducing only marginal computational overhead. Further analyses demonstrate that the surrogate model provides useful guidance for offspring selection, leading to improved evolutionary efficiency.

Abstract

Resource-Constrained Project Scheduling

Explore similar work

Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

Guiding Large Language Models with Genetic Programming-Evolved Heuristic Knowledge for Dynamic Multi-Mode Project Scheduling

Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling