Flow shop scheduling
Every job takes the same path through your production line, and you set the order by feel. Our model computes it for the whole week.
- Free 30-minute call
- No commitment
- You own the code
In short: A flow shop schedule plans a production line where every job passes the same stations in the same order. It chooses the job sequence that finishes the whole batch soonest or misses the fewest due dates.
The problem
On Monday at six, the production line starts up. Every job goes to the press, then the oven, then assembly, then packing. The only open question is which job goes first. You set the order the way it’s always been set: by feel, and by which customer called most often. By Wednesday the oven has nothing to do, and a finished job waits because packing has no room.
This is a flow shop. In a job shop, every order takes its own route through the machines. Here every job takes the same path, without exception. Because the stages are fixed, only one decision is left: the order in which jobs start. Once that order is set, every machine inherits it, mistakes included.
Where a production line loses time
Buffers are the waiting spaces between stages, and they are limited. A job that finishes early may wait because the next queue is full. With no buffer at all, a machine can’t pass a job on until the next stage has room. In planning, this is called blocking. So one long job in the wrong place can stop every stage before it.
Some production lines allow no waiting at all. Once a job starts, it must move through every stage without pausing, for example because a hot part would cool down. In planning, this is called no-wait. Rules like these remove the waiting time that normally absorbs delays. On such lines, the order of jobs matters even more.
Why generic scheduling software underperforms
Generic scheduling software applies dispatch rules, simple fixed priorities such as shortest processing time first or earliest due date. It fixes a sequence and stops. It has no objective function. That’s a score that judges possible sequences by your criteria. So it can’t say how close it gets to the best makespan, the time until the last job is finished.
The software doesn’t know what only your production line has: how small each buffer is, which stage blocks, where a job must not wait. You keep those rules in your head. We build the model for your line, and each of those rules becomes a constraint. You check the result on your own orders before you decide.
What changes
Today, you set Monday’s order by feel and find out on Wednesday where the production line stalls. Our model proposes the order for the whole week, with every buffer and no-wait rule built in. You see where jobs will wait before it happens. You check the sequence, swap a job if a customer calls, and release it.
Same five jobs, two orders
Take five jobs, A to E. Each goes through a press, then an oven. Times are in hours, press first. A needs 3 and 4, and B needs 5 and 2. C needs 2 and 5, D needs 6 and 4, and E needs 3 and 3.
Run them in the order the phone rang, say B, then D, E, A and C. The oven finishes the last job after 27 hours. Now run C, then A, E, D and B instead. Same jobs and same machines, yet the oven is done after 21 hours. Nobody worked faster, and the order alone gave back six hours.
That second order isn’t luck. It comes from Johnson’s rule, published by Selmer Johnson in 1954 for two-stage lines. Find the shortest time in the table. If it’s on the first machine, that job goes as early as possible; if it’s on the second, as late as possible. Cross it off and repeat. And no order finishes in under 21 hours: the press alone needs 19, and the last job still needs its oven time.
Flow shop scheduling optimisation: what you get
With flow shop scheduling optimisation, jobs finish sooner and more of them finish on time. We model your stages, buffers, blocking and no-wait rules, and your goals for makespan and lateness. We test the model with your orders and in your busiest weeks before it goes live. You judge it on makespan, on-time delivery, buffer waiting time and machine utilisation.
- A model written around your own flow 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.
The permutation flow shop (PFSP)
Finding the best job order for such a production line is called the flow shop scheduling problem (FSP). Its simplest form is the permutation flow shop (PFSP). Permutation is the maths word for an ordering. In a PFSP, every machine processes the jobs in the same order. You choose one sequence and repeat it at every stage.
Ten jobs can already run in 3.6 million different orders. A job shop of the same size has vastly more, because each machine picks its own order. For two machines, Johnson’s rule finds the best sequence with no search at all. In optimisation, that’s called polynomial time: the work grows gently as you add jobs.
For three or more machines, no such simple rule exists, but the structure still helps. Branch-and-bound is an exact method that splits the search into branches. It drops every branch that can’t beat the best sequence found so far. The NEH heuristic, named after Nawaz, Enscore and Ham, is a fast rule of thumb. It inserts jobs one at a time, each in its best position so far. In a flow shop, every job takes the same path. That feels rigid, but it is exactly what makes the problem easier to solve.
Makespan, tardiness and the rules of your production line
What you optimise is usually makespan or weighted tardiness. Makespan decides how much the production line ships in a day. Total weighted tardiness adds up how long after their due dates jobs finish. Important jobs count more. It decides whether customers reorder.
Buffers, blocking and no-wait rules limit which sequences work. Blocked and no-wait lines are harder to schedule, because they remove the waiting time that absorbs delays. But they still use one order for all machines. So they stay far easier to plan than a job shop of the same size. The model treats each of these rules as a hard constraint and keeps it in every plan.
How hard flow shop scheduling is
Minimising makespan in a flow shop is NP-hard from three machines up. NP-hard means no known method finds the proven best answer quickly once the problem grows. In practice, though, exact branch-and-bound can still solve much larger flow shops than job shops.
Beyond that, metaheuristics take over. These are search strategies that keep improving a sequence without proving it’s the best. Large neighbourhood search tears up part of a sequence and rebuilds it. Tabu search bans its own recent moves for a while, so it can’t circle back. Genetic algorithms breed new sequences from the best of the old ones. Where the case is small enough, we use mixed-integer linear programming (MILP), which models the sequence as yes-or-no decisions and proves the best answer.
Hybrid flow shop scheduling and other variants
The permutation flow shop is the base case: one order for every machine. A non-permutation flow shop lets each machine reorder the jobs. That can shorten makespan if there is room in front of a stage to re-sort waiting jobs. But then you lose the advantage of one order for all machines. On a production line with no room for a queue, it’s rarely worth it.
The hybrid flow shop (HFS), sometimes called a flexible flow shop, is what most plants run. Here one or more stages have several machines working in parallel. So at that stage, the plan also has to say which machine each job runs on. The schedule decides both the job order and the machine assignment.
Food processing line scheduling
Food processing is a hybrid flow shop almost by definition. Several cooking kettles or filling machines work side by side at one stage, then feed a shared packing line. Electronics assembly works the same way, with parallel placement lines. So does textile production, with several looms at one stage.
In each case, the sequence decides how long jobs wait between stages. The machine assignment decides whether parallel machines share the load or one of them becomes the bottleneck. That’s why our production scheduling treats the hybrid flow shop as the central case.
Common questions.
Something else? Ask us directly.
Ask whether every product visits the stages in the same order. If it does, even when some products skip a stage, you have a flow shop. If orders pick their own route, it’s a job shop. Many plants are a flow shop with a few parallel machines at one stage. That’s the hybrid flow shop, and it’s the most common case we see.
If your production line really has two stages and nothing else matters, yes. Johnson’s rule then gives the sequence with the shortest makespan, the time until the last job is finished. You can work it out on paper. Add a third stage, due dates, limited space between the stages or setup times, and the rule no longer finds the best sequence for sure. The rule then becomes a decent starting sequence that a model improves.
They become switch costs and rules in the model. Running a product without an allergen after one that contains it needs a full clean, so the order matters a lot. The model groups products by cleaning needs and places the cleans where they cost least. Due dates still count, so it never groups products without checking the due dates.
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.
Similar pages.
Terms on this page
Every abbreviation explained in plain words, in our article “Metrics and methods”.
- Makespan
- FSPFlow shop scheduling problem
- HFSHybrid flow shop
- NEHNEH heuristic
- MILPMixed-integer linear programming
- Branch and bound
- NP-hardNP-hard
- Heuristic and metaheuristic
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