Offline RL learns to schedule jobs from imperfect data—and random solutions outperform expert heuristics

Researchers have developed a new offline reinforcement learning (RL) method that learns to schedule jobs effectively without needing constant interaction with a training environment—a departure from the sample-hungry online RL systems typically used for this task.

The new algorithm, called Conservative Discrete Quantile Actor-Critic (CDQAC), trains on static datasets of suboptimal scheduling trajectories and produces policies that match or surpass the heuristics that generated the training data. Tested on Job Shop Scheduling (JSP) and Flexible JSP (FJSP) benchmarks, CDQAC required as little as 1–5% of the original dataset to achieve high-quality policies, pointing to surprising efficiency gains.

How it works#

CDQAC combines a quantile-based critic with delayed policy updates, allowing it to estimate the return distribution—rather than just a single expected value—for each machine-operation pair. This distributional approach, paired with conservative policy adjustments, helps the algorithm avoid overestimating the value of untested actions, a common pitfall in offline RL.

Surprising finding: broad beats deep#

The researchers uncovered a counterintuitive result. Datasets generated by a simple random heuristic, which covers a wider variety of scheduling behaviors, yielded better-trained policies than datasets from stronger heuristics like Genetic Algorithms. This suggests that for JSP and FJSP, what matters most is state-action coverage—the diversity of scenarios explored—rather than the optimality of any single trajectory.

The authors attribute this partly to the problem structure: JSP and FJSP assign dense rewards aligned with makespan (total job duration) and use equal-length trajectories across heuristics, making it feasible to learn from a broad spectrum of behaviors.

Why it matters#

Offline RL sidesteps the computational cost of online training, making scheduling solutions more practical for real-world deployment. The finding that coverage trumps quality also suggests a rethinking of data collection strategies: simpler, more diverse datasets may be preferable to expertly optimized ones in contexts where exploration is expensive.