RESCHED: 트랜스포머 기반 아키텍처와 단순화된 상태를 활용한 유연한 직렬 공정 스케줄링 재고

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

최근 몇 년 동안, 특히 딥 강화 학습(DRL)에 기반한 신경망 접근 방식이 유연한 직렬 공정 스케줄링 문제(FJSP)에 대한 연구에서 주목받고 있습니다. 그러나 기존 방법들은 복잡한 특징 엔지니어링을 필요로 하는 상태 표현(종종 20개 이상의 수동으로 설계된 특징 필요)과 그래프 기반 신경망 아키텍처에 의존합니다. 본 연구에서는 모델링 복잡성을 줄이고 FJSP에 대한 보다 일반화 가능한 프레임워크를 발전시키기 위해, 스케줄링 공식과 모델 설계를 재고한 최소주의적인 DRL 프레임워크인 extsc{ReSched}를 제안합니다. 첫째, FJSP의 마르코프 결정 프로세스(MDP) 공식을 재검토하여, 하위 문제 기반 관점을 통해 상태 공간을 네 가지 필수 특징으로 축소하고, 과거 의존성을 제거했습니다. 둘째, 스케줄링 작업에 맞게 설계된 세 가지 경량화되지만 효과적인 아키텍처 수정 사항을 추가하여 트랜스포머 블록과 점곱 어텐션을 사용했습니다. 광범위한 실험 결과, extsc{ReSched}는 기존의 디스패칭 규칙과 최첨단 DRL 방법보다 FJSP에서 더 우수한 성능을 보였습니다. 또한, extsc{ReSched}는 직렬 공정 스케줄링 문제(JSSP)와 유연한 흐름 공정 스케줄링 문제(FFSP)에도 잘 적용되어, 이러한 변형에 특화된 신경망 기반 방법과 경쟁력 있는 성능을 달성했습니다.

Neural approaches to the Flexible Job Shop Scheduling Problem (FJSP), particularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely on complex feature-engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FJSP, we introduce \textsc{ReSched}, a minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formulation of FJSP, we condense the state space to just four essential features, eliminating historical dependencies through a subproblem-based perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that \textsc{ReSched} outperforms classical dispatching rules and state-of-the-art DRL methods on FJSP. Moreover, \textsc{ReSched} also generalizes well to the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.