Search papers, labs, and topics across Lattice.
This paper addresses the dynamic multi-mode resource-constrained project scheduling problem (DMRCPSP) by proposing a novel rank-based phenotypic characterisation (PC) scheme for genetic programming (GP). The PC scheme captures heuristic-driven ordering of activity-mode pairs and activity groups, enabling the construction of a surrogate model to estimate GP individual fitness. Experiments demonstrate that the surrogate-assisted GP algorithm identifies high-quality heuristic rules for DMRCPSP more efficiently than existing GP approaches.
A new rank-based phenotypic characterization scheme slashes the computational cost of genetic programming for dynamic project scheduling, enabling faster discovery of high-quality heuristic rules.
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.
