Job Shop Scheduling
JSSP — Disjunctive Programming / NP-Hard
A general job shop with 3 machines must schedule 4 jobs, each requiring operations in a job-specific order. Every hour of excess makespan costs €800–€2,000 in delayed shipments. The JSSP is NP-hard for ≥2 machines — among the hardest combinatorial problems known.
Where This Decision Fits
Manufacturing decision chain — the highlighted step is what this page optimizes
The Problem
Scheduling 4 jobs with 12 operations across 3 machines
A job shop operates 3 machines (M1, M2, M3) and must process 4 jobs. Each job consists of 3 operations that must be executed in a fixed, job-specific order (routing). Unlike flow shops, different jobs may visit machines in different sequences — Job 1 might require M1 → M2 → M3 while Job 2 requires M2 → M3 → M1.
The scheduler must decide the sequence of operations on each machine to minimize the overall makespan Cmax (completion time of the last operation). This is modelled with disjunctive constraints: for any two operations assigned to the same machine, one must precede the other — creating a massive combinatorial search space.
| Job | Op 1 | Op 2 | Op 3 |
|---|---|---|---|
| J1 | M1 (3) | M2 (4) | M3 (2) |
| J2 | M2 (2) | M3 (3) | M1 (4) |
| J3 | M3 (3) | M1 (2) | M2 (5) |
| J4 | M1 (4) | M3 (3) | M2 (2) |
subject to
sij + pij ≤ si,j+1 // precedence: op j of job i finishes before op j+1 starts
sij + pij ≤ skl ∨ skl + pkl ≤ sij // disjunctive: no two ops overlap on same machine
Cmax ≥ sij + pij // makespan ≥ every completion time
sij ≥ 0 // non-negative start times
With 4 jobs and 3 machines, there are (4!)3 = 13,824 possible machine sequences. For the classic 10×10 FT10 benchmark, the search space exceeds 1065. This combinatorial explosion is why JSSP has driven decades of research in heuristics, metaheuristics, and exact methods.
See full Manufacturing optimizationTry It Yourself
Sequence operations on machines to minimize makespan
JSSP Scheduler
4 Jobs · 12 Ops · 3 MachinesReady. Select a scenario and click “Solve & Compare All Algorithms”.
| Algorithm | Makespan | M1 Util | M2 Util | M3 Util | Idle |
|---|---|---|---|---|---|
| Click Solve to run | |||||
The Algorithms
Three approaches to job shop scheduling
Random Sequence
Baseline O(n)Randomly order operations on each machine while respecting job precedence constraints. Serves as a lower-bound baseline for comparison. Produces valid but generally poor schedules with large makespans and uneven machine utilisation.
SPT Dispatch (Shortest Processing Time)
Heuristic O(n log n)At each decision point, schedule the ready operation with the shortest processing time on its designated machine. This greedy priority rule reduces average flow time and often produces competitive makespans. Widely used in real shops due to its simplicity and robustness.
Shifting Bottleneck
Heuristic O(m · n2)Iteratively identifies the bottleneck machine (the one causing the largest increase in makespan), optimally sequences operations on that machine, then re-optimizes previously scheduled machines. This decomposition-based approach, introduced by Adams, Balas & Zawack (1988), consistently produces near-optimal solutions on classical benchmarks.
Computational Complexity
- JSSP is NP-hard for ≥ 2 machines (Garey & Johnson, 1979)
- With n jobs and m machines: (n!)m possible schedules to evaluate
- The 10×10 FT10 instance (Fisher & Thompson, 1963) remained unsolved for 26 years
- Exact methods (branch & bound, constraint programming) handle up to ~20×15 instances
- State-of-the-art metaheuristics (tabu search, genetic algorithms) solve 50×20 instances within 1% of optimality
References
Academic foundations
- (1988). The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34(3), 391–401.
- (1969). Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm. Operations Research, 17(6), 941–957.
Explore More Applications
This demo is part of a comprehensive mathematical modeling and operations research toolkit covering scheduling, routing, packing, network optimization, and stochastic models.