ReLA: 강화 학습을 이용한 작업 스케줄링을 위한 표현 학습 및 집계

ReLA: Representation Learning and Aggregation for Job Scheduling with Reinforcement Learning

작업 스케줄링은 다양한 제약 조건 하에서 작업 단계를 기계에 할당하는 데 널리 사용되는 제조 시스템의 핵심 기술입니다. 기존 솔루션은 문제 규모가 증가함에 따라 긴 실행 시간 또는 불충분한 스케줄링 품질의 한계를 가지고 있습니다. 본 논문에서는 구조화된 표현 학습과 집계를 기반으로 하는 강화 학습(RL) 스케줄러인 ReLA를 제안합니다. ReLA는 자기 주의(self-attention) 및 컨볼루션을 사용하는 두 개의 내부 개체 학습 모듈과 크로스 어텐션을 사용하는 하나의 개체 간 학습 모듈을 사용하여 작업 단계 및 기계와 같은 스케줄링 요소에서 다양한 표현을 학습합니다. 이러한 모듈은 다중 스케일 아키텍처에서 사용되며, 출력은 RL 의사 결정을 지원하기 위해 집계됩니다. 작은, 중간, 큰 규모의 작업 인스턴스에 대한 실험 결과, ReLA는 대부분의 테스트 환경에서 최신 솔루션보다 우수한 최단 완료 시간을 달성했습니다. 작은 규모의 인스턴스에서 ReLA는 최첨단(SOTA) 기준 모델의 최적성 격차를 13.0% 줄였으며, 대규모 인스턴스에서는 78.6% 줄여 평균 최적성 격차를 각각 7.3% 및 2.1%로 낮추었습니다. 이러한 결과는 ReLA의 학습된 표현과 집계가 RL 스케줄링에 강력한 의사 결정 지원을 제공하며, 실제 응용 분야에서 빠른 작업 완료 및 의사 결정을 가능하게 한다는 것을 확인합니다.

Job scheduling is widely used in real-world manufacturing systems to assign ordered job operations to machines under various constraints. Existing solutions remain limited by long running time or insufficient schedule quality, especially when problem scale increases. In this paper, we propose ReLA, a reinforcement-learning (RL) scheduler built on structured representation learning and aggregation. ReLA first learns diverse representations from scheduling entities, including job operations and machines, using two intra-entity learning modules with self-attention and convolution and one inter-entity learning module with cross-attention. These modules are applied in a multi-scale architecture, and their outputs are aggregated to support RL decision-making. Across experiments on small, medium, and large job instances, ReLA achieves the best makespan in most tested settings over the latest solutions. On non-large instances, ReLA reduces the optimality gap of the SOTA baseline by 13.0%, while on large-scale instances it reduces the gap by 78.6%, with the average optimality gaps lowered to 7.3% and 2.1%, respectively. These results confirm that ReLA's learned representations and aggregation provide strong decision support for RL scheduling, and enable fast job completion and decision-making for real-world applications.