Does Size Generalization Imply Disruption Robustness? A Pre-Registered Study of GNN–PPO Scheduling Policies for the Dynamic Flexible Job-Shop Problem

기술 요약: 크기 일반화가 교란 강건성을 의미하는가?

문제 정의
본 연구는 작업(operation)이 적절한 기계에 시간에 따라 할당되어야 하는 조합 최적화 과제인 동적 및 확률적 유연 직업 숍 문제(Dynamic and Stochastic Flexible Job-Shop Problem, FJSP)를 다룬다. 정적인 결정론적 버전과 달리, 이 문제는 세 가지 유형의 불확실성을 포함한다: 동적 작업 도착(포아송 프로세스로 모델링), 확률적 처리 시간(로그-정규 승수), 그리고 기계 고장(로그-정규 수리 시간을 갖는 지수적 고장 시간). 심층 강화 학습(DRL)을 그래프 신경망(GNN)과 결합하는 방식은 더 큰 인스턴스 크기에 대한 일반화와 단일 유형의 교란 처리에 있어 유망함을 보여주었으나, 단일 정책이 크기 일반화(학습 시 본 것보다 큰 인스턴스에서 잘 작동함)와 다중 교란 강건성(기계 고장, 확률적 시간, 동적 도착의 동시 발생 처리)을 동시에 달est할 수 있는지는 아직 검증되지 않았다.

방법론
연구진은 관계형 그래프 동형 네트워크(Relational Graph Isomorphism Network, GIN) 인코더와 근사 정책 최적화(Proximal Policy Optimization, PPO) 에이전트를 평가하기 위해 사전 등록된 통계적으로 엄격한 프로토콜을 채택하였다.

• 아키텍처: 정책은 세 가지 엣지 유형(작업 내 선행 관계, 기계 경쟁, 작업-기계 적격성)을 별도의 선형 변환을 통해 구분하여 집계하는 관계형 GIN을 활용한다. 이 설계는 완전한 동종(homogeneous) 표현과 완전한 이종(heterogeneous) 표현 사이의 중간 단계에 위치한다. 액터 헤드(actor head)는 인스턴스 크기에 관계없이 후보 작업에 대한 로짓(logits)을 생성하므로, 파라미터 수가 작업 수에 의존하지 않는다.
• 학습 및 보상: 에이전트는 MaskablePPO를 사용하여 학습되었다. 강건성을 테스트하기 위해 연구는 두 가지 보상 구조를 평가하였다: 메이크스팬(makespan)을 최소화하는 기본 잠재 기반 보상, 그리고 교란 후 계획된 시작 시간으로부터의 편차를 페널티로 부여하는 "불안정성 페널티"($\kappa \cdot \Delta_{inst}$)를 포함한 확장 버전이다.
• 실험 설계: 연구는 HARKing(결과를 알고 난 뒤 가설을 세우는 행위)을 피하기 위해 고정된 결정 규칙과 함께 다섯 가지 사전 등록된 가설(H1–H5)을 설정하였다.
  • 베이스라인: 정책은 9가지 우선순위 디스패칭 규칙(PDR), 튜닝된 유전 알고리즘(GA), 그리고 정밀 제약 프로그래밍(CP-SAT) 솔버와 비교되었다.
  • 벤치마크: 평가는 Fisher–Thompson 및 Lawrence 패밀리(JSSP)와 7개의 Brandimarte 인스턴스(FJSP) 및 합성 확장판을 포함한 43개 인스턴스에 걸쳐 수행되었다.
  • 통계 프로토콜: 비교 분석에는 윌콕슨 부호 순위 검정(Wilcoxon signed-rank tests)을, 다중 방법 순위 산정에는 프리드만-네메니 검정(Friedman–Nemenyi tests)과 임계 차이 도표(critical-difference diagrams)를 사용하였다. 효과 크기(effect sizes)도 전반적으로 보고되었다.

주요 결과
다섯 가지 사전 등록 가설 중 네 가지는 기각되었고, 하나는 채택되었다. 결과는 다음과 같다:

1. 정적 경쟁력 (H1 - 기각): GNN-PPO 정책은 정적 인스턴스에서 최적의 디스패칭 규칙을 능가하지 못했다. 정책의 평균 상대 백분율 편차(RPD)는 24.82%였으며, 이는 최적의 PDR(FIFO)의 18.96%와 비교된다. 이 정책은 모든 FJSP 인스턴스에서 패배했으며, JSSP 인스턴스의 18.6%에서만 승리했다.
2. 크기 일반화 (H2 - 채택): 정책은 학습 세트보다 1.5배에서 3.0배 큰 인스턴스 크기로 성공적으로 일반화되었다. 절대적인 RPD는 최적의 PDR에 비해 경쟁력이 낮았지만, 10가지 방법들 사이에서의 순위는 모든 크기 계층에서 최적의 PDR의 순위보다 유의미하게 나쁘지 않았다. 이는 절대적인 솔루션 품질보다는 상대적 경쟁력의 전이를 나타낸다.
3. 다중 교란 강건성 (H3 - 기각): 정책은 아홉 가지 서로 다른 교란 체제(고장, 확률적 시간, 도착의 조합) 하에서 강건성에 실패했다. 모든 체제에서 정책의 강건성 지수(Robustness Index, RI)는 최적의 PDR보다 유의미하게 낮았다. 특히 "동적 도착" 축은 학습 중에 보지 못한 분포 변화(에피소드 중간의 작업 삽입)를 나타내어 매우 치명적이었다.
4. 교란 인식 보상 (H4 - 기각): 보상에 불안정성 페널티($\kappa > 0$)를 추가하는 것은 강건성을 개선하지 못했다. 오히려 이는 명목상(undisturbed) 성능의 붕괴를 초래하여 RPD를 46.6에서 106.0 퍼센트 포인트까지 증가시켰다. 연구는 이 실패의 원인을 에이전트를 교란이 없는(nominal) 에피소드에 노출시키지 않은 채 도메인 무작위화된 교란 에피소드에서만 학습시킨 결과로 진단한다.
5. 결정 지연 시간 (H5 - 엄격한 임계값 하에 기각): 정책의 결정 지연 시간(4–11 ms)은 크고 어려운 인스턴스에서 CP-SAT보다 몇 자릿수 더 빨랐으나, 사전 등록된 엄격한 임계값(CP-SAT 시간의 1% 미만)을 충족하는 데는 실패했다(43개 중 42개 인스턴스). 이 실패는 CP-SAT가 문제를 거의 즉각적으로 해결하는 작은 인스턴스들로 인해 발생한 수학적 아티팩트(artifact)에 의한 것이었다.

의의 및 주장
본 논문의 핵심 기여는 솔루션 품질 측면에서의 긍정적인 결과가 아니라, GNN-PPO 스케줄링 정책의 한계를 통계적으로 엄격하게 규명한 진단에 있다. 저자들은 크기 일반화와 다중 교란 강건성이 동일한 아키텍처에서 자동으로 발생하는 하나의 '패키지'가 아니라 분리된 속성이라고 주장한다.

• 아키텍처 전이 vs. 경쟁력: 본 연구는 크기 불변 아키텍처가 절대적인 용량은 약하더라도 순위 상대적 경쟁력(크기가 커져도 다른 방법들과 비교했을 때 "그만큼의" 수준을 유지하는 능력)을 전이할 수 있다는 경험적 증거를 제공한다.
• 공동 목표의 비용: H3와 H4의 기각은 정책이 여러 유형의 교란에 대해 강건성을 최적화하면서 동시에 명목 성능을 유지하는 것이 (특정 아키텍처나 학습 체계의 조정 없이는) 불가능함을 시사한다. "불안정성 페널티"가 실패한 이유는 (명목 에피소드 노출이 없는) 도메인 무작위화 학습 체계가 보상 설계와 호환되지 않았기 때문이다.
• 방법론적 엄격성: 가설과 결정 규칙을 사전 등록함으로써, 연구는 설명되지 않은 실패가 빈번한 DRL 스케줄링 문헌의 경향에 맞서 방어 가능한 '부정적 결과(negative result)'를 제시한다. 연구는 단순히 "분포 변화"와 같은 모호한 표현 대신, 구체적인 실패 메커니즘(예: 학습 시 명목 에피소드 제외의 영향)을 식별한다.

저자들은 실무자들이 크기 일반화 주장만으로 교란 강건성을 추론해서는 안 된다고 결론짓는다. 대신, 이러한 능력들은 별도의 평가와 엔지니어링이 필요한 독립적인 설계 축으로 취급되어야 한다. 연구는 교란 발생 시 즉각적인 대응책으로서 빠른 반응형 GNN 정책을 사용하고, 동시에 더 높은 품질의 솔루션을 생성하기 위해 GA나 CP-SAT와 같은 느린 솔버를 병렬로 실행하는 하이브리드 배포 전략을 제안한다.