메모리 기반 개선 휴리스틱을 활용한 유연한 작업장 스케줄링

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

인터넷 4.0 시대의 스마트 제조는 대량 맞춤형 생산과 동적 생산을 요구하며, 이를 위해 더욱 발전되고 유연한 스케줄링 기술이 필요합니다. 유연한 작업장 스케줄링 문제(FJSP)는 복잡한 제약 조건과 실제 생산 시나리오와의 높은 연관성으로 인해 많은 관심을 받고 있습니다. 현재 FJSP를 위한 딥 강화 학습(DRL) 기반 접근 방식은 주로 구성적 방법을 사용합니다. 이러한 방법은 효과적이지만, 종종 최적(근사치) 솔루션을 달성하는 데 한계가 있습니다. 반면, 개선 기반 방법은 초기 솔루션의 이웃 영역을 반복적으로 탐색하며, 최적해에 더 효과적으로 접근할 수 있습니다. 그러나 FJSP의 유연한 기계 할당은 이 프레임워크 적용에 상당한 어려움을 야기하며, 여기에는 정확한 상태 표현, 효과적인 정책 학습, 효율적인 탐색 전략이 포함됩니다. 이러한 문제점을 해결하기 위해, 본 논문에서는 이기종 그래프 표현을 사용하는 메모리 기반 개선 탐색 프레임워크인 MIStar를 제안합니다. MIStar는 기계에서의 작업 순서를 명시적으로 모델링하여 스케줄링 솔루션을 정확하게 표현하는 새로운 이기종 분산 그래프를 사용합니다. 또한, 특징 추출을 위해 메모리 기반 이기종 그래프 신경망(MHGNN)을 설계하여, 정책 네트워크의 의사 결정 능력을 향상시키기 위해 과거의 정보를 활용합니다. 마지막으로, 병렬 탐욕적 탐색 전략을 채택하여 솔루션 공간을 탐색하고, 더 적은 반복 횟수로 우수한 솔루션을 얻을 수 있도록 합니다. 합성 데이터 및 공개 벤치마크에 대한 광범위한 실험 결과, MIStar는 기존의 수작업 개선 휴리스틱 및 최첨단 DRL 기반 구성적 방법보다 훨씬 우수한 성능을 보이는 것을 확인했습니다.

The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.