Contents
Figure 1: Job Shop Scheduling with Reinforcement Learning (Python Tutorial) — a six-by-six shop is small enough to train on a laptop and honest enough to expose a bad baseline
Your shop floor has six jobs, six machines, and one planner who swears the schedule "worked fine last week." You want a smarter dispatcher, and you want to build it yourself. Reinforcement learning can learn dispatching rules from experience, and the Python setup is shorter than you would expect.
I have not run this on a real factory, so treat it as a learning project rather than a production blueprint. What I did do is run every line below on a laptop and measure it: 20 held-out instances, three baselines, real numbers. Building a tiny version teaches you more than reading ten papers — especially when the numbers surprise you.
What Is the Job Shop Scheduling Problem?
Each job contains a sequence of operations, and each operation needs a specific machine for a fixed duration. Operations within a job must run in order, and each machine handles one operation at a time. The goal is to minimise the makespan: the time when the last job finishes.
The problem is NP-hard, so solve time explodes as instances grow. Dispatching rules like shortest processing time (SPT) run in microseconds but leave quality on the table. RL tries to learn a better rule from experience — the same trade-off I analysed for OR-Tools versus reinforcement learning, where a solver usually wins on a single static instance.
How RL Frames the Problem
You need a Markov decision process before any algorithm helps. Here is the formulation used below:
- State: each job's progress, next machine, next duration and ready time, plus each machine's free time.
- Action: pick which job schedules its next operation.
- Reward: the negative increase in makespan after each decision, divided by the longest operation so the scale stays near 1.
- Episode end: every operation has a start time.
Why choose a job instead of an operation? Because each job offers exactly one eligible operation at a time, which keeps the action space at six and the logic clean. The cost is that you cannot express "wait for a machine" — a real dispatcher can.
Setting Up Your Environment
pip install gymnasium stable-baselines3 sb3-contrib ortools numpy
The run behind this post used gymnasium 1.4.0, stable-baselines3 2.9.2, sb3-contrib 2.9.2, torch 2.15.0+cpu, OR-Tools 9.15.6755 and NumPy 2.5.3 on Python 3.12. Library versions change often, so check the docs if an import fails [1][2].
Building the Gymnasium Environment
This environment generates a random instance on every reset, which forces the agent to learn a policy rather than memorise one schedule.
import numpy as np
import gymnasium as gym
from gymnasium import spaces
class JobShopEnv(gym.Env):
MAX_DUR = 9
def __init__(self, n_jobs=6, n_machines=6):
super().__init__()
self.n_jobs, self.n_machines = n_jobs, n_machines
self.action_space = spaces.Discrete(n_jobs)
self.observation_space = spaces.Box(
0.0, 1.0, shape=(n_jobs * 4 + n_machines,), dtype=np.float32
)
def _random_jobs(self):
return [
[(int(m), int(self.np_random.integers(1, self.MAX_DUR + 1)))
for m in self.np_random.permutation(self.n_machines)]
for _ in range(self.n_jobs)
]
def reset(self, seed=None, options=None):
super().reset(seed=seed)
self.jobs = (options or {}).get("jobs") or self._random_jobs()
self.horizon = sum(d for job in self.jobs for _, d in job)
self.next_op = np.zeros(self.n_jobs, dtype=int)
self.job_ready = np.zeros(self.n_jobs)
self.machine_free = np.zeros(self.n_machines)
self.makespan = 0.0
return self._obs(), {}
def action_masks(self):
return self.next_op < self.n_machines
def _obs(self):
feats = []
for j in range(self.n_jobs):
if self.next_op[j] < self.n_machines:
m, d = self.jobs[j][self.next_op[j]]
feats += [self.next_op[j] / self.n_machines,
(m + 1) / self.n_machines,
d / self.MAX_DUR,
self.job_ready[j] / self.horizon]
else:
feats += [1.0, 0.0, 0.0, self.job_ready[j] / self.horizon]
feats += list(self.machine_free / self.horizon)
return np.array(feats, dtype=np.float32)
def step(self, action):
j = int(action)
m, d = self.jobs[j][self.next_op[j]]
start = max(self.job_ready[j], self.machine_free[m])
end = start + d
self.job_ready[j] = self.machine_free[m] = end
self.next_op[j] += 1
old, self.makespan = self.makespan, max(self.makespan, end)
reward = -(self.makespan - old) / self.MAX_DUR
done = bool((self.next_op >= self.n_machines).all())
return self._obs(), reward, done, False, {}
Sanity check before training: the observation is 30 numbers (six jobs × four features plus six machines), and every action is valid at reset. If your shapes or your mask are wrong, PPO will happily train on garbage.
Why the Action Mask Matters
Once a job finishes, the agent must stop picking it. The action_masks method blocks invalid actions before the agent even considers them. Penalties alone teach rule-following slowly and unreliably, so masking is the better default [2].
Without a mask, an invalid action indexes past the end of the job's operation list and raises an exception mid-episode. With one, the choice simply does not exist.
Training the Agent with MaskablePPO
Stable-Baselines3's core PPO does not support masking, but sb3-contrib provides MaskablePPO:
from sb3_contrib import MaskablePPO
from sb3_contrib.common.wrappers import ActionMasker
env = ActionMasker(JobShopEnv(), lambda e: e.unwrapped.action_masks())
model = MaskablePPO("MlpPolicy", env, verbose=0, seed=0)
model.learn(total_timesteps=200_000)
On this laptop CPU, 200,000 timesteps took 4.9 minutes and a further 200,000 took another 5.2 minutes. Watch the reward curve in the logs; if it never improves, suspect the reward or observation design before blaming PPO.
Building Three Baselines
An RL result means nothing without comparisons. Two dispatching rules and an exact solver, all on the same instances.
Baseline 1: Shortest Processing Time
def spt_action(env):
valid = np.flatnonzero(env.action_masks())
return min(valid, key=lambda j: env.jobs[j][env.next_op[j]][1])
def run_spt(jobs):
env = JobShopEnv()
env.reset(options={"jobs": jobs})
done = False
while not done:
_, _, done, _, _ = env.step(spt_action(env))
return env.makespan
Baseline 2: Most Work Remaining
SPT alone is a weak bar in this construction, so add a second rule that is actually competitive for makespan:
def mwkr_action(env):
def remaining(j):
return sum(d for _, d in env.jobs[j][env.next_op[j]:])
return max(np.flatnonzero(env.action_masks()), key=remaining)
Baseline 3: OR-Tools CP-SAT
CP-SAT finds optimal or near-optimal schedules on small instances, so it is your ground truth [3]:
from ortools.sat.python import cp_model
def solve_cp(jobs, seconds=10):
model = cp_model.CpModel()
horizon = sum(d for job in jobs for _, d in job)
by_machine, ends = {}, []
for j, job in enumerate(jobs):
prev_end = None
for k, (m, d) in enumerate(job):
s = model.NewIntVar(0, horizon, f"s{j}_{k}")
e = model.NewIntVar(0, horizon, f"e{j}_{k}")
by_machine.setdefault(m, []).append(
model.NewIntervalVar(s, d, e, f"i{j}_{k}"))
if prev_end is not None:
model.Add(s >= prev_end)
prev_end = e
ends.append(prev_end)
for ivs in by_machine.values():
model.AddNoOverlap(ivs)
makespan = model.NewIntVar(0, horizon, "makespan")
model.AddMaxEquality(makespan, ends)
model.Minimize(makespan)
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = seconds
solver.Solve(model)
return solver.ObjectiveValue(), solver.StatusName()
Note that solve_cp returns two values, not one. The draft version of this loop packed that tuple straight into a results list, and the mean calculation then fails on a nested tuple — unpack it, or you will debug numpy instead of scheduling.
Evaluating Everything Fairly
Test on fresh instances the agent never saw during training:
def run_policy(model, jobs):
env = JobShopEnv()
obs, _ = env.reset(options={"jobs": jobs})
done = False
while not done:
action, _ = model.predict(obs, action_masks=env.action_masks(),
deterministic=True)
obs, _, done, _, _ = env.step(action)
return env.makespan
test_env = JobShopEnv()
results = []
for seed in range(20):
test_env.reset(seed=1000 + seed)
jobs = test_env.jobs
cp, _ = solve_cp(jobs, 5)
results.append((run_policy(model, jobs), run_spt(jobs), cp))
rl, spt, cp = np.mean(results, axis=0)
print(f"RL: {rl:.1f} | SPT: {spt:.1f} | CP-SAT: {cp:.1f}")
Compute the optimality gap too: (rl - cp) / cp. And print the per-instance numbers, because an average hides the variance that decides whether a policy is usable.
What the Numbers Actually Showed
Twenty held-out 6x6 instances, same seeds for every method, deterministic policy evaluation:
| Method | Mean makespan | Gap vs CP-SAT | Notes |
|---|---|---|---|
| Random valid actions | 75.6 | +57.5% | sanity floor |
| SPT | 111.6 | +132.5% | weak in list scheduling |
| MWKR | 61.1 | +27.4% | the real bar |
| MaskablePPO, 200k steps | 57.5 | +19.7% | 4.9 min training |
| MaskablePPO, 400k steps | 56.2 | +17.1% | 10.1 min training |
| CP-SAT (5 s cap) | 48.0 | optimal | 0.06 s mean |
| Lower bound | 39.8 | — | max(machine load, longest job) |
The trained policy beat SPT on all 20 instances and beat MWKR on 14 of 20, but it never matched CP-SAT. Doubling training from 200k to 400k timesteps improved the mean by 1.3 makespan units — real, and small.
The surprise is SPT: 132% above optimal. In this priority-list environment SPT defers every long operation to the end of its job, so the final operations arrive in a clump and serialise. A single baseline would have made RL look heroic; the MWKR column is why you always run two.
Latency is the other half of the story: about 23 ms per instance end to end for the policy, against 0.06 s for CP-SAT. At six jobs, CP-SAT wins on both quality and wall clock, which is the honest headline.
How to Improve Your Agent
Try these upgrades in order:
- Train longer. Doubling to 400k steps moved the mean from 57.5 to 56.2 here, so expect diminishing returns rather than a breakthrough.
- Improve the observation: add remaining work per job and per machine, which is the feature MWKR uses.
- Tune the reward. Test alternatives such as negative machine idle time.
- Use a graph neural network. Graph encodings of operations and machines represent the structure far better than flat vectors [5].
- Scale gradually. Move from 6x6 to 10x10 only after the small version works.
- Use curriculum learning: easy instances first, harder ones later.
Common Pitfalls
- Training on one instance. The agent memorises it and fails everywhere else.
- Skipping the mask. Invalid actions waste training time and break schedules.
- Comparing against a single baseline. SPT lost by 132% here while MWKR lost by 27%; one baseline would have told you the wrong story.
- Ignoring the reward scale. Huge rewards destabilise training, so normalise them.
- Testing on training data. Use fresh seeds, always.
- Reporting a mean without the spread. The policy's standard deviation was 6.4 makespan units, so single-instance wins mean nothing.
Best Book to Read
| Book | Description | Get it |
|---|---|---|
| Reinforcement Learning: An Introduction | explains why a masked policy over a small action space learns at all, and its treatment of value estimation is what makes reward design less of a guessing game [4]. | View on Amazon |
As an Amazon Associate I earn from qualifying purchases. Links on this page are affiliate links, and I may earn a commission at no extra cost to you.
The authors publish the second edition free online, so you can start before the book arrives. For the routing version of the same experiment, see neural policies versus classical heuristics.
Wrapping Up
You just built a complete RL scheduling pipeline: an environment, a masked PPO agent, and three solid baselines. On 6x6 instances the policy lands 17% above a CP-SAT optimum that takes 60 milliseconds to find, which is exactly why production scheduling still starts with a solver.
So run the script this week, then change one thing: the reward, the observation, or the instance size. Watch what breaks. If your agent beats MWKR, that is a real result; if it only beats SPT, you have measured the baseline, not the agent.
Frequently Asked Questions
Why mask invalid actions instead of penalising them?
Because a penalty teaches the rule slowly and unreliably, while a mask removes the choice entirely. Once a job's last operation is scheduled, it must never be picked again, and MaskablePPO applies the mask before sampling, so the agent cannot waste a step or corrupt the schedule.
Why is shortest processing time so bad in this setup?
Because the environment builds a priority list rather than a time-stepped dispatch, and SPT defers long operations to the end of every job. That leaves the last few operations long and serialised, so makespan suffers badly: SPT averaged 111.6 against a CP-SAT optimum of 48.0 in the run for this post.
How long does the agent take to train?
About five minutes for 200,000 timesteps on a laptop CPU with a small MLP policy, and about ten minutes for 400,000. Inference afterwards costs roughly 23 milliseconds per instance end to end, including the environment loop.
Does the trained agent generalise to unseen instances?
Yes on the distribution it trained on: it beat SPT on all 20 held-out 6x6 instances and beat the stronger most-work-remaining rule on 14 of 20. That is not the same as generalising to 10x10 shops or to instances with different duration distributions, which need their own test set.
Should I use RL or CP-SAT for real scheduling?
CP-SAT for anything static, small or auditable, because it proves optimality in milliseconds at this size. RL makes sense when instances arrive constantly, the shop is stochastic, and you need a decision in milliseconds, or as a warm start that a solver then improves.
Sources
[1]Gymnasium, Environment API — thereset/stepcontract, spaces and seeding behaviour that this environment implements: gymnasium.farama.org[2]sb3-contrib, Maskable PPO — the action-masking wrapper andpredict(..., action_masks=...)signature used in the training and evaluation loops: sb3-contrib.readthedocs.io/en/master/modules/ppo_mask.html[3]Google OR-Tools, CP-SAT solver — interval variables,AddNoOverlapandAddMaxEquality, the building blocks of the ground-truth model: developers.google.com/optimization/cp[4]Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition — the free online edition, including policy gradients and value estimation: incompleteideas.net/book/the-book-2nd.html[5]Taillard, Benchmark instances for job shop scheduling — the standard instance sets to test against once the 6x6 toy works: optimizizer.com/TA.php