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

A research team from Victoria University of Wellington has published a paper on arXiv introducing a novel surrogate-assisted genetic programming (GP) algorithm designed to tackle the computationally intensive Dynamic Multi-mode Resource-constrained Project Scheduling Problem (DMRCPSP). This problem involves making real-time decisions for project scheduling as conditions and resource availability change, a common challenge in construction, manufacturing, and software development. Traditional GP methods evolve heuristic rules for these decisions but require a massive number of simulation-based fitness evaluations, leading to prohibitively high computational costs. The team's key innovation is a new 'rank-based phenotypic characterisation' scheme that translates the complex behavior of a scheduling heuristic into a numerical vector based on how it orders eligible tasks and resource modes.

This characterisation enables the use of a surrogate model—a faster, approximate predictor—to estimate the fitness of new, unevaluated heuristic rules generated by the genetic programming process. Experimental results show this hybrid approach identifies high-quality scheduling rules significantly faster than the previous state-of-the-art GP method, while adding only marginal computational overhead. The surrogate model effectively guides the evolutionary search, leading to improved efficiency. The work, accepted by the IEEE Congress on Evolutionary Computation 2026, demonstrates a practical pathway to applying advanced AI optimization to dynamic, real-world scheduling problems that were previously too slow to solve with high-quality heuristics.