[기술 요약] 통합 균질 그래프를 통한 선형 복잡도의 확장 가능한 생산 스케줄링

1. 문제 정의 (Problem Statement)

본 논문은 산업 현장의 핵심 과제인 **잡숍 스케줄링 문제(Job Shop Scheduling Problem, JSSP)**를 해결하고자 합니다. JSSP는 한정된 자원(기계)을 여러 작업(Job)에 최적으로 할당하는 조합 최적화 문제로, 다음과 같은 기존 방식의 한계를 가집니다.

• 전통적 최적화 기법: 문제 규모가 커질수록 계산 복잡도가 기하급수적으로 증가하여 실시간(Online) 적용이 불가능합니다.
• 우선순위 규칙(PDRs): 계산은 빠르지만, 미래의 병목 현상을 예측하지 못하는 근시안적(Myopic)인 특성이 있습니다.
• 기존 강화학습(RL) 접근법:
  • 고정 차원 모델: 입력 크기가 고정되어 있어 문제 규모가 변하면 재학습이 필요합니다.
  • 그래프 신경망(GNN) 기반 모델: 기존의 '이산 그래프(Disjunctive Graph)' 표현법은 기계 내 작업 간의 관계를 모두 연결하여 **이차 복잡도($O(N^2)$)**를 가지므로 대규모 문제에서 병목이 발생합니다.
  • 이종 그래프(Heterogeneous Graph) 모델: 서로 다른 노드(작업, 기계)를 처리하기 위해 별도의 파라미터가 필요하여 모델의 오버헤드가 커집니다.

2. 핵심 방법론 (Methodology)

본 논문은 **"특징 기반 균질화(Feature-based Homogenization)"**를 통해 계산 효율성과 표현력을 동시에 잡는 새로운 프레임워크를 제안합니다.

① 통합 균질 그래프 (Unified Homogeneous Graph)

기존의 밀집된(Dense) 이산 그래프 대신, 기계를 독립적인 노드로 간주하는 희소(Sparse) 이종 그래프 구조를 채택합니다.

• 구조: 작업 노드와 기계 노드를 연결하는 이분 그래프(Bipartite structure) 형태를 취합니다.
• 복잡도: 작업 간의 직접적인 연결을 제거하고 기계를 정보 허브로 활용함으로써, 에지(Edge)의 수를 작업 수($N$)에 비례하는 **선형 복잡도($O(N)$)**로 줄였습니다.

② 특징 기반 균질화 (Feature-based Homogenization)

이종 그래프의 구조적 이점을 누리면서도, 모델의 복잡도를 낮추기 위해 서로 다른 노드(작업 vs 기계)를 **하나의 공유된 잠재 공간(Shared Latent Space)**으로 투영합니다.

• 각 노드에 '노드 타입'을 나타내는 원-핫 인코딩(One-hot encoding)을 특징 벡터에 결합하여, 단일한 **균질 GNN(Graph Isomorphism Network, GIN)**이 두 노드 유형을 모두 처리할 수 있게 합니다.

③ 보상 설계 (Reward Shaping)

학습의 효율성을 높이기 위해 두 가지 보상을 결합합니다.

• Sparse Reward: 최종 Makespan(총 공정 시간)에 기반한 보상.
• Dense Shaping Reward: 작업 간의 완료 예정 시간(CLB) 편차(Spread)를 줄이는 방향으로 보상을 설계하여, 작업들이 균형 있게 진행되도록 유도합니다. (Potential-based reward shaping을 통해 최적 정책의 불변성을 보장함)

3. 주요 기여 (Key Contributions)

1. 선형 복잡도 달성: 기계 노드를 활용한 희소 그래프 구조를 통해 대규모 산업 현장에서도 실시간 추론이 가능한 $O(N)$ 복잡도를 구현했습니다.
2. 모델 효율성 극대화: 이종 레이어 없이 단일 GIN 백본을 사용하여 메모리 사용량과 추론 지연 시간을 최소화했습니다.
3. 구조적 포화 가설(Structural Saturation Hypothesis) 제안: 문제의 절대적 크기보다 **작업 대 기계 비율($J/M$)**이 정책의 성능을 결정하는 핵심 요소임을 밝혀냈습니다.
4. 제로샷 일반화(Zero-shot Generalization): 특정 규모에서 학습된 모델이 재학습 없이 훨씬 큰 규모의 문제에도 효과적으로 적용됨을 입증했습니다.

4. 실험 결과 (Results)

• 성능 비교: Taillard 및 Lawrence 벤치마크 데이터셋에서 기존의 우선순위 규칙(PDRs) 및 최신 RL 모델(Zhang et al.)보다 우수한 성능을 보였습니다.
• 확장성 및 제로샷 성능: 20×20 규모에서 학습된 단일 모델(Ours single)이 100×20과 같은 대규모 문제에서도 기존 규칙들보다 낮은 최적성 격차(Optimality Gap)를 유지하며 뛰어난 적응력을 보여주었습니다.
• 포화 지점 발견: 실험을 통해 $J/M \approx 1$인 지점(예: 20×20)이 가장 복잡한 충돌 패턴을 가지며, 이 지점에서 학습된 에이전트가 충돌 해결 로직을 내재화하여 대규모 문제를 "포화된 하위 문제들의 연속"으로 처리할 수 있음을 확인했습니다.

5. 의의 및 결론 (Significance)

본 연구는 **"유한한 수단으로 무한한 활용을 한다(Infinite use of finite means)"**는 원칙을 실천했습니다.
단순히 모델을 키우는 것이 아니라, **그래프의 구조적 특성을 영리하게 설계(Linear Complexity)**하고 학습 전략을 최적의 복잡도 지점(Structural Saturation)에 집중함으로써, 실제 산업 현장의 동적이고 대규모인 스케줄링 환경에 즉시 배포 가능한 강력하고 효율적인 AI 솔루션의 경로를 제시했습니다.