HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers

이 논문은 작업장 스케줄링 문제를 이종 그래프로 모델링하고 이종 그래프 트랜스포머를 활용하여 작업 우선순위 및 기계 경쟁 관계를 구분해 학습함으로써, 기존 동종 그래프 기반 강화학습 방법보다 우수한 스케줄링 성능을 달성하는 'HGT-Scheduler'를 제안합니다.

핵심

🏭 배경: 혼란스러운 공장의 상황 (JSSP)

상상해 보세요. 거대한 공장에 여러 대의 기계와 수많은 작업 (Job) 이 있습니다.

• 작업 A는 먼저 기계 1에서 가공된 후, 기계 2로 가야 합니다.
• 작업 B는 기계 1과 기계 2를 모두 사용해야 하지만, 순서가 다릅니다.

이때 중요한 규칙이 두 가지 있습니다.

1. 순서 규칙: 작업 A 는 반드시 B 가 끝난 후에 시작해야 합니다. (이건 선후 관계입니다.)
2. 자원 규칙: 기계 1 에는 한 번에 한 작업만 할 수 있습니다. A 와 B 가 동시에 기계 1 을 원하면 누가 먼저 할지 결정해야 합니다. (이건 경쟁 관계입니다.)

이 모든 것을 고려해서 가장 빨리 모든 작업을 끝내는 순서를 찾는 것이 바로 이 논문이 다루는 **'조업 스케줄링 문제'**입니다.

---

🧠 기존 방법의 문제점: "모든 것을 똑같이 취급하는 실수"

기존의 인공지능 (딥러닝) 은 이 공장 상황을 **'동질적인 그래프'**로 보았습니다.

• 비유: 공장 지도를 그릴 때, "A 가 B 보다 먼저다"라는 화살표와 "A 와 B 가 같은 기계를 두고 다툰다"라는 화살표를 똑같은 색의 선으로만 그렸습니다.
• 문제점: 인공지능은 "이 선은 A 가 B 보다 먼저라는 뜻일까, 아니면 기계 다툼을 의미하는 걸까?"를 구분하지 못합니다. 마치 친구와의 대화 내용과 상사와의 업무 지시를 모두 같은 목소리로 전달받는 것과 비슷합니다. 중요한 뉘앙스가 사라져서 최적의 해결책을 찾기 어렵습니다.

---

💡 이 논문의 해결책: "HGT-SCHEDULER" (이질적 그래프 트랜스포머)

저자는 **"아니, 이 두 가지 관계는 완전히 다르다!"**라고 주장하며 새로운 방법을 제시했습니다.

1. 공장 지도를 '이질적'으로 그리기

이제 인공지능은 공장 지도를 그릴 때 선의 종류를 명확히 구분합니다.

• 파란색 선 (Precedes): "이 작업이 끝나야 저 작업이 시작된다"는 순서를 나타냅니다.
• 빨간색 선 (Competes): "이 작업과 저 작업은 같은 기계를 두고 경쟁한다"는 경쟁을 나타냅니다.

2. '이질적 그래프 트랜스포머 (HGT)'라는 똑똑한 관리자

이 새로운 지도를 읽는 인공지능은 HGT라는 기술을 사용합니다.

• 비유: HGT 는 공장의 현명한 감독관입니다.
  • 파란색 선 (순서) 을 볼 때는 **"다음 단계 준비가 되었나?"**를 집중해서 봅니다.
  • 빨간색 선 (경쟁) 을 볼 때는 **"기계 사용권 다툼이 심한가?"**를 집중해서 봅니다.
• 기존 방식은 모든 선을 똑같이 보느라 혼란스러웠지만, HGT 는 **관계의 종류에 따라 다른 눈 (주의 메커니즘)**을 써서 정보를 처리합니다.

---

🎓 실험 결과: 무엇이 더 잘했을까?

저자는 이 새로운 방법 (HGT-Scheduler) 을 기존 방법 (동일한 선만 쓰는 방법) 과 비교해 보았습니다.

1. 작은 공장 (FT06, 6 개 작업/6 대 기계):

   • 결과: 새로운 방법 (HGT) 이 압도적으로 잘했습니다.
   • 이유: 관계의 종류를 구분해서 보니, 인공지능이 "어, 이 작업은 기계가 비어있는데도 순서 때문에 기다려야 하는구나"라고 정확히 파악했기 때문입니다.
   • 통계: 우연히 잘한 것이 아니라, 통계적으로도 유의미하게 더 좋았습니다.

2. 큰 공장 (FT10, 10 개 작업/10 대 기계):

   • 결과: 두 방법의 차이가 크지 않았습니다.
   • 이유: 공장이 너무 크고 복잡해서, 인공지능이 학습할 시간이 부족했습니다. 새로운 방법은 더 정교한 지도를 보느라 더 많은 '학습 시간'이 필요했습니다. 시간이 더 주어진다면 새로운 방법이 더 잘할 것으로 예상됩니다.

3. 전통적인 방법 (단순 규칙):

   • 단순히 "가장 짧은 작업부터 한다"거나 "가장 긴 작업부터 한다"는 옛날 방식은 인공지능에 비해 훨씬 못했습니다.

---

🔍 핵심 교훈 (결론)

이 논문의 가장 중요한 메시지는 다음과 같습니다:

"문제의 구조를 정확히 이해하는 것이 중요합니다."

인공지능에게 공장 상황을 가르칠 때, **'순서'**와 **'경쟁'**이라는 서로 다른 의미를 가진 관계를 구별해 주면, 인공지능은 훨씬 더 똑똑한 결정을 내릴 수 있습니다. 마치 음악 선생님이 악보의 '화음'과 '리듬'을 따로 가르쳐야 학생이 더 잘 연주할 수 있는 것과 같습니다.

이 기술이 발전하면, 미래의 공장이나 물류 센터에서 인공지능이 실시간으로 가장 효율적인 작업 순서를 찾아내어, 생산 시간을 획기적으로 줄이고 비용을 아낄 수 있을 것입니다.

기술 요약

1. 문제 정의 (Problem Definition)

작업장 스케줄링 문제 (Job Shop Scheduling Problem, JSSP) 는 제한된 수의 기계에서 여러 작업 (Job) 을 처리할 때, 각 작업 내 공정의 순서 제약 (precedence constraints) 과 기계 공유로 인한 자원 제약 (resource constraints) 을 만족하면서 목표 (예: 최대 완료 시간, Makespan) 를 최소화하는 NP-난 (NP-hard) 조합 최적화 문제입니다.

• 기존 접근법의 한계: 최근 딥 강화학습 (DRL) 기반의 스케줄링 방법들은 JSSP 를 이분지 그래프 (Disjunctive Graph) 로 모델링합니다. 그러나 대부분의 기존 연구는 이 그래프를 동질적 (Homogeneous) 으로 간주하여, 작업 간 순서 제약 (Conjunctive edges) 과 기계 간 충돌 제약 (Disjunctive edges) 을 단일 관계 유형으로 합쳐버립니다.
• 핵심 문제: 이러한 단순화는 두 가지 제약이 가진 본질적인 의미 (Semantic) 의 차이를 무시합니다. 작업 순서 제약은 '상류/하류'의 시간적 흐름을, 기계 충돌 제약은 '동시성'과 '자원 경쟁'을 나타내는데, 이를 동일하게 처리하면 중요한 구조적 정보가 손실되고 신경망의 표현력이 저하됩니다.

2. 제안 방법론 (Methodology)

저자는 JSSP 를 이질적 그래프 (Heterogeneous Graph) 로 재정의하고, 이를 처리하기 위해 이질적 그래프 트랜스포머 (Heterogeneous Graph Transformer, HGT) 를 활용한 강화학습 에이전트인 HGT-Scheduler 를 제안합니다.

2.1 이질적 그래프 표현 (Heterogeneous Graph Formulation)

• 노드 (Nodes): 모든 작업 (Operation) 을 노드로 매핑합니다. (더미 노드인 Source/Sink 는 제외하고 실제 할당 대상만 사용).
• 노드 특징 (Node Features): 각 노드는 3 차원 벡터로 표현됩니다.
  1. 정규화된 처리 시간 (Normalized processing time).
  2. 완료 비율 (Completion percentage, 글로벌 시간 대비).
  3. 스케줄링 여부 플래그 (Scheduled flag, 0 또는 1).
• 엣지 (Edges) 의 이질적 구분:
  • precedes (순서): 같은 작업 내 선행/후행 관계를 나타내는 방향성 엣지.
  • competes (경쟁): 같은 기계를 필요로 하는 작업들 간의 관계를 나타내는 비방향성 엣지.
• 기존 동질적 그래프와 달리, 이 두 엣지 유형을 별도의 인접 행렬로 유지하여 구조적 차이를 명시적으로 보존합니다.

2.2 HGT 아키텍처 (Heterogeneous Graph Transformer)

• 타입 의존적 어텐션 (Type-dependent Attention): HGT 는 엣지 유형에 따라 다른 가중치 행렬을 사용하여 메시지 전달을 수행합니다.
  • precedes 엣지를 통한 메시지 전달은 작업 흐름의 지연과 하류 병목 현상을 학습합니다.
  • competes 엣지를 통한 메시지 전달은 기계 혼잡도와 자원 경쟁을 학습합니다.
• 구조: 3 개의 HGT 레이어, 4 개의 어텐션 헤드, 128 차원의 은닉층을 사용합니다. 잔차 연결 (Residual connection) 과 레이어 정규화 (Layer normalization) 를 적용하여 학습 안정성을 높였습니다.
• 풀링 (Pooling): 모든 작업 노드의 임베딩을 글로벌 어텐션 풀링 (Global Attention Pooling) 을 통해 하나의 그래프 레벨 임베딩으로 요약합니다. 이는 전체 공장의 상태를 평가하는 데 사용됩니다.

2.3 강화학습 프레임워크 (RL Formulation)

• MDP 설정: 상태는 이질적 그래프, 행동은 다음에 스케줄링할 유효한 작업 선택, 보상은 밀집 보상 (Dense Reward) 전략을 사용합니다.
  • 보상 설계: 최종 Makespan 만 보상을 주는 희소 보상 대신, 남은 작업의 이론적 하한선 (Lower bound) 변화에 기반한 밀집 보상을 매 단계 제공합니다.
• 학습 알고리즘: PPO (Proximal Policy Optimization) 를 사용하여 정책 (Actor) 과 가치 함수 (Critic) 를 학습합니다.
• 액션 마스킹 (Action Masking): 작업 순서 제약으로 인해 현재 선택 불가능한 작업들의 확률을 0 으로 강제하여 유효한 행동만 선택하도록 합니다.

3. 주요 기여 (Key Contributions)

1. JSSP 를 위한 이질적 그래프 공식화: 작업 순서와 기계 경쟁이라는 두 가지 서로 다른 의미의 제약을 명시적으로 구분하여 그래프 상태로 표현하는 새로운 프레임워크를 제시했습니다.
2. HGT 기반 스케줄러 제안: 엣지 유형에 따른 어텐션 메커니즘을 적용하여 제약 조건별 상호작용 패턴을 학습할 수 있는 HGT-Scheduler 를 개발했습니다.
3. 실증적 검증: Fisher-Thompson (FT) 벤치마크 (FT06, FT10) 에서 기존 동질적 그래프 모델 (GIN, Homo-HGT) 과 전통적 휴리스틱 (SPT, LPT) 보다 우수한 성능을 입증했습니다.
4. 아키텍처 분석: 3 레이어 구조가 최적의 성능을 제공하며, 단순한 파라미터 증가가 아닌 구조적 설계의 이점임을 증명했습니다.

4. 실험 결과 (Results)

실험은 FT06 (6 작업 x 6 기계) 과 FT10 (10 작업 x 10 기계) 인스턴스에서 수행되었으며, 50,000 스텝의 제한된 학습 예산 하에 진행되었습니다.

• FT06 (소규모) 결과:

  • HGT-Scheduler: 평균 Makespan 59.6 (최적값 55 대비 8.36% Gap).
  • 동질적 모델 (Homo-HGT): 평균 Makespan 66.0 (Gap 20.00%).
  • 통계적 유의성: HGT-Scheduler 는 동일한 아키텍처의 동질적 모델보다 통계적으로 유의미하게 우수했습니다 (p = 0.011). 이는 엣지 유형을 구분하는 것이 학습 성능을 직접적으로 향상시킨다는 가설을 입증했습니다.
  • GIN (기존 표준): 66.6 (Gap 21.09%) 으로 HGT-Scheduler 보다 성능이 떨어졌습니다.

• FT10 (대규모) 결과:

  • 성능: HGT-Scheduler (1594.2) 와 Homo-HGT (1540.6) 모두 전통적 휴리스틱과 GIN 보다 압도적으로 우수했으나, 두 트랜스포머 모델 간의 성능 차이는 통계적으로 유의하지 않았습니다 (p = 0.7751).
  • 해석: 대규모 문제에서는 이질적 그래프의 복잡한 구조를 학습하기 위해 더 긴 학습 시간 (Exploration horizon) 이 필요하며, 50,000 스텝의 제한된 예산 하에서는 동질적 모델이 더 빠르게 수렴하는 경향이 있었습니다.

• 아블레이션 연구 (Ablation Study):

  • 레이어 수: 3 레이어 구조가 최적의 성능을 보였습니다. 1 레이어는 정보 전달 범위가 부족하고, 4 레이어는 과도한 평활화 (Over-smoothing) 로 인해 성능이 저하되었습니다.
  • 파라미터 수: HGT-Scheduler 는 동질적 모델보다 약 8.3% 더 많은 파라미터를 가지지만, 이 미세한 차이는 성능 향상의 주된 원인이 아니며, 엣지 의미의 분리가 핵심임을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 구조적 표현의 중요성: JSSP 와 같은 복잡한 조합 최적화 문제에서 그래프의 이질적 구조 (Heterogeneous Structure) 를 명시적으로 모델링하는 것이 DRL 에이전트의 학습 효율성과 정책 품질을 크게 향상시킵니다.
• 학습 메커니즘의 개선: 작업 흐름과 자원 경쟁을 구분하여 학습함으로써, 에이전트는 병목 현상과 자원 충돌을 더 정확하게 식별하고 해결할 수 있게 됩니다.
• 한계 및 향후 과제: 현재 연구는 대규모 인스턴스 (FT10) 에서 제한된 학습 시간 하에 이질적 모델의 잠재력을 완전히 발휘하지 못했습니다. 향후 더 긴 학습 시간과 동적 환경 (Dynamic Job Arrivals) 에서의 적용을 통해 이 방법론의 확장성을 검증할 필요가 있습니다.

이 논문은 스케줄링 문제를 단순한 그래프가 아닌 의미가 다른 관계들이 공존하는 이질적 그래프로 접근함으로써, 딥 강화학습 기반의 최적화 성능을 한 단계 끌어올린 중요한 연구로 평가됩니다.