다중 트리 유전 프로그래밍을 위한 동적 다중 모드 프로젝트 스케줄링에서 확장 가능한 니-포인트 기반 활동 그룹 선택 방법

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

동적 다중 모드 자원 제약 프로젝트 스케줄링 문제는 활동의 실행 순서와 해당 실행 모드에 대한 결정을 동시에 내려야 하는 어려운 스케줄링 문제입니다. 유전 프로그래밍은 현재 가능한 활동-모드 쌍 집합에서 활동-모드 쌍을 선택하도록 안내하는 우선순위 규칙을 진화시키는 하이퍼 휴리스틱으로 널리 사용됩니다. 최근에는 각 의사 결정 지점에서 단일 활동이 아닌 활동 집합의 부분 집합을 선택하는 활동 그룹 선택 전략이 제안되었으며, 이는 활동 간의 상호 의존성을 고려하여 보다 효과적인 스케줄링을 가능하게 합니다. 이 전략은 소규모 문제에서는 효과적이지만, 더 큰 문제에 적용할 경우 확장성 문제가 발생합니다. 본 연구에서는 활동 조합을 평가하기 전에 유망한 활동 부분 집합을 식별하기 위해 니-포인트 기반 선택 메커니즘을 도입하여 그룹 선택 전략의 확장성을 향상시킵니다. 먼저 활동 순서 규칙을 사용하여 모든 가능한 활동-모드 쌍을 순위화하고, 니-포인트 선택을 통해 유망한 쌍을 찾습니다. 그런 다음, 그룹 선택 규칙이 최상의 활동 조합을 선택합니다. 우리는 두 가지 유형의 규칙을 동시에 진화시키기 위한 다중 트리 GP 프레임워크를 개발했습니다. 실험 결과는 제안된 방법이 대규모 문제에 잘 적용되며, 대부분의 시나리오에서 순차적 의사 결정 방식의 GP보다 우수한 성능을 보임을 보여줍니다.

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.