Genetic programming evolves better project scheduling heuristics efficiently
Surrogate-Assisted Genetic Programming with Phenotypic Characterisation in Dynamic Multi-Mode Project Scheduling
Neural and Evolutionary ComputingArtificial Intelligence
Summary
Scheduling projects with limited resources and uncertain task times is tricky. The authors show that using genetic programming (GP) with special shortcuts, called surrogates, helps find good scheduling rules faster. They study how to summarize GP programs in different ways to make these shortcuts work better. Their findings show that how you summarize matters for removing repeating candidates and keeping useful variety in solutions. Combining duplicate removal and shortcut checks leads to the best results.
What this means in practice
- •For project management software teams: Improve automatic scheduling recommendations for complex projects with varying resources and uncertain task durations using efficient genetic programming shortcuts.
- •For manufacturing operations planners: Generate better scheduling rules for production lines where tasks have different modes and limited resources, saving time on simulation evaluations.
Authors
Yuan Tian, Yi Mei, Mengjie Zhang
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.