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

Source: arXiv - 2603.16286v1

Overview

The paper tackles the Dynamic Multi‑Mode Resource‑Constrained Project Scheduling Problem (DMRCPSP) – a real‑world challenge where project managers must continuously re‑schedule tasks as resources and project states evolve. By marrying Genetic Programming (GP) with surrogate modeling, the authors dramatically cut the time needed to evolve effective scheduling heuristics, making on‑the‑fly decision support feasible for large, complex projects.

Key Contributions

• Rank‑based phenotypic characterisation (PC): A novel way to turn a GP‑generated heuristic rule into a fixed‑length vector by ranking eligible activity‑mode pairs and activity groups in each decision context.
• Surrogate‑assisted GP framework: Integrates the PC vectors with a regression‑type surrogate model that predicts a heuristic’s fitness without running costly simulations.
• Efficiency gains: Demonstrates that the surrogate‑guided GP finds high‑quality scheduling rules earlier and with only a modest overhead compared to a state‑of‑the‑art GP baseline.
• Offspring selection insight: Shows that the surrogate’s fitness estimates can bias the evolutionary search toward promising offspring, improving overall evolutionary efficiency.

Methodology

1. Problem encoding:

   • Each GP individual encodes a heuristic rule that decides which activity‑mode pair to schedule next.
   • In a given project state, the rule produces an ordered list of feasible actions.

2. Phenotypic characterisation:

   • For every decision situation, the ordered list is transformed into a rank vector (e.g., “activity A‑mode 2 is ranked 1st, activity B‑mode 1 is ranked 2nd, …”).
   • Aggregating these vectors across many sampled states yields a fixed‑size PC vector that captures the rule’s behaviour independent of its syntactic GP representation.

3. Surrogate model construction:

   • A lightweight regression model (e.g., Random Forest or Gradient Boosting) is trained on a small set of evaluated GP individuals, using their PC vectors as inputs and their true simulation‑based fitness as targets.

4. Surrogate‑assisted evolution:

   • During each GP generation, the surrogate predicts fitness for newly created offspring.
   • Only the most promising candidates (according to the surrogate) are passed to the expensive simulation for true evaluation; the rest are discarded or kept for later re‑evaluation.

5. Iterative refinement:

   • The surrogate is periodically retrained with newly obtained true fitness values, keeping its predictions aligned with the evolving population.

Results & Findings

• The surrogate‑assisted approach consistently discovers higher‑quality heuristics earlier in the run.
• Offspring selected by the surrogate exhibit better average true fitness, confirming that the surrogate provides useful guidance rather than just noise.
• The rank‑based PC proved robust across different project instances, handling varying numbers of activities, modes, and resource constraints.

Practical Implications

• Faster heuristic generation: Project‑management software can now evolve custom scheduling rules on‑the‑fly, adapting to new resource availabilities without waiting hours for a full simulation‑based search.
• Scalable decision support: The method scales to larger projects (hundreds of activities) where traditional GP would be prohibitively slow.
• Plug‑and‑play surrogate: Because the PC is derived from the behaviour of a rule rather than its syntax, the surrogate can be swapped out (e.g., using neural nets) without redesigning the GP pipeline.
• Real‑time re‑planning: In industries like construction, aerospace, or software release planning, the approach enables near‑real‑time re‑scheduling when unexpected events (resource outages, scope changes) occur.

Limitations & Future Work

• Surrogate fidelity: The surrogate’s accuracy depends on the diversity of training samples; in highly non‑linear or noisy scheduling landscapes, prediction errors can mislead the search.
• Domain‑specific PC design: The rank‑based PC works well for DMRCPSP but may need adaptation for other combinatorial optimisation problems (e.g., vehicle routing).
• Computational budget trade‑off: While overall runtime drops, there is still a modest overhead for training and updating the surrogate; tighter budgets may require more aggressive pruning strategies.
• Future directions suggested by the authors:
  • Explore deep learning‑based surrogates that can capture richer behavioural patterns.
  • Extend the framework to multi‑objective project scheduling (e.g., balancing cost, risk, and makespan).
  • Investigate transfer learning: re‑using surrogate knowledge across similar projects to further reduce evaluation cost.

Authors

• Yuan Tian
• Yi Mei
• Mengjie Zhang

Paper Information

• arXiv ID: 2603.16286v1
• Categories: cs.NE, cs.AI
• Published: March 17, 2026
• PDF: Download PDF