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

This paper proposes a surrogate-assisted Genetic Programming algorithm that utilizes a novel rank-based phenotypic characterisation scheme to significantly reduce the computational cost of evolving high-quality heuristic rules for the dynamic multi-mode resource-constrained project scheduling problem.

The Gist

The Big Picture: Managing a Chaotic Construction Site

Imagine you are the manager of a massive construction project. You have hundreds of tasks (like pouring concrete, wiring electricity, painting walls) that need to happen in a specific order. You also have limited resources (only 12 cranes, 50 electricians, etc.).

The Problem:
In the real world, things don't go exactly as planned. A crane might break down, or a delivery might be late. You don't know exactly how long a task will take until you actually start it. This is called the Dynamic Multi-Mode Project Scheduling Problem. You have to make split-second decisions on the fly: "Do I use the slow, cheap electrician or the fast, expensive one? Which task should I start next?"

The Old Way (Genetic Programming):
To solve this, researchers use a computer technique called Genetic Programming (GP). Think of this as a digital "evolutionary lab."

1. The computer creates thousands of different "rulebooks" (heuristics) for making these decisions.
2. It tests each rulebook by running a massive simulation of the construction site.
3. The best rulebooks survive and breed to create new, better rulebooks.

The Bottleneck:
The problem is that running these simulations is extremely expensive in terms of computer time. It's like trying to find the best recipe for a cake by baking 10,000 cakes and tasting them all. It takes forever and costs a fortune.

---

The Solution: The "Cheat Sheet" (Surrogate Model)

The authors propose a smarter way to do this. Instead of baking 10,000 cakes, they want to taste a tiny crumb of the batter to guess if the cake will be good.

They call this a Surrogate-Assisted Genetic Programming approach.

• The Surrogate Model: This is a "cheat sheet" or a "predictor." It's a simple mathematical model that guesses how good a rulebook is without running the full, expensive simulation.
• The Catch: To make a good guess, the predictor needs to understand the personality of the rulebook. It needs to know how the rulebook thinks, not just the final score.

The Innovation: The "Ranking Personality Test"

Here is the paper's main breakthrough. Previous methods tried to describe a rulebook's personality, but they failed for this specific construction problem because the decisions are too complex.

The authors invented a new way to describe a rulebook's personality, which they call Rank-Based Phenotypic Characterisation (PC).

The Analogy: The Job Interview
Imagine you are interviewing candidates for a job.

• The Old Way: You ask the candidate, "Who did you hire?" They say, "I hired Bob." You write down "Bob."
  • Problem: Two candidates might both hire Bob, but one hired him because he was the best, while the other hired him because he was the only one available. The old method thinks they are identical, but they aren't.
• The New Way (This Paper): You ask the candidate to rank everyone in the room. "Who is #1? Who is #2? Who is #3?"
  • You record the entire ranking list.
  • Even if two candidates pick the same #1 person, if their #2 and #3 choices are different, you know they have different "personalities."

In the paper, the computer looks at a decision moment (e.g., "Which task should I do next?"). It asks the rulebook to rank all possible tasks. It records this list of rankings as a vector (a list of numbers). This list is the rulebook's "fingerprint."

How It Works in Practice

1. Generate: The computer creates a bunch of new rulebooks (offspring).
2. Fingerprint: Instead of simulating the whole construction site, the computer quickly asks each rulebook to rank a few sample tasks. This creates their "fingerprint."
3. Predict: The computer looks at its database of previously tested rulebooks. It finds the one with the most similar fingerprint.
4. Guess: It assumes the new rulebook will perform about as well as the similar, previously tested one.
5. Select: It picks the top candidates based on this guess and only then runs the expensive, full simulation on the winners.

The Results: Faster and Smarter

The researchers tested this on three different levels of project complexity (Easy, Medium, Hard).

• Speed: The new method (called SKGGP) found high-quality rulebooks much faster than the old method. It saved about 20% to 40% of the computer time.
• Quality: The rulebooks it found were just as good (or better) than the ones found by the slow, traditional method.
• The "Sweet Spot": They tested generating different numbers of "extra" candidates to test.
  • If they generated too many extra candidates, the "cheat sheet" got confused and started making bad guesses (like a librarian trying to guess the best book from a pile of 1,000 random books).
  • If they generated a moderate amount (about double the usual number), the cheat sheet worked perfectly, finding the best candidates quickly.

Summary

Think of this paper as inventing a super-efficient hiring manager for a chaotic construction site.

• Before: The manager had to put every single job applicant through a grueling, week-long trial shift to see if they were good.
• Now: The manager gives the applicants a quick, 5-minute personality quiz (the ranking test). Based on the answers, the manager can predict who will pass the trial shift with high accuracy.
• Result: They hire the best people much faster and spend way less money on trial shifts.

This allows project managers to make better, real-time decisions without waiting days for a computer to crunch the numbers.

Technical Summary

1. Problem Definition

The paper addresses the Dynamic Multi-Mode Resource-Constrained Project Scheduling Problem (DMRCPSP).

• Context: Unlike static scheduling, DMRCPSP involves uncertainty where activity durations are unknown until execution. Decisions (which activities to start and in which mode) must be made online as the project state evolves.
• Constraints: Activities must respect precedence relationships and limited renewable resource capacities. Each activity has multiple execution modes with different durations and resource requirements.
• Objective: Minimize the overall project makespan (total duration).
• Challenge: While Genetic Programming (GP) is effective at evolving heuristic rules for these dynamic decisions, the evolutionary process is computationally prohibitive. It requires thousands of expensive simulation-based fitness evaluations to assess the quality of evolved rules, limiting scalability and real-time applicability.

2. Methodology

The authors propose a Surrogate-Assisted Genetic Programming (SAGP) framework tailored specifically for DMRCPSP. The core innovation lies in bridging the gap between GP heuristics and surrogate modeling through a novel Phenotypic Characterisation (PC) scheme.

A. The Surrogate-Assisted Framework

The algorithm follows a standard surrogate-assisted workflow:

1. Initialization: Generate an initial population of GP individuals (heuristic rules).
2. Phenotypic Characterisation (PC): Compute a PC vector for each individual based on its behavior in specific decision situations.
3. Filtering: Remove duplicate individuals based on PC vectors to avoid redundant full evaluations.
4. Offspring Generation: Generate $k \times |P|$ intermediate offspring (where $k$ is a multiplier).
5. Surrogate Estimation: Instead of running full simulations for all offspring, use a surrogate model to estimate their fitness based on their PC vectors.
6. Selection: Select the top $|P|$ offspring (based on estimated fitness) for full fitness evaluation (simulation).
7. Iteration: Repeat until the stopping criterion is met.

B. Novel Rank-Based Phenotypic Characterisation (PC)

The paper identifies that existing PC schemes (designed for single-choice problems) fail for DMRCPSP because the decision process involves both ranking (ordering activity-mode pairs) and subset selection (choosing a group of activities).

• Decision Situations: The PC scheme samples two types of decision contexts from the simulation:
  1. Activity Ordering Situations: Where the heuristic ranks eligible activity-mode pairs.
  2. Activity Group Selection Situations: Where the heuristic selects a feasible group of activities from the ranked subset.
• Vector Construction: For each situation, the heuristic assigns priority values. The ranks of all candidates (not just the selected one) are extracted to form a "decision vector."
• Final PC Vector: The concatenation of decision vectors from all sampled situations creates a numerical representation of the heuristic's behavioral profile. This captures the relative ordering logic of the rule, not just the final choice.

C. Surrogate Model

• Type: A Nearest-Neighbour (NN) regression model.
• Mechanism: To estimate the fitness of a new individual, the algorithm calculates the Manhattan distance between its PC vector and the PC vectors of the current population (which have known true fitness values). The fitness of the nearest neighbor is assigned as the estimate.
• Database Limitation: The surrogate database is reset every generation because fitness values are stochastic (dependent on random seeds) and not directly comparable across generations.

3. Key Contributions

1. First PC Scheme for DMRCPSP: The paper introduces the first phenotypic characterisation scheme capable of handling the complex, dual-stage decision-making (ranking + subset selection) inherent in DMRCPSP.
2. Rank-Based Representation: Unlike previous methods that only record the rank of the selected candidate, this scheme records the full ranking order of candidates. This preserves semantic relationships between different orderings, allowing for more accurate behavioral similarity measurements.
3. Surrogate-Assisted GP Algorithm (SKGGP): The integration of this PC scheme into a GP framework allows for the pre-selection of promising offspring, significantly reducing the number of expensive simulations required.
4. Empirical Validation: The study rigorously analyzes the impact of the offspring multiplier ($k$) and the trade-off between evaluation budget savings and solution quality.

4. Experimental Results

The proposed algorithm (SKGGP) was compared against the state-of-the-art baseline (KGGP) across three precedence complexity scenarios (Order Strength: 0.75, 0.5, 0.25).

• Performance Quality:
  • SKGGP variants with higher offspring multipliers ($k=2$ and $k=4$) consistently found higher-quality heuristic rules (lower makespan) than the baseline KGGP.
  • SKGGP achieved faster convergence, reaching optimal solutions in fewer generations.
• Evaluation Budget Savings:
  • SKGGP could achieve the same performance level as KGGP while saving 20–40% of the full fitness evaluations.
  • This indicates the surrogate model successfully filters out low-quality offspring before they undergo expensive simulation.
• Precision Analysis:
  • The surrogate model's precision (ability to correctly identify top-tier individuals) decreases as the number of intermediate offspring ($k$) increases.
  • At $k=1.5$, precision was ~80–90%. At $k=4$, it dropped to ~50–60%.
  • Despite lower precision at high $k$, the sheer volume of generated offspring meant that enough high-quality individuals were still selected to improve overall performance.
• Computational Overhead:
  • The time cost for surrogate estimation (calculating PC vectors and distance) was negligible, accounting for only 1/20 to 1/40 of the time required for a full simulation evaluation.

5. Significance

• Scalability: This work makes GP-based hyper-heuristics viable for large-scale, dynamic project scheduling problems where simulation costs were previously a bottleneck.
• Generalizability: The rank-based PC approach offers a new paradigm for characterizing heuristics in problems involving complex ordering and subset selection, potentially applicable to other dynamic scheduling domains.
• Efficiency: By enabling the discovery of high-quality rules earlier in the evolutionary process, the method supports more responsive and adaptive project management systems.

In conclusion, the paper successfully demonstrates that a carefully designed phenotypic characterisation scheme can unlock the potential of surrogate-assisted evolutionary algorithms for complex, dynamic resource-constrained problems, offering a significant reduction in computational cost without sacrificing solution quality.