Learned cluster schedulers usually split each decision in two. First they pick which ready task runs next, then they decide where it runs. Real schedulers also have to set continuous knobs, such as how fast to run a task, what power cap to give it, or what share of a machine to reserve, and they must respect hard limits like an energy budget or a job deadline. Current learned schedulers either leave out the continuous knob entirely or treat the limits as penalties that the policy learns to avoid on average. This note proposes making the second phase a hybrid action, meaning a discrete choice of machine and idle time slot plus a continuous speed setting. That hybrid action is projected exactly onto the set of settings that keep the whole remaining schedule feasible. The observation that makes this possible is that in scheduling, once the discrete choices are fixed, the feasible set for the continuous knob is a small union of intervals. It can be computed in closed form by scanning the timeline for idle gaps. General safety methods for continuous control need an online optimizer to find the nearest safe action. Here the equivalent step is nearly free.
Put simply, the policy chooses a task, a machine, a gap in that machine's timeline, and a speed. Before the policy acts, a cheap bookkeeping step tells it exactly which gaps and speeds cannot break the energy budget or the deadlines, now or later. The policy can only choose inside that set, so it spends its whole learning budget on reducing job completion time and none on learning to avoid violations.
Core Claim
In online scheduling with continuous resource knobs and hard budgets, a two-phase policy whose second phase outputs a hybrid action over an exactly computed feasible set should do two things. It should never violate the hard constraints, and it should reach lower job completion time than both penalty-based constrained hybrid reinforcement learning and a discrete scheduler that runs at a fixed speed with a hand-written placement rule. The expected advantage should grow as task arrivals and runtimes become less predictable, because that is when fixing the continuous knobs after the fact stops being possible.
Each input direction plays a different role. Two-phase decomposition supplies the backbone. The Lachesis design in Learning to Optimize DAG Scheduling in Heterogeneous Environment uses a graph neural network (a network that passes messages along the edges of the task dependency graph) to pick a ready stage, followed by an earliest-finish-time rule for placement. DOPPLER in DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs learns both an ordering policy and a placement policy. Both schedulers are purely discrete. Hybrid action optimization supplies the form of the second phase. Discrete action constraints supply the safety mechanism, which is a cheap, scheduling-specific counterpart of the projection shield in Realizable Continuous-Space Shields for Safe Reinforcement Learning.
How This Differs From the Closest Work
CHPO: Constrained Hybrid-action Policy Optimization for Reinforcement Learning is the nearest method. It trains discrete and continuous actors and switches between maximizing reward and minimizing cost depending on whether the average cost is above a threshold. It motivates this proposal, because it shows that Lagrangian penalty methods are unstable in hybrid spaces: on Parking, HPPO-Lag reaches a reward of 20.01 against CHPO's 37.63. It also constrains the proposal. CHPO enforces limits only in expectation over rollouts, and its tasks are navigation problems with no precedence structure. The proposal does not trade reward against cost at all for the hard constraints. It removes infeasible actions before sampling.
The shield in Realizable Continuous-Space Shields for Safe Reinforcement Learning supplies the template of an offline realizability check followed by online projection. It reports collisions going from 78% to effectively zero, while Lagrangian PPO still collided in about 5–9% of episodes. That shield, however, needs hand-written temporal-logic specifications and a runtime optimizer whose latency it acknowledges. In scheduling, the corresponding pieces are an interval scan and a lower-bound certificate, described below.
Two further papers shape the design. Effects of Different Representations for Solving Integrated Production and Transportation Scheduling Problem shows that "active decoding" beats semi-active decoding inside a genetic algorithm with fixed task durations. Active decoding means searching for idle gaps and inserting tasks early, instead of stacking each task after the last one. This proposal reuses gap search as the discrete part of the action and extends it to durations that depend on speed. Scheduling Drone and Mobile Charger via Hybrid-Action Deep Reinforcement Learning learns hybrid rendezvous-plus-duration actions through a latent decoder. It handles battery depletion through a look-ahead reward rather than a hard guarantee, and it does not decompose the decision into phases.
Research Program
The scheduler runs at each scheduling event. In phase one, a Lachesis-style graph neural network picks a ready stage $v$. In phase two, a hybrid head picks a machine $e$, an idle gap $g$ on that machine, and a normalized speed $u \in [0,1]$. The executed speed is
$$s = \ell_{e,g} + u\,(h_{e,g} - \ell_{e,g}),$$
where $[\ell_{e,g}, h_{e,g}]$ is the range of speeds that are still feasible when $v$ is placed in gap $g$ on machine $e$. The range is feasible when three conditions hold.
The first condition is that the task fits the gap. The task's duration at speed $s$ must fit between its earliest start time (set by its predecessors and data transfer) and the end of the gap. This gives a lower bound on speed.
The second condition is that the energy budget remains realizable. The energy spent at speed $s$, plus the minimum possible energy of every unscheduled task, must not exceed the remaining budget $B$. This gives an upper bound on speed.
The third condition is that deadlines remain realizable. The critical path of the remaining work, with every remaining task run at maximum speed, must still meet each job's deadline.
Any pair $(e, g)$ with an empty range is masked out of the discrete distribution. If every pair is empty, the realizability certificate from the previous step guarantees that this cannot happen when runtimes are deterministic. That guarantee is the analogue of the shield's offline check. When runtimes are stochastic, the scheduler plans with an upper quantile of runtime, and the guarantee becomes probabilistic at that quantile. Characterizing that probability empirically is part of the work.
Training uses PPO. The continuous head is a Beta distribution over $u$, so the change of variables into the feasible range is exact. The reward is negative job completion time. For soft objectives, such as energy use below the hard budget, the CHPO switching rule is added on top.
The analysis side will measure two things: how often the certificate is conservative, meaning it masks actions that would in fact have stayed feasible, and how much completion time that conservatism costs.
Baselines
The naive reference is a critical-path priority list with semi-active placement, with every task run at the constant speed that exactly exhausts the energy budget. It shows how much any learning adds.
The strongest discrete learned competitor is a Lachesis- and Decima-style scheduler: a graph network for stage selection plus earliest-finish-time placement at that same constant speed. Learning Scheduling Algorithms for Data Processing Clusters reports that Decima reduces average job completion time by 21% relative to the best hand-tuned heuristics on a 25-node Spark cluster running TPC-H. For Lachesis, the file reports only that it beats Decima on makespan and schedule length ratio, and I found no reported Lachesis number on Lacuna. Beating this baseline means lower average job completion time under the same energy budget.
The strongest constrained hybrid competitor is CHPO run on the same two-phase backbone, with a hybrid second phase that has no masking and treats the budget as a cost threshold. For both CHPO and a PPO-Lagrangian variant, the proposal counts as beating them if it has zero budget and deadline violations, where they have nonzero violation rates, and equal or better completion time.
The flat alternative is DGRL from Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete and Hybrid Action Spaces. DGRL embeds the whole joint action and searches nearby actions under a max-coordinate distance. It reports up to 129% gains in hybrid spaces and runs on a job-shop environment with $10^{10}$ actions. It is the direct test of whether decomposition is needed at all.
Three ablations isolate the key ingredient. The first removes the feasibility mask and replaces it with a penalty. The second removes gap choice, so tasks are only appended after the last one. The third removes the learned speed and uses constant speed with the mask kept.
For fairness, all learned methods share the same graph encoder, simulator, number of environment steps, and hyperparameter search budget of 20 configurations each, and results are averaged over five seeds.
Why not just…?
Why not just keep the earliest-finish-time rule for placement, as Lachesis does? The Lachesis authors found that rule sufficient, but only because their durations were fixed. Once speed is a decision, finishing a task earliest means running it at high power, which spends energy that later tasks need. The constant-speed ablation and the Lachesis-style baseline test this directly. If they match the proposal, then the continuous knob does not matter in this regime, and that would be reported as the finding.
Why not just learn the order and placement, then set all speeds afterward with a linear program? This is the approach of Exploiting Temporal Flexibility to Obtain High Quality Schedules, which sequences first and then stretches durations with an LP. It is a genuine threat. With a static graph and known runtimes, it should match or beat the proposal, because the LP is exact. It needs the whole future, though, and does not work online when jobs arrive and runtimes vary. The experiments therefore sweep arrival rate and runtime variance and look for a crossover. If no crossover appears, the claim fails.
Why not just discretize speed into levels and use a discrete policy? Hardware speed settings are often discrete anyway. Discretization multiplies the number of actions by machines, gaps, and speed levels. Evidence from DGRL and from HaDMC's comparison against DQN suggests that discrete policies degrade as the action count grows. The proposal will include a variant that masks a discrete grid of 8 and 32 speed levels. If the 8-level variant matches the continuous one, the continuous head is not justified, and the contribution reduces to the feasibility mask.
Proposed Experiments
The primary testbed is the TPC-H DAG workload in the Decima simulator. It will be extended with heterogeneous executors, a power-speed curve for each executor, a cluster-wide energy budget, and per-job deadlines. The energy model is synthetic, and this will be stated as such. Metrics are average job completion time, violation rate, and decision latency, measured against Decima's figure of under 15 ms per scheduling event. The secondary testbed is the EX and NEX integrated production and transport benchmarks, with automated guided vehicle speed made continuous and a per-vehicle energy budget added. It tests whether active decoding with continuous durations carries over to factories.
Four results would settle the proposal. First, violation rates must be exactly zero for the proposal under deterministic runtimes, and bounded by the chosen runtime quantile under stochastic runtimes, while CHPO and PPO-Lagrangian show nonzero rates. Second, completion time must beat the Lachesis-style baseline at matched energy. Third, the sequence-then-LP baseline must win at zero runtime variance and lose above some level of runtime variance. Fourth, the no-mask ablation must train more slowly and less stably, which would show that exact projection, and not the extra continuous head, is what drives the gains.
References
- Learning to Optimize DAG Scheduling in Heterogeneous Environment
- DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs
- Realizable Continuous-Space Shields for Safe Reinforcement Learning
- CHPO: Constrained Hybrid-action Policy Optimization for Reinforcement Learning
- Effects of Different Representations for Solving Integrated Production and Transportation Scheduling Problem
- Scheduling Drone and Mobile Charger via Hybrid-Action Deep Reinforcement Learning
- Learning scheduling algorithms for data processing clusters
- Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete and Hybrid Action Spaces
- Exploiting Temporal Flexibility to Obtain High Quality Schedules