본 연구는 그래프 신경망(GNNs)을 이용하여 나노위성 작업 스케줄링을 보다 효율적으로 수행하는 방법을 조사합니다. 오프라인 나노위성 작업 스케줄링(ONTS) 문제는 우선 순위, 최소 및 최대 활성화 이벤트, 실행 시간 프레임, 주기 및 실행 창과 같은 서비스 품질(QoS) 고려 사항과 위성의 전력 자원 및 에너지 수집 및 관리의 복잡성에 대한 제약 조건을 고려하여 궤도에서 수행될 작업에 대한 최적의 스케줄을 찾는 것을 목표로 합니다. ONTS 문제는 기존의 수학적 공식과 정확한 방법을 사용하여 접근해왔지만, 문제의 어려운 경우에 대한 적용 가능성은 제한적입니다. 본 연구는 여행 판매원, 스케줄링 및 시설 배치 문제와 같은 최적화 문제에 효과적으로 적용된 GNN의 사용을 조사합니다. 구체적으로, GNN이 후보 솔루션의 실현 가능성 및 최적성과 관련하여 ONTS 문제의 복잡한 구조를 학습할 수 있는지 여부를 조사합니다. 또한, GNN 기반 휴리스틱 솔루션을 사용하여 ONTS 문제에 대한 더 나은 솔루션(목표 값과 관련하여)을 제공하고 최적화 비용을 줄이는 것을 평가합니다. 실험 결과, GNN은 ONTS 문제의 인스턴스에 대한 실현 가능성과 최적성을 학습할 수 있을 뿐만 아니라 훈련 중에 본 것보다 더 어려운 인스턴스로 일반화할 수 있음을 보여줍니다. 또한, GNN 기반 휴리스틱은 기존 SCIP(Solving Constraint Integer Programs) 솔버와 비교하여 시간 제한 내에 발견된 최상의 솔루션의 예상 목표 값을 45% 향상시켰고, 실현 가능한 솔루션을 찾는 데 걸리는 예상 시간을 35% 단축시켰습니다.
