Skip to content

Job shop scheduling

In a job shop, every order takes its own path, and each rush order means replanning by hand. We schedule the whole shop at once.

  • Free 30-minute call
  • No commitment
  • You own the code
Typical industries
Manufacturing
Problem type
Scheduling
You receive
A documented model, run on your data

In short: A job shop schedule plans a workshop where each order follows its own route through the machines. It sets the order of operations on every machine, so jobs finish on time and the shop stays busy.

The problem

On Tuesday morning, a rush order lands on your desk. It needs the lathe, then the mill, then heat treatment. The lathe is busy and the mill already has a queue. You move three jobs to make room and hope no other order runs late. By Thursday another order is late, and nobody saw it coming.

That’s a job shop. Each order has its own routing, the list of machines it visits in turn. The next order needs the mill, then grinding, then quality inspection. A third needs the lathe twice. In a flow shop, by contrast, every job visits the same machines in the same order.

So every order competes for the same machines, each in its own sequence. No machine can run two jobs at once. The schedule decides when each step runs, and on which machine. Get it wrong and machines stand idle, orders finish late, and you rebuild the week by hand on Friday.

Signs your job shop needs a model

You rebuild the sequence by hand whenever a rush order lands. Some machines sit idle while queues pile up in front of others. You promise due dates on gut feeling and miss them on a regular basis. Expediting, chasing late orders through the shop, has become daily routine. You can't say what a new order will do to the rest of the week.

Why your ERP schedule still runs late

Most shops already own a scheduler. It came with your ERP. Most ERP systems use classic material requirements planning (MRP). It counts back from each due date. For that, it assumes a fixed lead time, the time an order needs to pass through the shop. It assumes every machine has unlimited capacity. So it will happily load three jobs onto one mill on the same morning. You only see the mistake on the shop floor.

Scheduling add-ons go further and apply dispatch rules. These are fixed priorities, such as earliest due date, first in first out or shortest operation first. They respect capacity, but they have no objective function, a score that judges possible plans by your criteria. So the add-on doesn’t weigh anything up. Which due date matters more? Is a longer changeover worth it if the order finishes sooner? You make those calls in your head, one rush order at a time.

The add-on doesn’t know what only your shop has: which changeover takes long, which fixture exists only once, which machine can run only certain parts. We build the model for your shop. Each of your rules becomes a constraint. You check the result on your own orders before you decide.

What changes

Today, a rush order means you reshuffle the week by hand and hope. Our model re-plans every machine from the current state of your machines and orders. It shows which orders move and which due dates are at risk. You check the new sequence, change what you know better and release it. The rush order goes in, and you see what it does to the rest of the week.

Rescheduling when a machine fails or a rush order lands

The week's schedule rarely stays valid until Friday. A machine breaks down, a rush order arrives or material comes in late. The model recalculates from the current state of the floor. It locks the operations already running and re-plans everything still ahead. It repairs the plan you have, so you stay in control of what changes.

Job shop scheduling optimisation: what you get

We put your machines, operations, setup times and goals into one model. A good sequence means shorter lead times, fewer late orders and less steel waiting between machines. You see in advance what a new order does to the rest of the week. We test the model with your orders and in your busiest weeks before it goes live.

You judge the result on four figures: makespan, on-time delivery, setup hours and machine utilisation. Makespan is the time until the last job of the week is finished. You already know these numbers for today’s plan, so the comparison is fair from day one.

  • A model written around your own job shop scheduling rules.
  • Results measured in the numbers you already track.
  • It slots into how you already work, and you can check every answer it gives.

How it works

Every shift, job and resource goes into one model, and your rules go in as hard limits. You get the best schedule that keeps all of them. What “best” means is your call: lowest cost, the fairest split or the fewest late orders.

What the job shop scheduling problem (JSP) is

In planning, this is called the job shop scheduling problem (JSP). It’s the most general case of production scheduling, because each job has its own routing. Each job is a chain of operations, one step on one machine each, in a fixed order. Each operation needs a specific machine for a known time. If every job shares one route, it’s a flow shop, which has its own page: flow shop scheduling.

Why job shop scheduling is so hard

Every schedule must keep two rules at once. Precedence means an operation never starts before the previous step of its job is finished. Capacity means no machine runs two operations at once. On their own, both rules are easy. It gets hard when several jobs need the same machine.

An example: the machine your third operation needs is still busy with another job’s first operation. So every choice about which job goes next pushes back later steps of other jobs. In optimisation, this is drawn as a disjunctive graph, where disjunctive means either-or. Each job’s route is a fixed chain of arrows. Each machine adds an either-or choice: which of two jobs goes first?

Makespan, tardiness and setups

What you optimise is usually makespan or tardiness, and the two differ. Makespan decides how much the shop can push through in a week. Tardiness is how far jobs finish past their due dates. It decides whether customers come back. The shortest makespan doesn’t always mean the fewest late orders. A job can pass through the shop quickly and still miss its due date.

Setup times affect both. A setup time is the time it takes to change a machine over between two jobs. With sequence-dependent setup times (SDST), that changeover depends on which job ran before. So the job order decides how much capacity goes to changeovers instead of cutting metal. Job shop makespan minimisation only works when all three are solved together. In our model, they’re goals it scores. Capacity and precedence are hard constraints it never violates.

What NP-hard means for your shop

Job shop scheduling is NP-hard. The label comes from complexity theory. It means no known method finds the proven best schedule in reasonable time once the shop grows. The number of possible schedules explodes with every job and machine.

In 1963, Fisher and Thompson published a test case with ten jobs on ten machines. For more than 25 years, nobody could prove which schedule was best. A branch-and-bound method finally did. That’s an exact search that discards whole groups of schedules once it’s clear that none of them can be the best. Your shop probably has more than ten jobs on a quiet Tuesday. So what counts for you is how good the schedule is, how fast it arrives and whether it still works when the mill breaks down.

MILP or a JSP metaheuristic solver

For small cases, say ten jobs on five machines, we use mixed-integer linear programming (MILP). MILP writes the schedule as a maths model of yes-or-no decisions, such as whether job A runs before job B. The model then rules out whole groups of schedules that can’t win. You get the best schedule and the proof that none is better. The model also extends cleanly to due dates, setups and release times, the earliest moment a job may start.

A realistic job shop has dozens of jobs, sequence-dependent setups, rush orders and breakdowns. That’s far beyond exact methods, so metaheuristics are the standard there. These are search strategies that keep improving a schedule without proving it’s the best. Large neighbourhood search (LNS) tears up part of a schedule and rebuilds it. Tabu search bans its own recent moves for a while, so it can’t circle back.

At some point, no small change improves the schedule any more, although better schedules exist. In optimisation, such a schedule is called a local optimum. A simple search stops there. Tabu search can move on, because it may not undo its recent changes for a while. Genetic algorithms breed new schedules from the best of the old ones. None of them proves it found the best schedule, but they return strong ones within the time you have. For a custom JSP algorithm, we pick the method by the size of your shop. We tell you openly what that means for the quality of your plan.

Common questions.

Something else? Ask us directly.

Classic material requirements planning (MRP) inside your ERP counts back from due dates and assumes every machine has unlimited capacity. So the plan can look fine and still be impossible on the floor. Add-on modules that respect machine capacity fix that. But they usually set the order of jobs by fixed priority rules, such as “earliest due date first”. Neither MRP nor the add-ons weigh one late order against another. Our model does: it compares the plans and shows you what each one costs in late orders.

Not with a model. In a job shop with many product variants, a schedule made by hand is quickly out of date, so you end up patching it all day. The model takes that patching off your hands. When a machine fails or a rush order lands, it re-plans from the current state of the floor, and you review the changes instead of rebuilding the week.

Usually yes, as long as they’re roughly right and you know which ones are wrong. We compare planned times with the times your shop floor reports and correct the worst ones first. A model built on honest times beats one built on optimistic standards. If your ERP says 118 hours and the job really takes 134, every plan is 16 hours short.

For a handful of machines and stable orders, often yes. It gets hard when rush orders and shared machines mean that every change moves many other dates in the week. A whiteboard shows the plan. But it can’t tell you which other orders will be late because of a new one. That’s usually the moment shops start looking for something better.

Sometimes it can, and if that’s the case, we’ll tell you. Standard software is built for an average operation, though. Yours runs on its own rules: your contracts, your exceptions, the things you know by heart. A custom model writes those rules in, and that’s where the better plan comes from.

You don’t need either to start. We build the model from the data you’ve already got, even if it lives in three spreadsheets and one person’s head. You get a system you run yourself. We train your team until they no longer need us.

You see a first result with the prototype, before you commit to anything bigger. We start with a free 30-minute call about your operation and the model that would fit it. Then we build a working prototype and run it on your numbers.

Tell us what you’re planning.

In a free 30-minute call with a specialist, you find out whether optimisation can help.

  • Free, no commitment
  • You talk to a specialist directly
  • A clear go or no-go