pith. sign in

arxiv: 2605.18454 · v1 · pith:ZXJBPDHUnew · submitted 2026-05-18 · 💻 cs.LG · cs.AI· cs.SC

Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework

Chengpeng Hu , Yingqian Zhang , Hendrik Baier This is my paper

Pith reviewed 2026-05-20 12:30 UTC · model grok-4.3

classification 💻 cs.LG cs.AIcs.SC
keywords programmatic reinforcement learninginterpretable policiesjob shop schedulingdomain-specific languageBayesian optimizationlocal searchcombinatorial optimization
0
0 comments X

The pith

ProRL learns human-readable programmatic policies for scheduling that match deep RL performance while using far fewer resources.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces ProRL as a way to solve job shop scheduling without relying on opaque neural networks. It defines a domain-specific language called DSL-S that turns scheduling strategies into structured, editable programs. Local search identifies promising incomplete program skeletons, after which Bayesian optimization tunes the remaining parameters so the programs select and combine existing heuristic rules. A sympathetic reader would care because the resulting policies remain interpretable to humans, can incorporate industrial practice, and still deliver competitive results even when trained on only 100 episodes.

Core claim

The central claim is that high-performing scheduling policies can be discovered and expressed as structured programs inside DSL-S, where local search finds the program structure and Bayesian optimization learns the numerical parameters, thereby producing policies that naturally embed existing heuristics and achieve strong benchmark results against both classical heuristics and deep reinforcement learning baselines.

What carries the argument

DSL-S, the domain-specific language that represents scheduling strategies as structured programs, which supports local search over incomplete programs followed by Bayesian optimization to learn parameters.

If this is right

  • Policies become human-readable and directly editable by practitioners.
  • Established industrial scheduling heuristics are naturally included in the learned programs.
  • Competitive performance holds even when training is limited to 100 episodes.
  • The approach supplies an alternative to black-box neural policies for combinatorial scheduling tasks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-search-plus-optimization pattern could transfer to other combinatorial optimization problems once suitable domain-specific languages are written.
  • Because programs are editable, domain experts could manually adjust learned policies for new constraints without retraining from scratch.
  • Lower data requirements may allow faster adaptation when a factory changes its scheduling rules or machine set.

Load-bearing premise

The domain-specific language DSL-S must be expressive enough that local search combined with Bayesian optimization can reliably discover high-performing scheduling strategies.

What would settle it

Running the same benchmark instances and observing that no combination of local search and Bayesian optimization inside DSL-S produces policies competitive with the reported baselines.

Figures

Figures reproduced from arXiv: 2605.18454 by Chengpeng Hu, Hendrik Baier, Yingqian Zhang.

Figure 1
Figure 1. Figure 1: Domain-specific language for scheduling (DSL-S). H denotes the set of PDRs (heuristics). A condition B represents an interpretable linear model characterized by the parameter vector w and the concept set C = {c0, c1, · · · , ck}. 4 Programmatic RL for Scheduling (ProRL) We first propose DSL-S, a domain-specific language to express programmatic policies. We then introduce a bilevel optimization framework th… view at source ↗
Figure 2
Figure 2. Figure 2: A programmatic policy discovered by ProRL. Depending on the state, the policy will choose an action from three heuristics: MWR, LOR and SPT. The concepts {LD, AM, AO, JD, ST} represent machine load balance, available machine ratio, avail￾able operation ratio, job remaining time balance, and shortest operation remaining time balance, respectively. Control flow is handled by if-else statements. These stateme… view at source ↗
Figure 3
Figure 3. Figure 3: ProRL locally searches for architectures and then optimizes the program pa￾rameters via BO. The best program is mutated for generate the new neighborhood. ProRL with bilevel optimization The programmatic space is usually non￾differentiable and highly discontinuous. To practically implement ProRL, we propose an iterative bilevel optimization method (as in Eq. (1)), which (a) searches [PITH_FULL_IMAGE:figur… view at source ↗
Figure 4
Figure 4. Figure 4: Visualization of the policy shown in [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
read the original abstract

Deep reinforcement learning (DRL) has recently emerged as a promising approach to solve combinatorial optimization problems such as job shop scheduling. However, the policies learned by DRL are typically represented by deep neural networks (DNNs), whose opaque neural architectures and non-interpretable policy decisions can lead to critical trust and usability concerns for human decision makers. In addition, the computational requirements of DNNs can further hinder practical deployment in resource constrained environments. In this work, we propose ProRL, a novel interpretable programmatic reinforcement learning framework that achieves high-performance scheduling with human-readable and editable programmatic policies (i.e., programs). We first introduce a domain-specific language for scheduling (DSL-S) to represent scheduling strategies as structured programs. ProRL then explores the program space defined by DSL-S using local search to identify incomplete programs, which are subsequently completed by learning their parameters via Bayesian optimization. ProRL learns which scheduling heuristic rules to select, and hence, it naturally incorporates existing heuristics already used in industrial scenarios. Experiments on widely used benchmark instances demonstrate the strong performance of ProRL against existing heuristics and DRL baselines. Furthermore, ProRL performs well under strongly constrained computational resources, such as training with only 100 episodes. Our code is available at https://github.com/HcPlu/ProRL.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes ProRL, a novel interpretable programmatic reinforcement learning framework for solving job shop scheduling problems. It introduces a domain-specific language DSL-S to represent scheduling strategies as structured programs. ProRL uses local search to identify incomplete programs and Bayesian optimization to learn their parameters. The authors report that this approach achieves strong performance on widely used benchmark instances compared to existing heuristics and deep reinforcement learning baselines, and performs well even with limited computational resources such as training on only 100 episodes. The code is made available.

Significance. If the results hold, the framework provides an important step toward interpretable and deployable RL policies for combinatorial optimization tasks. By producing human-readable and editable programs that can incorporate industrial heuristics, it addresses trust and usability issues common with black-box DRL methods. The low-data regime performance is noteworthy for practical applications. The open-sourced code enhances the potential impact by enabling further research and verification.

major comments (3)
  1. Abstract and experimental section: The central claims of 'strong performance' against heuristics and DRL baselines, plus effectiveness with only 100 episodes, are asserted without any quantitative metrics, tables, statistical details, or protocol description visible in the provided text. The manuscript must supply concrete results (e.g., makespan values, optimality gaps, means and standard deviations over seeds) with direct comparisons to support these load-bearing assertions.
  2. DSL-S definition section: The claim that local search plus Bayesian optimization can reliably discover high-performing strategies rests on the unverified assumption that DSL-S is sufficiently expressive beyond the incorporated industrial heuristics. No analysis, completeness argument, or examples are provided showing that discovered programs exceed the best single heuristic already present in the DSL.
  3. Method and experimental evaluation: The two-stage search procedure (local search for incomplete programs followed by parameter tuning) lacks ablations that isolate its contribution. Without controls comparing ProRL to (a) simply selecting the best heuristic from the DSL or (b) alternative search strategies, it remains unclear whether reported gains derive from the programmatic RL framework itself rather than heuristic selection.
minor comments (2)
  1. Notation and terminology: Define 'incomplete programs' more precisely and clarify how parameters are represented and optimized within the Bayesian optimization stage to avoid ambiguity for readers.
  2. References: Add or verify citations to prior work on programmatic reinforcement learning and interpretable methods for scheduling problems to better situate the contribution.

Simulated Author's Rebuttal

3 responses · 0 unresolved

Thank you for the detailed and constructive review of our manuscript. We appreciate the feedback highlighting areas where the presentation and analysis can be strengthened. We address each major comment below and outline the revisions we will make to the manuscript.

read point-by-point responses

  1. Referee: Abstract and experimental section: The central claims of 'strong performance' against heuristics and DRL baselines, plus effectiveness with only 100 episodes, are asserted without any quantitative metrics, tables, statistical details, or protocol description visible in the provided text. The manuscript must supply concrete results (e.g., makespan values, optimality gaps, means and standard deviations over seeds) with direct comparisons to support these load-bearing assertions.

    Authors: We thank the referee for this observation. The experimental section of the full manuscript includes tables with makespan values, optimality gaps, and direct comparisons to heuristics and DRL baselines on standard benchmark instances. To improve clarity and address the concern about visibility of supporting evidence, we will revise the abstract to reference key quantitative results (e.g., average performance gains) and expand the experimental section to explicitly report means and standard deviations over multiple random seeds along with a detailed description of the evaluation protocol. revision: yes

  2. Referee: DSL-S definition section: The claim that local search plus Bayesian optimization can reliably discover high-performing strategies rests on the unverified assumption that DSL-S is sufficiently expressive beyond the incorporated industrial heuristics. No analysis, completeness argument, or examples are provided showing that discovered programs exceed the best single heuristic already present in the DSL.

    Authors: We agree that an explicit demonstration of expressiveness beyond single heuristics strengthens the contribution. In the revised manuscript, we will add concrete examples of programs discovered by the local search plus Bayesian optimization procedure that outperform the best individual heuristic from DSL-S (e.g., by composing multiple rules with learned parameters). We will also include a brief discussion in the DSL-S section on how the search space enables combinations and parameterizations that go beyond selecting any single pre-existing heuristic. revision: yes

  3. Referee: Method and experimental evaluation: The two-stage search procedure (local search for incomplete programs followed by parameter tuning) lacks ablations that isolate its contribution. Without controls comparing ProRL to (a) simply selecting the best heuristic from the DSL or (b) alternative search strategies, it remains unclear whether reported gains derive from the programmatic RL framework itself rather than heuristic selection.

    Authors: This is a fair critique regarding the need for isolating the framework's contributions. We will incorporate additional ablation experiments in the revised manuscript. These will include (a) a direct baseline that selects and evaluates the single best heuristic from DSL-S on the training set, and (b) comparisons against alternative search strategies such as random sampling within the DSL or a simple genetic algorithm. The results will clarify the incremental benefit of the two-stage local search and Bayesian optimization procedure. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper defines DSL-S explicitly as a domain-specific language for scheduling strategies, then applies standard local search to generate incomplete programs followed by Bayesian optimization to fit parameters, with final performance measured empirically on external benchmark instances against heuristics and DRL baselines. No quoted step reduces a central claim (such as performance or expressiveness) to its own inputs by construction, nor does any load-bearing premise collapse to a self-citation or fitted input renamed as prediction. The method incorporates existing heuristics by design but evaluates gains via independent experimental comparison, keeping the chain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claim depends on the expressiveness of the newly introduced DSL-S and the assumption that local search plus Bayesian optimization will locate strong programs within the space it defines.

free parameters (1)
  • program parameters
    Numerical values inside incomplete programs are fitted via Bayesian optimization.
axioms (1)
  • domain assumption DSL-S can represent effective scheduling strategies
    The framework presupposes that the language is rich enough for high-quality policies to exist and be discoverable.
invented entities (1)
  • DSL-S no independent evidence
    purpose: Domain-specific language to encode scheduling strategies as structured, human-readable programs
    New language introduced to enable programmatic rather than neural policies.

pith-pipeline@v0.9.0 · 5763 in / 1319 out tokens · 47300 ms · 2026-05-20T12:30:25.115376+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Management Science34(3), 391–401 (1988)

    Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job shop scheduling. Management Science34(3), 391–401 (1988)

    work page 1988

  2. [2]

    ORSA Journal on computing3(2), 149–156 (1991)

    Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA Journal on computing3(2), 149–156 (1991)

    work page 1991

  3. [3]

    Advances in Neural Information Processing Systems31(2018)

    Bastani, O., Pu, Y., Solar-Lezama, A.: Verifiable reinforcement learning via policy extraction. Advances in Neural Information Processing Systems31(2018)

    work page 2018

  4. [4]

    In: The Twelfth International Conference on LearningRepresentations(2024), https://openreview.net/forum?id=NGVljI6HkR

    Carvalho, T.H., Tjhia, K., Lelis, L.: Reclaiming the source of programmatic policies: Programmatic versus latent spaces. In: The Twelfth International Conference on LearningRepresentations(2024), https://openreview.net/forum?id=NGVljI6HkR

    work page 2024

  5. [5]

    Corsini, A., Porrello, A., Calderara, S., Dell’Amico, M.: Self-labeling the job shop scheduling problem.Advancesin Neural Information Processing Systems37, 105528– 105551 (2024)

    work page 2024

  6. [6]

    In: the 22nd ACM International Conference on Hybrid Systems: Computation and Control

    Dutta, S., Chen, X., Sankaranarayanan, S.: Reachability analysis for neural feedback systems using regressive polynomial rule inference. In: the 22nd ACM International Conference on Hybrid Systems: Computation and Control. pp. 157–168 (2019)

    work page 2019

  7. [7]

    The International Journal of Advanced Manufacturing Technology31, 342–349 (2006)

    El-Bouri, A., Shah, P.: A neural network for dispatching rule selection in a job shop. The International Journal of Advanced Manufacturing Technology31, 342–349 (2006)

    work page 2006

  8. [8]

    In: Industrial Scheduling, pp

    Fisher, H., Thompson, G.: Probabilistic learning combinations of local job-shop scheduling rules. In: Industrial Scheduling, pp. 225–251 (1963)

    work page 1963

  9. [9]

    In: the AAAI Conference on Artificial Intelligence

    Gu, Y., Zhang, K., Liu, Q., Gao, W., Li, L., Zhou, J.:π-light: Programmatic interpretable reinforcement learning for resource-limited traffic signal control. In: the AAAI Conference on Artificial Intelligence. vol. 38, pp. 21107–21115 (2024)

    work page 2024

  10. [10]

    Computers & Industrial Engineering180, 109255 (2023)

    Gui, Y., Tang, D., Zhu, H., Zhang, Y., Zhang, Z.: Dynamic scheduling for flexible job shop using a deep reinforcement learning approach. Computers & Industrial Engineering180, 109255 (2023)

    work page 2023

  11. [11]

    IEEE Access8, 186474–186495 (2020)

    Han, B.A., Yang, J.J.: Research on adaptive job shop scheduling problems based on dueling double DQN. IEEE Access8, 186474–186495 (2020)

    work page 2020

  12. [12]

    Graduate School of Industrial Administration, Carnegie-Mellon University (1984)

    Lawrence, S.: Resouce constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement). Graduate School of Industrial Administration, Carnegie-Mellon University (1984)

    work page 1984

  13. [13]

    In: International Conference on Machine Learning

    Liu, G.T., Hu, E.P., Cheng, P.J., Lee, H.Y., Sun, S.H.: Hierarchical program- matic reinforcement learning via learning to compose programs. In: International Conference on Machine Learning. pp. 21672–21697. PMLR (2023)

    work page 2023

  14. [14]

    In: the 41st International Confer- ence on Machine Learning

    Luo, L., Zhang, G., Xu, H., Yang, Y., Fang, C., Li, Q.: End-to-end neuro-symbolic reinforcement learning with textual explanations. In: the 41st International Confer- ence on Machine Learning. ICML’24, JMLR.org (2024)

    work page 2024

  15. [15]

    Journal of machine learning research9(Nov), 2579–2605 (2008)

    Maaten, L.v.d., Hinton, G.: Visualizing data using t-SNE. Journal of machine learning research9(Nov), 2579–2605 (2008)

    work page 2008

  16. [16]

    Transactions on Machine Learning Research (2024),https://openreview.net/forum?id=agT8ojoH0X

    Pirnay, J., Grimm, D.G.: Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. Transactions on Machine Learning Research (2024),https://openreview.net/forum?id=agT8ojoH0X

    work page 2024

  17. [17]

    Reijnen, I

    Reijnen, R., van Straaten, K., Bukhsh, Z., Zhang, Y.: Job shop scheduling bench- mark: Environments and instances for learning and non-learning methods. arXiv preprint arXiv:2308.12794 (2023)

    work page arXiv 2023

  18. [18]

    Proximal Policy Optimization Algorithms

    Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017) Programmatic Reinforcement Learning for Scheduling 33

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  19. [19]

    Management science38(10), 1495–1509 (1992)

    Storer, R.H., Wu, S.D., Vaccari, R.: New search spaces for sequencing problems with application to job shop scheduling. Management science38(10), 1495–1509 (1992)

    work page 1992

  20. [20]

    MIT press (2018)

    Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT press (2018)

    work page 2018

  21. [21]

    European Journal of Operational Research64(2), 278–285 (1993)

    Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research64(2), 278–285 (1993)

    work page 1993

  22. [22]

    Advances in Neural Information Processing Systems36, 74952–74965 (2023)

    Turpin, M., Michael, J., Perez, E., Bowman, S.: Language models don’t always say what they think: Unfaithful explanations in chain-of-thought prompting. Advances in Neural Information Processing Systems36, 74952–74965 (2023)

    work page 2023

  23. [23]

    Journal of Computational Science61, 101649 (2022)

    Ðurasević, M., Jakobović, D.: Selection of dispatching rules evolved by genetic programming in dynamic unrelated machines scheduling based on problem charac- teristics. Journal of Computational Science61, 101649 (2022)

    work page 2022

  24. [24]

    In: the 33rd International Conference on Neural Information Processing Systems

    Verma, A., Le, H.M., Yue, Y., Chaudhuri, S.: Imitation-projected programmatic reinforcement learning. In: the 33rd International Conference on Neural Information Processing Systems. pp. 15752–15763 (2019)

    work page 2019

  25. [25]

    In: International Conference on Machine Learning

    Verma, A., Murali, V., Singh, R., Kohli, P., Chaudhuri, S.: Programmatically interpretable reinforcement learning. In: International Conference on Machine Learning. pp. 5045–5054. PMLR (2018)

    work page 2018

  26. [26]

    In: Inter- national Conference on Tools and Algorithms for the Construction and Analysis of Systems

    Wang, Y., Zhu, H.: Verification-guided programmatic controller synthesis. In: Inter- national Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 229–250. Springer (2023)

    work page 2023

  27. [27]

    The Journal of Machine Learning Research23(1), 12275–12280 (2022)

    Weng, J., Chen, H., Yan, D., You, K., Duburcq, A., Zhang, M., Su, Y., Su, H., Zhu, J.: Tianshou: A highly modularized deep reinforcement learning library. The Journal of Machine Learning Research23(1), 12275–12280 (2022)

    work page 2022

  28. [28]

    Engineering Applications of Artificial Intelligence131, 107790 (2024)

    Wu, X., Yan, X., Guan, D., Wei, M.: A deep reinforcement learning model for dynamic job-shop scheduling problem with uncertain processing time. Engineering Applications of Artificial Intelligence131, 107790 (2024)

    work page 2024

  29. [29]

    In: Parallel Problem Solving from Nature (1992)

    Yamada, T., Nakano, R.: A genetic algorithm applicable to large-scale job-shop problems. In: Parallel Problem Solving from Nature (1992)

    work page 1992

  30. [30]

    In: The Twelfth International Conference on Learning Representations (2024)

    Zhang, C., Cao, Z., Song, W., Wu, Y., Zhang, J.: Deep reinforcement learning guided improvement heuristic for job shop scheduling. In: The Twelfth International Conference on Learning Representations (2024)

    work page 2024

  31. [31]

    Advances in Neural Information Processing Systems33, 1621–1632 (2020)

    Zhang, C., Song, W., Cao, Z., Zhang, J., Tan, P.S., Chi, X.: Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Systems33, 1621–1632 (2020)

    work page 2020