Solving the Job Shop Problem using Google's OR-Tools

Written from inside a 24/7 manufacturing operation in 2019. Republished here, unchanged, with a coda on where the same math ended up seven years later.

The 2019 article

Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science where jobs are assigned to resources at particular times. The classic job shop scheduling problem of minimizing makespan was first presented by Fischer and Thompson in 1963 and has been solving in a variety of ways since. As Industry 4.0 adoption increases so does the need to model data that bounds algorithms and guides AI training. Using Google's Operational Research libraries I ported an existing python solution to C# to better understand job shop data modeling and improve my python skills.

Solving a job shop problem quickly can enable real-time production schedule updates for reactive or proactive responses to disrupting factors. Machine level telemetry combined with cloud compute power can help business better predict future bottlenecks and maximize throughput if data and systems are well modeled/defined. Effective data modeling also helps standardize communication when connecting Cyber Physical Systems (CPS) to a Manufacturing Execution System (MES) enabling iterative ROI impacts while transitioning to Industry 4.0 insights and supporting parallel development of training supplemental machine learning algorithms to enhance existing planning and scheduling resources.

Google's OR-Tools is "open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions." Let's take a look specifically at using OR-Tools to solve a JSP with the following constraints:

• A task must be completed before the next task in the job starts
• Only one task can be run on one machine at a time
• Once started a task must run to completion

We first need to describe the jobs as a sequential set of tasks consisting of machine and the amount of processing time required to complete.

Given the above problem set here is one possible solution. [The original showed the schedule as a chart.]

Then we find our bounds for the maximum makespan, machine count and define containers to hold the variables describing every task in a job.

After defining our task variables the following constraints must be added:

• Precedence constraints — All previous tasks in a job must be completed before the next can start
• No overlap constraints — A machine can only work on one task at a time

Next we use the modeled data to define our objective — find the shortest makespan or length of time between the start of the first task and completion of the last task.

Finally we submit the model to Google's API and display the results. Which can be either an optimal schedule, multiple equal solutions or an unsolvable solution if invalid constraints are defined. In this example an improved solution resulting in a makespan of 11 vs 12 was found.

Businesses using LEAN, ANSI, ISA 95, domain driven design or any combination of process and data modeling can leverage modern free libraries to realize iterative returns during their Industry 4.0 transition while improving current production planning capabilities.

To view the full source check out JobShopController.CS in my public repo ported from Google's python solution. [2026 note: that repo didn't survive the intervening seven years. The coda below is partly about what did.]

2026 coda: the same problem, wearing a different shop

I wrote the article above from inside a 24/7 global manufacturer of sports apparel, where I worked on a production-planning platform moving hundreds of millions of dollars of orders a year. Porting Google's job-shop sample wasn't research. It was me writing down the abstraction after living inside the real thing — trying to understand, on my own time, the math underneath the system I worked on all day.

Seven years later I run a job shop again. It's in my house.

The machines are GPUs. The jobs are build briefs executed by AI agents — plan this, build this, test this, review this — dispatched across a small fleet of always-on computers. And the three constraints from 2019 apply verbatim: tasks in a job run in order, one task per machine at a time, and once started a task runs to completion. The solver is the same too: CP-SAT, out of the same OR-Tools library, still free.

Two things changed. The first is the objective. Makespan is a factory's objective — time is the scarce thing when the machines are paid for. In my shop the machines are sunk cost and the scarce resource is metered: frontier-model API tokens cost real money, while the local GPUs cost electricity. So the objective flipped from "finish everything fastest" to "meet the deadlines while spending as little of the expensive machine as possible." Schedule the metered machine last, and only when a local one can't do the job.

The second is the constraint that turns out to matter. In a factory, processing time dominates. In a GPU shop, setup dominates: loading a 30-billion-parameter model into GPU memory can take longer than the inference you loaded it for. That makes it a job shop with sequence-dependent setup times — the classic extension — and the scheduling win is residency: put two jobs that need the same model back-to-back and the second one's setup is free.

Here's what that's worth. I recently ran an assay: 250 image-generation requests across three models, bursty arrivals, two dozen rush deadlines, two GPUs. First-in-first-out thrashed: 24 model loads and 19 missed deadlines. Sorting by model fixed the loads (3) but missed 16 deadlines. CP-SAT, with model residency and per-card memory in the model: 3 loads, zero misses, proven optimal in under two minutes. Fischer and Thompson's 1963 problem, Google's free solver, consumer hardware — doing real work in a home lab.

Rereading the 2019 piece, the paragraph that aged best isn't the one about the solver. It's the unglamorous one about data modeling — standardizing how cyber-physical systems talk to a manufacturing execution system. Swap "cyber-physical systems" for AI agents and "MES" for an orchestration ledger, and the sentence still holds without edits. The solver was never the hard part. The hard part is the telemetry and the modeling that make the solver's inputs true: what each machine can actually do, how long tasks actually take, what it actually costs. In 2019 that data came from the factory floor. In 2026 it comes from a ledger that records every task my agents run. Different floor, same discipline.

The job shop was never really about factories. It's the shape scarcity takes whenever constrained machines meet more work than time. In 2019 the machines cut and stitched. In 2026 they think. Either way, someone still has to walk the land before the cutting starts — and the walk is worth writing down.