Story
Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling
Key takeaway
Researchers developed a new algorithm to help manage changing project schedules and resource constraints more efficiently. This could improve how organizations plan and adapt large, complex projects.
Quick Explainer
The researchers proposed a new approach to enable surrogate-assisted genetic programming for dynamic, resource-constrained project scheduling. The key idea is to capture the ranking behavior of the scheduling heuristics, rather than just their fitness values, and use this as a surrogate model to estimate the quality of new heuristics generated by the genetic programming process. This rank-based phenotypic characterization allows the surrogate model to effectively guide the search towards high-performing scheduling policies, while requiring fewer expensive fitness evaluations compared to prior methods. The distinctive aspect is the suitability of this approach for the dynamic, multi-mode project scheduling problem, which involves both ranking and subset selection of eligible activities.
Deep Dive
Technical Deep Dive: Surrogate-Assisted Genetic Programming for Dynamic Multi-Mode Project Scheduling
Overview
This research proposes a new phenotypic characterization (PC) scheme to enable surrogate-assisted genetic programming (GP) for the dynamic multi-mode resource-constrained project scheduling problem (DMRCPSP). The PC scheme captures the ranking behavior of GP heuristics over eligible activities and activity groups, allowing a surrogate model to estimate the fitness of unevaluated GP individuals.
Problem & Context
- DMRCPSP requires making real-time scheduling decisions under changing project states and resource availability
- GP can effectively evolve heuristic rules for DMRCPSP, but the evolutionary process relies on many expensive fitness evaluations via simulation
- Surrogate models can reduce evaluation cost, but require problem-specific PC schemes to capture heuristic behavior
- Existing PC schemes are not suitable for DMRCPSP due to its unique decision structures involving both ranking and subset selection
Methodology
- Proposed a rank-based PC scheme that extracts the ranking behavior of GP heuristics across representative decision situations
- Integrated the PC scheme into a surrogate-assisted GP algorithm, using nearest-neighbor regression to estimate fitness of intermediate offspring
- Introduced an offspring multiplier parameter to control the number of intermediate offspring generated per generation
Data & Experimental Setup
- Evaluated on 3 DMRCPSP scenarios with varying precedence complexity and resource constraints
- Compared the proposed SKGGP algorithm against the baseline KGGP algorithm from prior work
- Ran 30 independent trials of each algorithm with 100 generations and 1000 population size
Results
- SKGGP with larger offspring multipliers (2, 4) outperformed KGGP across all scenarios
- SKGGP could identify high-quality heuristics using 20-40% fewer expensive fitness evaluations
- Surrogate precision decreased as offspring multiplier increased, but still enabled effective offspring selection
Limitations & Uncertainties
- Surrogate model's precision limited when selecting from a large number of intermediate offspring
- Expanding the surrogate database and exploring more expressive PC schemes could improve accuracy
What Comes Next
- Investigate techniques to maintain surrogate precision with larger offspring populations
- Explore alternative machine learning models for the surrogate beyond nearest-neighbor regression
- Assess the proposed approach on additional DMRCPSP problem instances and configurations
