SCHEMA: Hierarchical Reinforcement Learning for Scheduling Under Communication Contention

Scheduling a large graph of dependent tasks on a small pool of machines is a foundational problem in distributed and high-performance computing, with applications in cloud job scheduling, compiler operator placement, and computation-graph execution on accelerators, among others. It is hardest when tasks vastly outnumber machines, where communication, not computation, dominates makespan. Most schedulers treat the cost of moving data between machines as fixed and known in advance. Under contention this fails. When data transfers compete for shared resources, the cost of communication is no longer fixed but depends on the scheduler's own earlier placements. A value function trained under static costs therefore mispredicts the makespan actually achieved, and the error grows as contention increases. SCHEMA is a reinforcement-learning framework built around this effect. It casts scheduling as a hierarchical Markov decision process whose two levels, selecting a task, then its machine, are pointer networks that attend over the current frontier, keeping inference tractable as graphs reach tens of thousands of nodes. Rather than a fixed cost table, communication is modeled as an environment of capacity-limited link tiers whose occupancy grows as tasks are placed; SCHEMA predicts the tier each data transfer would use under current load and exposes this to the policy alongside structural graph features. Trained with PPO and evaluated on four workloads from 90 to 16,208 nodes against eight classical and learned baselines, SCHEMA achieves shorter schedules, and its margin over the strongest baseline improves with graph size, reaching 29% on the largest workload. Ablation studies attribute independent gains to the congestion-aware environment, the tier-estimation features, and the hierarchical policy, and removing any one lengthens the largest schedule by more than 75%.