arXiv:2601.14485cs.AI2026-01中稿 · the Pacific Rim In…被引 2

用拐点筛选提升遗传编程的活动分组效率,解决大规模项目调度难题。

Scalable Knee-Point Guided Activity Group Selection in Multi-Tree Genetic Programming for Dynamic Multi-Mode Project Scheduling

  • 基于拐点识别候选活动对,减少组合搜索空间。
  • 在大规模实例上表现优于传统逐个选择的方法。
  • 适合需要高效调度复杂项目的工程场景。

动态多模式资源约束项目调度问题需同时决策活动执行顺序与执行模式。遗传编程作为超启发式方法,常用于演化优先规则以指导从当前可执行集合中选择活动-模式对。近期提出活动分组选择策略,每次决策选取一组活动而非单个,通过考虑活动间依赖性提升调度效果。然而该策略在大规模实例中存在可扩展性问题。本文引入基于拐点的筛选机制,在评估组合前识别有潜力的活动对:先使用活动排序规则对所有可执行活动-模式对进行排序,再通过拐点选择确定候选对,最后由分组选择规则选出最优组合。构建多树遗传编程框架,同步演化两类规则。实验表明,该方法在大规模实例中具有良好的可扩展性,多数情况下优于采用序列决策的遗传编程方法。

原文摘要 · Abstract (English)

The dynamic multi-mode resource-constrained project scheduling problem is a challenging scheduling problem that requires making decisions on both the execution order of activities and their corresponding execution modes. Genetic programming has been widely applied as a hyper-heuristic to evolve priority rules that guide the selection of activity-mode pairs from the current eligible set. Recently, an activity group selection strategy has been proposed to select a subset of activities rather than a single activity at each decision point, allowing for more effective scheduling by considering the interdependence between activities. Although effective in small-scale instances, this strategy suffers from scalability issues when applied to larger problems. In this work, we enhance the scalability of the group selection strategy by introducing a knee-point-based selection mechanism to identify a promising subset of activities before evaluating their combinations. An activity ordering rule is first used to rank all eligible activity-mode pairs, followed by a knee point selection to find the promising pairs. Then, a group selection rule selects the best activity combination. We develop a multi-tree GP framework to evolve both types of rules simultaneously. Experimental results demonstrate that our approach scales well to large instances and outperforms GP with sequential decision-making in most scenarios.

项目调度遗传编程多模式调度分组选择

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。