ReLA: Representation Learning and Aggregation for Scalable Job Scheduling with Reinforcement Learning
Abstract
Large-scale job scheduling is a classic problem in computing systems and industrial operations, where complex workloads, workflows, or ordered job operations must be assigned to computing nodes or machines under resource, precedence, and availability constraints. Existing solvers can provide useful reference solutions, but their search cost is often too high for time-sensitive scheduling. Recent reinforcement-learning (RL) schedulers offer faster inference, yet many rely on limited state representations, which can weaken action scoring as scheduling instances scale. In this paper, we propose ReLA, an RL scheduler built on structured representation learning and aggregation. ReLA learns intra-entity representations using self-attention and convolution, captures inter-entity operation–machine interactions using cross-attention, and aggregates multi-scale representations for parallel actor-based scoring of feasible actions. Experiments on synthetic and public scheduling benchmarks show that ReLA achieves the best makespan in most tested settings. On small and medium instances, ReLA achieves a 7.3% average optimality gap and reduces the state-of-the-art (SOTA) baseline gap by 13.0%. On large instances with at least a hundred jobs, ReLA reduces the SOTA gap by 78.6%, with an average gap of 2.1%. These results demonstrate ReLA’s effectiveness for scalable and runtime-efficient scheduling over large action spaces.