Permutation Flow Shop

SFC · Operational · canonical PFSP

Graham three-field classification Fm | prmu | Cmax

The permutation flow shop problem (PFSP) is the most studied scheduling problem in operations research. n jobs pass through m machines in the same order, and every machine must process jobs in the same permutation. Choose the sequence that minimises the makespan Cmax. Johnson (1954) solved the two-machine case optimally; for m ≥ 3 the problem is strongly NP-hard. The state-of-the-art combines NEH (1983) as a constructive backbone with iterated-greedy metaheuristics (Ruiz & Stuetzle 2007).

Where This Decision Fits

APICS planning hierarchy — the highlighted level is what this page optimises

S&OPYears
→
MPSMonths
→
MRPWeeks
→
CRPDays–Weeks
→
SFCHours–Days

The Problem

n jobs, m machines, same permutation on every machine

The shop has m machines in a fixed serial layout (M1 → M2 → … → Mm). Every one of the n jobs must be processed by all machines in that exact order. The distinguishing constraint of the permutation flow shop is that the job sequence on every machine is the same. A job cannot overtake another on a downstream machine. The decision is the permutation π; the objective is makespan.

Canonical applications include paint lines, semiconductor fabs, textile finishing, printing, and many flow-oriented batch processes. Variants cover additional constraints common in practice: no-wait (contiguous processing between machines, see steel production), blocking (no intermediate buffers), and sequence-dependent setup times (print shop). Johnson (1954) gave an O(n log n) optimal rule for m = 2; the general case is strongly NP-hard (Garey, Johnson & Sethi 1976).

Job M1 pj1 M2 pj2 M3 pj3 M4 pj4 M5 pj5
Makespan recurrence (given permutation π) C(π(1), 1) = p(π(1), 1)
C(π(1), i) = C(π(1), i−1) + p(π(1), i)    // i > 1
C(π(k), 1) = C(π(k−1), 1) + p(π(k), 1)    // k > 1
C(π(k), i) = max( C(π(k−1), i), C(π(k), i−1) ) + p(π(k), i)   // k, i > 1
min Cmax(π) = C(π(n), m)

For 10 jobs the search space is 10! = 3,628,800 permutations — brute force is still feasible as a ground truth, and is used in the solver below to verify heuristic solutions on the small scenario. For 20 jobs the space is ~2.43×1018; this is where NEH and iterated greedy earn their reputations. For the 50- and 100-job Taillard (1993) benchmarks, the best-known makespans are reached only by metaheuristics.

Manufacturing framework No-wait variant (steel) SDST variant (print shop)

Try It Yourself

Six algorithms compared on the same instance; click a row to inspect its Gantt

PFSP Scheduler

10 jobs · 5 machines · Fm | prmu | Cmax
Scenario
Small scenario: 6 jobs × 4 machines, 720 possible permutations. The brute-force optimum is computed and reported as a reference row so you can see exactly how close each heuristic comes.
Algorithm (select to inspect its Gantt)
Schedule (multi-machine Gantt)

Click “Solve & Compare” to run all six algorithms on the current scenario.

Comparison
Algorithm Cmax Gap vs best Time (ms)
Click Solve to run
Permutation detail (selected algorithm)
Select an algorithm above and click Solve to see the permutation and per-machine completion grid.
Reading the Gantt
The Gantt chart stacks m horizontal machine rows top-to-bottom. Job blocks are coloured by job index and flow diagonally down-right as each job moves through the machines. The same permutation drives all rows — you can read it off by following any machine row left-to-right. Green cells in the comparison table mark the minimum Cmax; on the small scenario an additional “brute-force optimum” row gives the ground truth.

The Algorithms

A 70-year lineage of flow-shop heuristics

Johnson’s Rule

Exact for m=2 O(n log n) F2 || Cmax

Partition the jobs into two sets A = {j : pj1 ≤ pj2} and B = {j : pj1 > pj2}. Sort A by increasing pj1 and B by decreasing pj2; schedule A followed by B. Provably optimal for the two-machine PFSP (Johnson 1954).

For m > 2 Johnson’s rule is no longer exact but is frequently applied to virtual two-machine reductions — see CDS below.

Palmer’s Slope Index

Heuristic O(nm + n log n) Fm | prmu | Cmax

Compute sj = Σi=1..m (2i − m − 1) · pji. Sort jobs by non-increasing slope index. Palmer (1965) is the earliest general-m flow-shop heuristic: jobs whose bulk of processing is concentrated on later machines are scheduled first so the pipeline fills smoothly.

CDS — Campbell-Dudek-Smith

Heuristic O(m · n log n) Fm | prmu | Cmax

For k = 1…m−1 construct a virtual two-machine instance: P1(j) = Σi=1..k pji, P2(j) = Σi=m−k+1..m pji. Apply Johnson’s rule to obtain a candidate sequence and evaluate its real-instance makespan. Return the best of the m−1 candidates (Campbell, Dudek & Smith 1970).

NEH — Nawaz-Enscore-Ham

State-of-the-art constructive O(n2 m) Fm | prmu | Cmax

Step 1: sort jobs by non-increasing total processing time Σi pji. Step 2: take the two longest jobs and keep the better of their two orderings. Step 3: for k = 3…n, insert job k into the best of k positions of the partial sequence.

Nawaz, Enscore & Ham (1983). Consistently the best-performing simple constructive heuristic on Taillard benchmarks; average gap to best-known is typically 3–5%. The insertion step alone captures most of NEH’s power and is the scaffold for every modern flow-shop metaheuristic.

Iterated Greedy (IG)

Metaheuristic · current SOTA O(iterations · n2 m) Fm | prmu | Cmax

Start from an NEH-constructed sequence. Each iteration: destruct (remove d random jobs, typically d = 4), construct (reinsert them one by one using NEH’s insertion step), local search (optional best-improvement insertion), accept via a simulated-annealing-like criterion.

Ruiz & Stuetzle (2007). The current de-facto state-of-the-art on Taillard benchmarks. Simple to implement, extremely effective in practice. This page runs 120 iterations as a live demo; serious runs use 104–106 iterations with restart and fine-tuned acceptance.

Random Permutation

Baseline O(n) Fm | prmu | Cmax

Shuffle the jobs uniformly at random. The baseline that all other heuristics should beat. On Taillard-class instances the expected gap from random permutation to NEH is typically 15–30%, making it a useful reality check.

PFSP historical note
Flow shops are the original OR scheduling problem — Johnson (1954) pre-dates computational complexity theory by two decades. The field’s evolution reads as a greatest-hits catalogue of combinatorial optimisation: exact dynamic programming (Held-Karp-flavoured), specialised branch-and-bound with Taillard bounds (1993), the constructive heuristic pantheon of the 1960s–1980s (Palmer, CDS, Gupta, Dannenbring, NEH), tabu search (Nowicki & Smutnicki 1996), genetic algorithms (Reeves 1995), ant colony (Stützle 1998), and the current state of the art, iterated greedy (Ruiz & Stuetzle 2007) and its successors including ML-augmented dispatch rules.

References

Foundational papers on the permutation flow-shop

  • Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68. — foundational two-machine rule.
  • Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time — a quick method of obtaining a near optimum. OR Quarterly, 16(1), 101–107. — slope index.
  • Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management Science, 16(10), B630–B637. doi:10.1287/mnsc.16.10.B630 — CDS.
  • Gupta, J. N. D. (1971). A functional heuristic algorithm for the flow-shop scheduling problem. OR Quarterly, 22(1), 39–47.
  • Dannenbring, D. G. (1977). An evaluation of flow shop sequencing heuristics. Management Science, 23(11), 1174–1182. doi:10.1287/mnsc.23.11.1174
  • Nawaz, M., Enscore, E. E. Jr., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. doi:10.1016/0305-0483(83)90088-9 — NEH.
  • Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285. doi:10.1016/0377-2217(93)90182-M — Taillard benchmarks.
  • Nowicki, E., & Smutnicki, C. (1996). A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91(1), 160–175. doi:10.1016/0377-2217(95)00037-2
  • Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479–494. doi:10.1016/j.ejor.2004.04.017
  • Ruiz, R., & Stuetzle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049. doi:10.1016/j.ejor.2005.12.009 — iterated greedy SOTA.
  • Framinan, J. M., Leisten, R., & Ruiz García, R. (2014). Manufacturing Scheduling Systems. Springer. doi:10.1007/978-1-4471-6272-8
  • Pinedo, M. L. (2022). Scheduling: Theory, Algorithms, and Systems (6th ed.). Springer. doi:10.1007/978-3-031-05921-6

Need to sequence
a multi-machine production line?

Get in Touch
Disclaimer
Processing-time matrices are synthetic instances drawn from the Taillard distribution, not real production data. The browser solver runs NEH, CDS, Palmer, Johnson (on the two-machine reduction), random baseline, and a short 120-iteration iterated greedy; serious deployment uses commercial solvers (Gurobi, CPLEX, OR-Tools CP-SAT) or long-horizon metaheuristics with restarts.
Manufacturing