RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

이 논문은 복잡한 특징 공학과 그래프 기반 아키텍처에 의존하지 않고, 4 가지 핵심 상태와 변형된 트랜스포머를 활용한 경량화 DRL 프레임워크인 'ReSched'를 제안하여 유연 작업장 스케줄링 문제 (FJSP) 에서 기존 최첨단 방법보다 우수한 성능과 일반화 능력을 입증했습니다.

핵심

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

공장을 상상해 보세요. 수많은 **작업 (Job)**들이 있고, 각각의 작업은 여러 단계로 나뉘어 있습니다. 이 작업들을 처리할 수 있는 **기계 (Machine)**들도 여러 대 있습니다.

• 문제: 어떤 기계가 어떤 작업을 먼저 처리해야 할지, 그리고 각 기계가 언제까지 일을 끝낼지 결정해야 합니다.
• 목표: 모든 작업을 가장 빨리 끝내는 것 (최소 시간).

기존의 인공지능 (AI) 방법들은 이 문제를 해결하기 위해 너무 많은 정보를 필요로 했습니다. 마치 운전할 때 차의 속도, 연료, 엔진 온도뿐만 아니라 지난 10 년간의 주행 기록까지 모두 기억해야만 다음에 어떻게 운전할지 결정하는 것처럼, 매우 복잡하고 비효율적이었습니다.

💡 RESCHED 의 혁신: "간단하게, 하지만 똑똑하게"

이 논문은 **"복잡한 것을 단순하게 만들면 오히려 더 똑똑해질 수 있다"**는 아이디어를 제시합니다.

1. 상태 (State) 의 단순화: "과거의 짐을 내려놓으세요"

기존 AI 는 과거의 모든 기록을 기억하며 복잡한 특징 (20 개 이상의 수동으로 만든 정보) 을 사용했습니다. 하지만 RESCHED 는 **"지금 당장 필요한 4 가지 정보만 보면 된다"**고 말합니다.

• 비유: 요리사를 생각해보세요.
  • 기존 방법: "어제 내가 어떤 재료를 썼는지, 10 분 전 오븐 온도가 몇 도였는지, 그리고 내일 날씨가 어떻게 될지까지 모두 기억하며 요리를 한다." (너무 복잡함)
  • RESCHED 방법: "지금 냄비에 있는 재료 (작업), 지금 사용 중인 가스불의 상태 (기계), 그리고 이 요리에 걸리는 시간 (소요 시간) 만 보면 된다."
  • 효과: 불필요한 과거 정보 (과거의 기록) 를 버리고, 현재 상황에 집중함으로써 AI 가 훨씬 더 빠르게 배우고 결정할 수 있게 됩니다.

2. 아키텍처 (구조) 의 변화: "트랜스포머 (Transformer) 의 활용"

RESCHED 는 최신 AI 기술인 **트랜스포머 (Transformer)**를 사용합니다. 이는 구글 번역기나 챗봇이 사용하는 기술로, 문장 전체의 맥락을 한 번에 파악하는 데 탁월합니다.

• 작업과 기계의 관계:
  • 작업 (Operation) branch: 같은 제품 (Job) 을 만드는 과정들 사이의 순서를 파악합니다. (예: "먼저 페인트칠을 하고, 그 다음에 건조해야 한다")
  • 기계 (Machine) branch: 여러 대의 기계가 서로 어떻게 협력해야 하는지 파악합니다.
• 핵심 기술 (RoPE 와 크로스 어텐션):
  • RoPE (회전 위치 인코딩): 작업의 순서가 중요할 때, "무엇이 먼저고 무엇이 나중인지"를 숫자로만 세는 게 아니라, 상대적인 거리를 자연스럽게 이해하게 해줍니다. (예: "첫 번째 작업"과 "두 번째 작업"의 관계)
  • 크로스 어텐션: 기계가 너무 많고 작업이 너무 많을 때 (1 대의 기계가 10 개 이상의 작업을 기다리는 상황), 기계가 자신의 정보도 잊지 않고 작업 정보를 잘 받아들이도록 도와줍니다.

🏆 결과: 왜 이것이 대단한가요?

1. 압도적인 성능: RESCHED 는 기존의 수동 규칙 (사람이 정한 단순한 규칙) 이나 최신 AI 방법들보다 훨씬 더 빠르고 효율적인 스케줄을 만들어냅니다.
2. 범용성 (Generalization):
   • 비유: 이 시스템은 "작은 공장에서 일하는 법"을 배웠지만, 거대한 공장에 가도 즉시 적응합니다.
   • 기존 AI 는 공장 크기가 바뀌면 다시 처음부터 배워야 했지만, RESCHED 는 크기가 다른 문제 (작은 공장부터 거대 공장까지) 도 잘 해결합니다.
   • 심지어 공장의 종류가 조금씩 달라져도 (기계 고정형, 흐름형 등) 별도의 수정 없이 똑같은 모델로 해결합니다.
3. 빠른 속도: 학습이 끝나면, 실제 문제를 해결하는 데 걸리는 시간이 매우 짧습니다. 복잡한 계산을 기다릴 필요 없이 즉시 답을 내놓습니다.

🚀 결론: "복잡함을 덜어내면 진짜 지능이 나온다"

이 논문은 **"더 많은 정보를 넣는 것이 답이 아니다"**라고 말합니다. 오히려 필요한 정보만 깔끔하게 정리하고 (최소 상태 표현), 이를 처리하는 **지능적인 구조 (트랜스포머)**를 만들면, AI 는 훨씬 더 강력하고 유연하게 문제를 해결할 수 있습니다.

RESCHED 는 공장의 혼란을 정리하는 초고속, 초지능 스케줄러로, 미래의 스마트 팩토리와 물류 시스템을 바꿀 잠재력을 가지고 있습니다.

---

한 줄 요약:

"과거의 복잡한 기록을 버리고 '지금 당장 필요한 4 가지 정보'만 보고, 최신 AI 기술을 활용해 공장의 모든 작업을 가장 빠르게 끝내는 RESCHED라는 새로운 시스템을 개발했습니다."

기술 요약

1. 문제 정의 (Problem Definition)

이 논문은 유연한 작업장 스케줄링 문제 (Flexible Job Shop Scheduling Problem, FJSP) 를 해결하기 위한 새로운 심층 강화학습 (DRL) 프레임워크인 RESCHED를 제안합니다.

• FJSP 의 복잡성: 작업 (Job) 은 여러 작업 (Operation) 으로 구성되며, 각 작업은 호환 가능한 여러 대의 기계 (Machine) 중 하나에서 처리될 수 있습니다. 이는 기계 할당과 작업 순서 결정이라는 두 가지 결합된 의사결정을 필요로 합니다.
• 기존 방법의 한계:
  • 복잡한 상태 표현: 기존 DRL 기반 방법들은 20 개 이상의 수동으로 설계된 (handcrafted) 특징(feature) 과 복잡한 이분 그래프 (disjunctive graph) 구조에 의존합니다. 이는 불필요한 중복성을 포함하며, 과거의 건설 데이터를 상태에 포함시키는 것이 오히려 학습을 저해할 수 있음을 발견했습니다.
  • 비효율적인 아키텍처: 대부분의 기존 방법은 그래프 어텐션 네트워크 (GAT) 를 사용하는데, 이는 긴 범위의 의존성을 포착하기 위해 깊은 레이어 쌓기를 요구하거나 선형 어텐션 메커니즘의 한계로 인해 복잡한 비국소적 상호작용을 모델링하기 어렵습니다.
  • 휴리스틱 의존성: 행동 공간 (action space) 을 줄이기 위해 휴리스틱 규칙을 사용하는 것은 일반화 능력을 저하시키고 최적 해를 놓칠 수 있습니다.

2. 방법론 (Methodology)

RESCHED 는 상태 표현의 단순화와 Transformer 기반 아키텍처의 혁신을 통해 문제를 재정의합니다.

2.1. 간소화된 상태 표현 (Simplified State Representation)

기존의 복잡한 특징 공학을 배제하고, 마르코프 결정 과정 (MDP) 관점에서 FJSP 를 재해석하여 단 4 가지 핵심 특징만으로 상태를 구성합니다.

• 핵심 아이디어: 각 스케줄링 단계를 독립적인 서브문제 (subproblem) 로 간주하여 과거의 이력 (historical dependencies) 을 제거합니다.
• 4 가지 특징:
  1. 작업 가용 시간 (Operation Available Time): 선행 작업이 완료된 시점.
  2. 기계 가용 시간 (Machine Available Time): 해당 기계가 다음 작업을 시작할 수 있는 시점.
  3. 처리 시간 (Duration): 특정 기계에서 작업을 처리하는 데 걸리는 시간.
  4. 최소 처리 시간 (Minimum Duration): 해당 작업이 처리 가능한 모든 기계 중 가장 짧은 처리 시간 (작업 난이도의 하한선).
• 그래프 구조: 작업 간 선후행 관계 (O2O) 와 작업 - 기계 연결 (O2M) 은 특징이 아닌 그래프 구조로 명시적으로 인코딩됩니다. 이를 통해 불필요한 특징과 보조 변수 추적을 제거합니다.

2.2. 듀얼 브랜치 Transformer 아키텍처 (Dual-Branch Transformer Architecture)

기존 GNN 기반 정책 네트워크를 대체하여 Transformer를 기반으로 한 구조를 도입했습니다. 스케줄링 문제의 특수성을 반영한 세 가지 주요 개선 사항이 적용되었습니다.

1. 작업 브랜치 (Operation Branch) - RoPE 적용:

   • 작업 내의 순서 (O2O 의존성) 를 모델링하기 위해 **회전 위치 임베딩 (Rotary Positional Embedding, RoPE)**을 도입했습니다.
   • 추가 학습 파라미터 없이 작업 내 상대적 거리를 효과적으로 인코딩하여, 인덱스 기반 위치 인코딩보다 강력한 일반화 능력을 제공합니다.

2. 기계 브랜치 (Machine Branch) - Edge-in-Attention:

   • 작업과 기계 간의 상호작용 (처리 시간 등) 을 모델링하기 위해 **크로스 어텐션 (Cross-Attention)**을 사용합니다.
   • 기존 방법과 달리 엣지 특징 (처리 시간) 을 어텐션 점수 조절이 아닌 값 벡터 (Value Vector) 에 직접 임베딩하여, 엣지 속성이 최종 표현에 직접적으로 영향을 미치도록 합니다.

3. 자기 기반 크로스 어텐션 (Self-based Cross-Attention):

   • 작업 수에 비해 기계 수가 훨씬 적은 (예: 10:1 이상) 구조적 불균형을 해결하기 위해 고안되었습니다.
   • 기계 노드가 다른 작업 노드들의 정보를 집계할 때, 자기 자신 (Self) 에게도 어텐션 가중치를 부여하여 기계 고유의 정보가 과도한 작업 정보에 의해 희석 (dilution) 되는 것을 방지하고 학습 안정성을 높입니다.

2.3. 의사결정 및 보상 (Decision-Making & Reward)

• 행동: 각 단계에서 가능한 작업 - 기계 쌍 중 하나를 선택합니다. 휴리스틱으로 행동 공간을 제한하지 않고, 자연스러운 선후행 제약만 적용합니다.
• 보상: 실제 완료 시간 (Makespan) 의 변화가 아닌, 예측된 하한선 (Estimated Lower-bound) Makespan의 감소량을 보상으로 사용합니다. 이는 학습 효율성을 높이고 과적합을 방지합니다.
• 학습 알고리즘: 구현의 단순성과 상태/아키텍처 설계의 영향을 분리하기 위해 REINFORCE 알고리즘을 사용했습니다 (PPO 버전도 부록에서 검증됨).

3. 주요 기여 (Key Contributions)

1. 최소화된 상태 설계: FJSP 의 MDP 를 재검토하여 4 가지 핵심 특징과 그래프 구조만으로 완전한 상태 표현을 달성했습니다. 이는 불필요한 특징, 과거 이력 추적, 보조 변수를 제거하여 모델 복잡도를 획기적으로 낮췄습니다.
2. 스케줄링 전용 Transformer 아키텍처: RoPE 를 통한 작업 내 의존성 모델링, 엣지 특징 직접 임베딩, 그리고 구조적 불균형을 해결하는 자기 기반 크로스 어텐션이 포함된 새로운 듀얼 브랜치 구조를 제안했습니다.
3. 범용성 및 SOTA 성능: FJSP 에서 기존 휴리스틱 및 최신 DRL 방법 (HGNN, DANIEL 등) 을 능가하는 성능을 달성했으며, JSSP(작업장 스케줄링) 와 FFSP(유연한 흐름 공장 스케줄링) 로의 일반화 능력도 입증했습니다.

4. 실험 결과 (Results)

• FJSP 성능: SD1, SD2 합성 데이터셋 및 Brandimarte, Hurink 등 표준 벤치마크에서 SOTA(State-of-the-Art) 성능을 기록했습니다. 특히 어려운 SD2 인스턴스에서 기존 최강 모델인 DANIEL 대비 갭 (Gap) 을 30% 이상 줄였습니다.
• 일반화 능력 (Generalization):
  • 크기 일반화: 작은 문제 (예: 10x5) 로 훈련된 모델이 훨씬 큰 문제 (40x10) 에서도 우수한 성능을 발휘했습니다.
  • 변형 일반화: 별도의 튜닝 없이 JSSP(Taillard 벤치마크) 와 FFSP(MatNet 설정) 에서도 경쟁력 있는 성능을 보였습니다. 특히 JSSP 에서 훈련된 단일 모델이 100x20 크기의 문제까지 잘 일반화되었습니다.
• 효율성: 추론 시간이 매우 짧아 실시간 스케줄링에 적합하며, OR-Tools 같은 정확한 최적화 솔버와 비교해도 계산 시간 대비 우수한 해를 제공합니다.
• 강건성: 다양한 랜덤 시드에서 일관된 성능을 보이며, 아키텍처 설계가 성능 향상의 주된 원인임을 입증했습니다.

5. 의의 및 결론 (Significance)

이 논문은 스케줄링 문제를 해결하는 DRL 접근법의 패러다임을 전환합니다.

• 단순함의 힘: 복잡한 특징 공학과 그래프 기반 인덕티브 바이어스 (inductive bias) 에 의존하지 않고, **충분한 상태 표현 (State Sufficiency)**과 **표현력 있는 일반 아키텍처 (Transformer)**의 결합이 더 강력하고 일반화 가능한 모델을 만들 수 있음을 증명했습니다.
• 범용 프레임워크: FJSP, JSSP, FFSP 등 다양한 스케줄링 변형 문제에 동일한 아키텍처를 적용할 수 있어, 실제 제조 및 물류 시스템 등 복잡한 제약 조건을 가진 다양한 자원 할당 문제에 확장 가능한 유연한 프레임워크를 제공합니다.
• 미래 지향성: KV Cache 기법을 통해 추론 속도를 이론적으로 10~40 배 가속화할 수 있는 가능성을 제시하여, 대규모 스케줄링 문제의 실시간 적용 가능성을 높였습니다.

결론적으로, RESCHED 는 복잡한 스케줄링 문제를 해결하기 위해 불필요한 복잡성을 제거하고 핵심 구조에 집중함으로써, 효율성과 성능을 동시에 달성한 새로운 기준을 제시합니다.