RL in Scheduling and Operations Research

One-liner: this page explains how reinforcement learning makes its way into operations research (OR) — rewriting combinatorial problems like inventory, scheduling, bin packing, and routing as MDPs, using RL to train "learned solvers," and whether RL competes with or complements classical OR methods (MILP, CP, heuristics). It's the case-study companion to the "RL vs OR" section of the RL vs adjacent paradigms page.

1. How OR problems become MDPs

1.1 The core difficulty of combinatorial optimization

Classical OR problems — traveling salesman (TSP), vehicle routing (VRP), job-shop scheduling (JSP), bin packing, inventory management, network routing — are all combinatorial optimization at heart: finding the optimum among exponentially many discrete options. Their common structure:

minimize  objective (cost/time/distance)
subject to constraints (resources, deadlines, capacity, precedence)

classical solvers: MILP (mixed-integer programming) / CP (constraint programming) → exact solutions via branch-and-bound
          heuristics (NEH, ALNS, genetic algorithms) → approximate solutions

Exact methods explode exponentially as scale grows (NP-hard), and heuristics require domain experts to hand-write neighborhoods and rules. RL enters by turning "constructing a solution" into "sequential decision-making":

1.2 Serialization: solution construction as an MDP

Almost every OR problem can be rewritten as a sequential decision process:

state s_t  : the partial solution built so far (scheduled jobs / visited route / current inventory level)
action a_t : the next decision (next node to insert / next job to schedule / how much to order)
reward r_t : the incremental cost of that step (negative), or the final objective value on completion
transition : update the partial solution with the decision taken
termination: construction completes, terminal reward is received

policy π: P(next choice | current partial solution) — parameterized by a neural network

An example (TSP):

s_t = set of visited cities + current position
a_t = the next city to visit
r_t = distance to that city (negative reward)
policy learning objective: minimize the expected total tour length

This "learning to construct" paradigm underlies directions like L2S (Learning to Schedule) and Learning to Optimize. Representative methods include Pointer Networks (Vinyals et al., 2015), the Attention Model (Kool et al., 2018), and GPN for scheduling (Zhang et al., 2020).

INFO

The beauty of serialization: it splits a "one-shot global optimization" into "step-by-step local decisions." Local optima don't guarantee a global optimum, but with good policy learning (looking ahead, using global features), RL-learned construction heuristics often approach the optimum — and require no hand-written domain rules; the policy is learned from data. This is exactly isomorphic to the "sequence of decisions" framework on the Markov decision process page.

2. Case 1: inventory management and the dynamic newsvendor

2.1 From static newsvendor to dynamic inventory

The classic newsvendor problem: a newsvendor buys q newspapers per day, demand D is random, unsold copies lose money, sold copies earn it. The static version finds one optimal q. Its RL version (the dynamic one):

state s_t  : current inventory level I_t
action a_t : order quantity q_t this period
randomness : demand D_t ~ known distribution
reward r_t : sales revenue − ordering cost − holding cost − stockout penalty
transition : I_{t+1} = max(I_t + q_t − D_t, 0)

Dimension	Static newsvendor	Dynamic inventory RL
Decision	How much to order, once	How much to order each period
State	None	Inventory, demand forecast, in-transit quantity
Objective	Single-period expected profit	Long-term expected profit (including holding/stockout costs)
Solution	Closed form (quantile formula)	Value/policy learning

2.2 Why the industry prefers "closed form + rules" over RL

To be honest: for single-item inventory with a known demand distribution, the newsvendor formula / DP solves it exactly, and RL has no edge. RL is only worth it under three conditions:

1. Many items, many warehouses, shared resources: the state explodes and no closed form exists;
2. Non-stationary demand (promotions, seasons, spikes) with continuously drifting distributions;
3. A simulator is available: supply-chain simulation (AnyLogic, in-house simulators) can generate training data.

This judgment applies to all of OR: RL doesn't come to replace classical methods; it only addresses the scale and complexity where classical methods break down. That's the core conclusion of "RL vs OR" in RL vs adjacent paradigms.

3. Case 2: job-shop scheduling and bin packing (learning to construct)

3.1 Job-shop scheduling (JSP/flow shop)

Job-shop scheduling: n jobs are processed on m machines in technological order, each machine handles one job at a time, and the goal is to minimize the total completion time (makespan). It's a notoriously hard NP-hard nut, and industry relies on heuristics (priority rules, genetic algorithms) to crack it.

The RL route (GPN, Graph Pointer Network, Zhang et al., 2020) writes scheduling as sequential decision-making on a graph:

state : a heterogeneous graph (job nodes + machine nodes + operation edges) expressing "which operations remain to be scheduled"
action: choose "the next operation to start"
reward: −makespan upon completing the solution (or step-by-step machine-idle penalties)
policy: a GNN computes attention scores over the graph → select an operation

Results: GPN's makespan on benchmark instances matches or even beats traditional heuristics, and it generalizes to unseen sizes to some degree (e.g., trained on 15×15, tested on 20×15) — but performance degrades as scale grows, exposing the key weakness of learned solvers (see Section 7).

3.2 Bin packing and more

• Online bin packing: items arrive in a stream and must be placed in a bin immediately; RL can learn "which bin to use / whether to open a new one."
• 2D/3D bin packing (container loading, warehouse stacking): the state is a representation of occupied volume, and the action is "which bin, and how to rotate it."
• Vehicle routing (VRP): Nazari et al. (2018) extended the Attention Model to VRP, learning a construction policy for which customer to serve next.

3.3 Wins and losses against classical heuristics

Method	Solution quality	Speed	Generalization	Expert knowledge needed
MILP/CP	Exact optimum	Exponential	Perfect (exact)	Modeling skill
Hand-written heuristics (ALNS, etc.)	Good	Fast	Depends on instance structure	High (domain expert)
Learning to construct (RL)	Good to near-optimal	Fast (one forward pass)	Strong in-distribution, degrades OOD	Low (only a simulator)

The key insight: the real selling point of learned solvers isn't solution quality — it's "one forward pass, one usable solution." Where real-time response is required (a warehouse needs a plan for an order wave in milliseconds), MILP doesn't have time to run at all, and that's where RL shines.

3.4 Three paradigms of learned solvers

"Learning to construct" isn't the only game in town — there are three paradigms in total; don't conflate them:

Paradigm	What it does	Representative	Pros	Cons
Learning to construct	Build a full solution step by step from empty	Attention Model, GPN	One forward pass, fast	Quality depends on the training distribution
Learning to improve	Iteratively apply local modifications to a given solution	RL versions of LNS/ALNS	Can approach optimality	Needs a good initial solution; iteration cost
Neural-guided search	Guide branching decisions inside MILP/CP	Gasse 2019	Exactness preserved	Doesn't replace the solver; integration is complex

Selection advice: for "real-time solutions," choose construction; for "solution quality," choose improvement or neural-guided search; if you want both, do it two-stage (construct an initial solution, then let improvement/a solver finish the job).

4. Case 3: network routing and resource allocation

4.1 Network routing: teaching packets which way to go

The traffic-engineering problem: given a topology and a traffic matrix, decide how traffic is split across links to minimize the maximum link utilization. As RL:

state : link loads / queue lengths across the network (partially observable, needs aggregation)
action: the split ratios of each ingress flow across egress paths
reward: −(max utilization) or −(delay/loss)
transition: the traffic matrix changes dynamically (non-stationary!)

Representative work (e.g., the 2018 public demo of Machine Learning for Network Routing, a DeepMind–Google collaboration) showed that a trained RL routing policy can adapt to bursty traffic and reroute faster than traditional algorithms. But note the huge caveat: traffic is constantly shifting, and network states show up out-of-distribution all the time — which is why network RL has never replaced protocols like OSPF/MPLS at scale and is used mostly for optimization inside specific data centers.

4.2 Resource allocation: bandwidth, compute, spectrum

Cloud-platform allocation, wireless-spectrum allocation, and compute scheduling are also natural RL fits: the state is resource occupancy and task queues, the action is "who gets the resource," and the reward is completion rate or latency. In multi-tenant scenarios this stacks a multi-agent RL game on top — every tenant bids and preempts strategically.

5. The learned-solver recipe: RL trains construction heuristics

Putting it all together, here's a reusable "train a solver with RL" methodology:

1. Define the problem's "construction process" (a sequential decision unfolding)
2. Choose a representation: sequence (Transformer) or graph (GNN) to encode the current partial solution
3. Define the reward: the objective value of the completed solution (or step-by-step increments)
4. Train: REINFORCE with baseline (or PPO) to maximize expected reward
5. Inference: greedy or beam search over multiple sampled solutions, take the best

Training objectives and implementation details (baseline design, reward shaping) live on the policy gradient methods page. The REINFORCE baseline is often "the mean reward of the current batch" (like the Attention Model's rollout baseline), whose purpose is variance reduction.

L(θ) = E_{π_θ}[ (G − b) · log π_θ(a|s) ]
       ↑              ↑            ↑
  expectation   reward minus baseline   log-prob of the chosen action
(raise the probability of "better-than-average" decisions — the core of policy gradient; see the policy-gradient page)

5.1 Training and inference details: baseline, sampling, and heatmaps

A learned solver's performance hinges heavily on three implementation details:

Detail	Common practice	Effect
Baseline	Greedy rollout baseline / batch-mean baseline	Variance reduction (the key to REINFORCE)
Inference sampling	Greedy / beam search / sample-and-select	More samples → better solutions; cost rises linearly
Output form	Probability distribution (softmax) or heatmap	Heatmaps pair nicely with search post-processing

Engineering "free lunch": once you've trained a stochastic policy, running beam search at inference (width 100–1000) usually lifts TSP solution quality to near-optimal right away — you keep multiple candidate paths alive during construction and pick the best at the end. It's "trading inference compute for solution quality," the same idea as AlphaGo's search (see AlphaGo and Monte Carlo tree search). When a paper reports "RL beats the optimum," it's often this "policy + sampling" combination at work, not the policy alone — always check the inference protocol when reading results.

5.2 The relationship with MILP: hybrid, not replacement

The industry's most accepted approach in the 2020s is neural-guided search:

• Use RL/GNN to learn a "pre-selector" that ranks candidate branches/variables for the MILP solver (e.g., SCIP), without changing the solver itself;
• The learner acts as the "navigator" and MILP as the "verifier and refiner" — you get the best of both worlds.

Gasse et al. (2019), Exact Combinatorial Optimization with GNN, is the representative work — a GNN scores branch-and-bound selection decisions in MILP, cutting solve time substantially on medium-scale instances. This shows the RL–OR relationship is complementary, not one of replacement.

5.3 Mechanism details: from Pointer Network to Attention Model

To build intuition for "learning to construct," look at its two source models:

Model	Architecture	Mechanism in one line
Pointer Network (Vinyals 2015)	seq2seq + pointer attention	At each step, "pick one" from the input sequence; the output is an index sequence
Attention Model (Kool 2018)	Transformer encoder + context attention	Attention scores act directly as selection probabilities, enabling REINFORCE training

How the Attention Model picks the next step (TSP example):
1. Encoder: all city coordinates → node embeddings (self-attention exchanges information)
2. Context: the "last visited node + visited mask" of the current partial solution
3. Attention: similarity between the context and each unvisited city → softmax → selection probabilities
4. Training: REINFORCE + greedy rollout baseline (see the policy-gradient page)

Why this structure works: attention explicitly couples "partial-solution information" with "candidate-action information," so the model can learn the combinatorial relation of "which to pick where" — far more suitable than a plain RNN for order-sensitive selection problems. It's also the general backbone of the later large-scale routing solvers (e.g., internal systems at Amazon and logistics companies).

6. Evaluation and generalization: the problem distribution is the Achilles' heel

6.1 The "training distribution" is the soft spot of learned solvers

Training and testing for learning-to-construct must specify a problem distribution (size, structure). Three questions you must answer:

Question	Risk	Mitigation
Size generalization	Train on 15-city TSP, test on 50-city — performance craters	Curriculum learning (grow sizes gradually), multi-scale training
Structure shift	Training is all "uniformly distributed customers," reality is "clustered"	The training distribution must cover the real business distribution
Out-of-distribution (OOD)	Facing unseen constraint combinations, the policy bluffs	Keep classical heuristics as fallback

This is a close cousin of the OOD problem in offline RL: the policy has no reliable signal outside the training distribution, and any "confident mistake" becomes an incident.

6.2 Evaluation protocol

• Compare on the same public benchmarks (TSPLIB, VRPLIB, standard JSP instance libraries) — don't invent your own dataset;
• Report both the optimality gap (deviation from the best-known or optimal solution) and the solve time;
• Run multiple seeds and report mean/variance — consistent with the discipline on the evaluation & benchmarks page.

6.3 A complete numerical walkthrough: 15×15 JSP

Let's tie the whole page together with a reproducible evaluation drill (job-shop scheduling, 15 jobs × 15 machines):

Step 1  Generate the instance distribution: sample processing times and machine orders at random (fixed random seed)
Step 2  Train: GPN on 5000 training instances until convergence (REINFORCE + greedy baseline)
Step 3  Evaluate: on 100 test instances, report
        - average makespan
        - optimality gap vs. a reference optimum (solved with OR-Tools/CP-SAT)
        - per-instance solve time (milliseconds vs. seconds)
Step 4  Generalization test: re-run on unseen sizes 20×15, 25×20
Step 5  Repeat Steps 2–4 across ≥3 seeds, report mean ± variance

The four questions this protocol can answer: How good is learning-to-construct within the training distribution? How much faster is it than heuristics? How much does it drop when the size changes? How stable is it across seeds? — only with all four answers in hand is a conclusion worth writing into a project report. Missing any one of them makes the conclusion incomplete. This corresponds to the experiment-matrix specification on the evaluation in practice page.

7. Deployment reality: where RL sits in supply-chain and scheduling software

7.1 What the industry actually looks like

• In ERP/supply-chain software (the SAP and Oracle SCM ecosystems), RL isn't yet a standard component; heuristics + solvers still dominate.
• Top logistics/e-commerce players (JD.com, Cainiao, SF Express, Amazon, and others) use learned solvers internally for warehouse operations, packing, and routing; public papers are scarce, mostly showing up as tech talks.
• Cloud vendors already have public cases of RL for resource scheduling (data-center cooling, task assignment) — e.g., DeepMind's cooling optimization for Google data centers.

7.2 Deployment advice (from engineering experience)

1. First ask "why isn't the classical method enough": too large? need real-time? distribution too messy? — the answer determines whether RL is worth it.
2. Simulator before algorithm: OR-style RL depends on a high-quality problem simulator; no simulator, no data. See anatomy of an RL system, "the environment is the product."
3. Guardrails and fallback: RL outputs must be able to fall back to traditional heuristics; go live with "hybrid scheduling" and ramp up gradually.
4. Design rewards close to real costs: beyond makespan there are switching costs, energy costs, and labor efficiency — nail down reward engineering before talking algorithms.

7.3 The role of offline RL in OR

Real scheduling systems accumulate massive "historical dispatch logs + after-the-fact outcomes." Learning "better dispatch policies" from these logs with offline RL is a hot research direction, but beware:

• Logs only contain decisions made by "the then-current policy"; the consequences of "the alternatives" are missing (counterfactuals);
• Scheduling environments are highly non-stationary (demand, machine breakdowns, staffing changes), so historical distributions go stale fast.

7.4 When not to use a learned solver

Finally, a "don't use RL" checklist to avoid using it for its own sake:

Situation	Why not
Small, fixed instance sizes	MILP/CP finds exact solutions in seconds
Highly homogeneous instance structure	One heuristic suffices; RL has nothing new to learn
Extremely non-stationary demand	The training distribution keeps failing; retraining can't keep up
Approximate solutions not allowed	Hard optimality requirements (legal/audit)
No simulator / no data	A learned solver without data spins its wheels

These situations align with the "when not to use RL" decision framework in RL vs adjacent paradigms: RL is one tool in the OR toolbox, not the whole toolbox.

7.5 A hybrid-with-MILP deployment blueprint

In real systems where RL and solvers mix, here's a landable blueprint (job-shop scheduling as the example):

Layer 1  Data & instances: pull historical work orders, machines, and process data from MES/APS systems → generate a problem-instance distribution
Layer 2  Learning to construct: a GPN/Attention model produces an initial schedule in milliseconds → gives the scheduler a "starting point"
Layer 3  Classical solver: run MILP/CP-SAT refinement for "critical bottleneck weeks" (minutes) → high-quality final schedule
Layer 4  Fallback rules: on solver timeout/failure, fall back to priority rules (e.g., SPT/EDD) → a plan is always guaranteed

Layer	Output	Time	Role
Learning to construct	Usable initial solution	Milliseconds	Fallback + warm start
Solver refinement	High-quality solution	Seconds–minutes	Improve solution quality
Rule fallback	Feasible solution	Instant	Last line of defense for reliability

Why this division of labor makes sense: RL is responsible for "fast," the solver for "accurate," and the rules for "stable" — none of the three steps on the others' toes, and every layer has the next one as a safety net. This is an order of magnitude more feasible than "letting RL end-to-end replace the scheduling system," and it's consistent with the "safety guardrails" layer in anatomy of an RL system. Most industrial OR projects should start life as this three-layer structure.

8. Summary: a decision table for RL × OR

Situation	Use what	Notes
Small scale, exactness feasible	MILP/CP	RL is pointless
Medium scale, stable structure	Heuristics/solvers	Start classical; don't rush to RL
Large scale, real-time solutions required	Learning to construct (RL-trained) + heuristic fallback	RL's main battlefield
Continuously evolving environment, massive logs	Offline RL pretraining + online fine-tuning	Frontier direction; deploy cautiously
Multi-actor competition (multi-tenant/multi-carrier)	Multi-agent RL (research)	In practice usually treated as noise

TIP

One line for engineering teams: in OR, RL's first success is not "replacing the solver" but "making the solver faster" (neural-guided search). Starting from "accelerating the existing system" is far more realistic than "end-to-end replacement" — and it fails far less often.

Further reading

• Markov decision processes — the full formal toolkit for writing OR problems as MDPs.
• RL vs adjacent paradigms — boundary analysis of RL vs OR, planning, and search.
• Offline RL — methods and pitfalls for learning from dispatch logs.
• Multi-agent RL — the game-theoretic view of multi-machine coordination and multi-tenant resource allocation.
• Reward engineering — writing multi-objective rewards for makespan, cost, and energy.
• Policy gradient methods — REINFORCE baselines and PPO in solver training.

References

• Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer Networks. NeurIPS 2015. (arXiv:1506.03134)
• Bello, I., et al. (2017). Neural Combinatorial Optimization with Reinforcement Learning. ICLR 2017. (presented at ICLR 2017; preprint submitted November 2016)
• Kool, W., van Hoof, H., & Welling, M. (2018). Attention, Learn to Solve Routing Problems! arXiv:1803.08475. (ICLR 2019)
• Nazari, M., et al. (2018). Reinforcement Learning for Solving the Vehicle Routing Problem. NeurIPS 2018. (arXiv:1802.04240)
• Zhang, C., et al. (2020). Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. NeurIPS 2020. (arXiv:2010.12367)
• Gasse, M., et al. (2019). Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS 2019. (arXiv:1906.01629)
• DeepMind & Google blog (2018). Machine Learning for Network Routing (public demo of data-center traffic engineering).
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. (MDP formalism and dynamic programming in Chapters 3–4)