Flexible Job Shop Scheduling
FJSP — Two-Stage Heuristic / NP-Hard
A flexible manufacturing cell allows each operation to be processed on alternative machines. The scheduler must simultaneously decide machine assignment and operation sequence. FJSP extends JSSP with machine flexibility, reducing makespan by 10–25% but increasing problem complexity.
Where This Decision Fits
Manufacturing decision chain — the highlighted step is what this page optimizes
The Problem
Scheduling 3 jobs with 7 operations across 3 machines
A flexible manufacturing cell operates 3 machines (M1, M2, M3) to process 3 jobs. Each job has 2–3 operations that must be executed in a fixed sequence. However, each operation can be processed on one or more eligible machines — this is the flexibility that distinguishes FJSP from classical Job Shop Scheduling.
The scheduler faces a two-stage decision: first, assign each operation to one of its eligible machines; then, sequence all operations on each machine to minimize the overall makespan (completion time of the last operation). Processing times vary by machine, so assignment choices directly affect total schedule length.
| Job | Operation | M1 (time) | M2 (time) | M3 (time) | Eligible |
|---|---|---|---|---|---|
| J1 | Op 1.1 | 4 | 6 | — | M1, M2 |
| J1 | Op 1.2 | — | 5 | 3 | M2, M3 |
| J1 | Op 1.3 | 7 | 4 | 5 | M1, M2, M3 |
| J2 | Op 2.1 | 3 | — | 5 | M1, M3 |
| J2 | Op 2.2 | 6 | 4 | 4 | M1, M2, M3 |
| J3 | Op 3.1 | 5 | 3 | 6 | M1, M2, M3 |
| J3 | Op 3.2 | — | 7 | 4 | M2, M3 |
subject to
Σk ∈ Mij xijk = 1 // each op assigned to exactly one eligible machine
sij + pijk ≤ si,j+1 // precedence within job i
sij + pijk ≤ si'j' ∨ si'j' + pi'j'k ≤ sij // no overlap on machine k
Cmax ≥ sij + pijk // makespan definition
xijk ∈ {0, 1}, sij ≥ 0
With 7 operations and up to 3 eligible machines each, the assignment space alone is 37 = 2,187 possible machine assignments, each producing a different sequencing subproblem. For real-world cells with 50+ operations, exact methods become intractable, motivating the two-stage heuristic approach demonstrated below.
See full Manufacturing optimizationTry It Yourself
Assign operations to machines and sequence them
FJSP Scheduler
3 Jobs · 7 Ops · 3 MachinesReady. Select a scenario and click “Solve & Compare All Algorithms”.
| Algorithm | Makespan | M1 Util | M2 Util | M3 Util | Time |
|---|---|---|---|---|---|
| Click Solve to run | |||||
The Algorithms
Three heuristics for flexible job shop scheduling
Random Assignment + SPT
Heuristic O(n)Randomly assign each operation to one of its eligible machines, then schedule operations on each machine using Shortest Processing Time (SPT) order. Fast baseline but ignores workload balance, often producing lopsided schedules with high makespan.
Global Workload + SPT
Heuristic O(n · m)For each operation, assign it to the eligible machine with the lowest total assigned workload so far. This greedy load-balancing strategy distributes work evenly across machines. Operations on each machine are then sequenced by SPT. Produces well-balanced schedules with near-optimal makespan.
Local Workload + LPT
Heuristic O(n · m)Assign each operation to the eligible machine where it has the shortest processing time (local optimum). Sequence operations on each machine using Longest Processing Time (LPT) first. This greedy approach minimises individual operation times but may create bottlenecks on the fastest machine.
Computational Complexity
- FJSP is NP-hard — it generalises the classical Job Shop Scheduling Problem (JSSP)
- JSSP itself is NP-hard; adding machine flexibility creates an additional combinatorial layer
- With n operations and m machines: up to mn possible assignments, each requiring sequencing
- Exact methods (MIP, constraint programming) handle ~20 operations; real cells need heuristics or metaheuristics
- State-of-the-art: genetic algorithms and adaptive neighbourhood search achieve near-optimal on benchmarks
References
Academic foundations
- (1990). Job-Shop Scheduling with Multi-Purpose Machines. Computing, 45(4), 369–375.
- (2002). Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems. IEEE Trans. Systems, Man, and Cybernetics, Part C, 32(1), 1–13.
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.