Problem Family
Scheduling Problems
The largest problem family in the repository, covering the full spectrum of deterministic scheduling theory. From single machine dispatching rules to multi-stage flow shops and resource-constrained project scheduling, each problem features exact methods, constructive heuristics, and state-of-the-art metaheuristics.
View Source CodePermutation Flow Shop
All n jobs must be processed on m machines in the same fixed order. The objective is to find the job permutation that minimizes the makespan — the completion time of the last job on the last machine. The most extensively studied scheduling problem in the literature, with the Taillard benchmark suite (120 instances, 20–500 jobs) serving as the standard evaluation framework.
s.t. Cπ(j),k = max(Cπ(j),k-1, Cπ(j-1),k) + pπ(j),k
Cπ(0),k = Cπ(j),0 = 0 (boundary conditions)
π ∈ Π(n) (permutation of n jobs)
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Johnson's Rule (F2||Cmax) | Exact | O(n log n) | Johnson (1954), exact for 2 machines |
| MIP (HiGHS + CP-SAT) | Exact | Exponential | Position-based formulation |
| Branch & Bound | Exact | Exponential | Taillard LB (1993), NEH warm-start |
| Palmer's Slope Index | Heuristic | O(nm + n log n) | Palmer (1965) |
| Gupta's Algorithm | Heuristic | O(nm + n log n) | Gupta (1971) |
| Dannenbring's Rapid Access | Heuristic | O(nm + n log n) | Dannenbring (1977) |
| CDS | Heuristic | O(m · n log n) | Campbell, Dudek & Smith (1970) |
| NEH | Heuristic | O(n² · m) | Nawaz et al. (1983), Taillard accel. (1990) |
| LR Heuristic | Heuristic | O(n³ · m) | Liu & Reeves (2001) |
| Local Search (VND) | Varies | Swap, insertion, Or-opt | |
| Simulated Annealing | Varies | Osman & Potts (1989) | |
| Genetic Algorithm | Varies | Reeves (1995) | |
| Tabu Search | Varies | Nowicki & Smutnicki (1996) | |
| Ant Colony Optimization | Varies | Stützle (1998) | |
| Iterated Greedy | Varies | Ruiz & Stützle (2007) |
Two-machine LB: For each pair (k, k′), solve the induced F2||Cmax sub-problem optimally via Johnson's Rule. The maximum over all pairs is a stronger bound.
Dominance properties: A partial permutation π dominates π′ if Cπ(j),k ≤ Cπ′(j),k for all j, k. Dominated partial sequences can be pruned in Branch & Bound without loss of optimality. NEH's insertion step implicitly exploits a weaker form: it evaluates all positions and keeps only the best, acting as a greedy dominance filter.
Try It Yourself — curated demo subset
| Algorithm | Makespan | Time | Gap |
|---|
Parallel Machine Scheduling
Assign n jobs to m parallel machines to minimize makespan. Three machine environments are supported: identical machines (Pm) where all have equal speed, uniform machines (Qm) where machine i has speed si, and unrelated machines (Rm) where processing time depends on both job and machine. Even the simplest case P2||Cmax is NP-hard, as it reduces to the PARTITION problem.
s.t. each job assigned to exactly one machine
M1 ∪ M2 ∪ ... ∪ Mm = {1,...,n}, Mi ∩ Mj = ∅
Variants Qm (uniform): processing time = pj / si on machine i with speed si
Rm (unrelated): processing time = pij, arbitrary per job-machine pair
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| MIP (HiGHS) | Exact | Exponential | Assignment-based formulation |
| LPT | Heuristic | O(n log n) | Graham (1969), 4/3−1/(3m) approx for Pm||Cmax |
| SPT | Exact | O(n log n) | Optimal for Pm||ΣCj (different objective) |
| MULTIFIT | Heuristic | O(n log n · k) | Coffman, Garey & Johnson (1978) |
| List Scheduling | Heuristic | O(n log m) | Graham (1966), 2−1/m approx for Pm||Cmax |
| Genetic Algorithm | Varies | Integer-vector encoding |
Try It Yourself — P2||Cmax demo
| Algorithm | Makespan | Load M1 | Load M2 | Time |
|---|
LPT Approximation Guarantee
For P2||Cmax, LPT produces schedules within 7/6 of optimal. The 4/3−1/(3m) bound holds for general Pm.
Single Machine Scheduling
Process n jobs on a single machine, where the schedule is fully determined by the processing order. This family spans a rich complexity landscape: some objectives admit optimal polynomial-time dispatching rules (SPT for ΣCj, EDD for Lmax), while others like weighted tardiness ΣwjTj are strongly NP-hard. The single machine setting is foundational to scheduling theory and serves as a building block for multi-machine problems.
NP-Hard Objectives 1 || ΣTj → Subset DP, O(2n · n), n ≤ 20
1 || ΣwjTj → Branch & Bound with ATC warm-start
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| SPT / WSPT / EDD | Exact | O(n log n) | Conway (1967), Smith (1956), Jackson (1955) |
| Moore's Algorithm | Exact | O(n log n) | Moore (1968) |
| Subset DP (Bitmask) | Exact | O(2n · n) | Held-Karp style enumeration, n ≤ 20 |
| Branch & Bound | Exact | Exponential | Potts & Van Wassenhove (1985) |
| ATC (Apparent Tardiness Cost) | Heuristic | O(n²) | Composite dispatching rule |
| Simulated Annealing | Varies | Swap/insertion for ΣwjTj |
Try It Yourself
Job Shop Scheduling
Each of n jobs consists of a sequence of operations on specific machines, where different jobs may visit machines in different orders. The disjunctive graph model (Roy & Sussmann, 1964) is the central representation: conjunctive arcs encode job precedence, and disjunctive arcs encode machine conflicts. The legendary ft10 instance (10 jobs, 10 machines) remained unsolved for over 25 years (1963–1989), illustrating the extreme difficulty of this problem class. Modern constraint programming solvers (e.g., CP-SAT, IBM CP Optimizer) are now the state-of-the-art exact approach for industrial-size JSP instances.
V = operations, C = conjunctive (job order), D = disjunctive (machine conflicts)
Cmax = longest path in the resolved disjunctive graph (critical path)
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Dispatching Rules (SPT/LPT/MWR/LWR/FIFO) | Heuristic | O(n·m) | G&T active schedule framework (1960) |
| Shifting Bottleneck | Heuristic | O(m² · n²) | Adams, Balas & Zawack (1988) |
| Simulated Annealing | Varies | Van Laarhoven et al. (1992) | |
| Tabu Search | Varies | Nowicki & Smutnicki (1996) |
Try It Yourself
| Algorithm | Makespan | Time |
|---|
Flexible Job Shop Scheduling
Extends the classical Job Shop by allowing each operation to be processed on any machine from a set of eligible machines. This introduces a routing sub-problem (machine assignment) in addition to the sequencing sub-problem. Total FJSP allows all machines for every operation; Partial FJSP restricts each operation to a subset. The integrated routing-and-sequencing nature makes FJSP significantly harder than standard JSP. As with JSP, constraint programming (CP-SAT) is increasingly used for exact solutions on moderate-size instances.
Sequencing: πk (operation order on each machine k)
Objective: min Cmax
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Dispatching Rules (SPT/LPT/MWR/LWR + ECT/SPT) | Heuristic | O(n·m) | Priority + machine selection |
| Hierarchical Decomposition | Heuristic | O(n·m²) | Brandimarte (1993) |
| Genetic Algorithm (Pezzella-style) | Varies | Pezzella et al. (2008) |
Mastrolilli & Gambardella (2000) — Effective neighbourhood functions for the FJSP via tabu search.
Benchmark suites: Brandimarte (1993) — 10 instances; Kacem et al. (2002) — 4 instances (widely used for FJSP evaluation).
Resource-Constrained Project Scheduling
Schedule n activities with precedence constraints and renewable resource requirements to minimize the project duration. Activities 0 (source) and n+1 (sink) are dummies. The problem is strongly NP-hard even with only 1 renewable resource type (Blazewicz, Lenstra & Rinnooy Kan, 1983). Schedule Generation Schemes (SGS) decode priority lists into feasible schedules: Serial SGS generates active schedules; Parallel SGS generates non-delay schedules. The PSPLIB benchmark library is the standard test bed for RCPSP algorithms.
s.t. Sj ≥ Si + pi ∀(i,j) ∈ E (precedence)
Σj ∈ A(t) rjk ≤ Rk ∀k, ∀t (resource capacity)
where A(t) = {j : Sj ≤ t < Sj + pj} is the set of activities in progress at time t
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Serial SGS (LFT / EST / MTS / GRPW) | Heuristic | O(n² · K) | Kolisch (1996) |
| Parallel SGS | Heuristic | O(n² · K) | Non-delay schedules |
| Genetic Algorithm | Varies | Hartmann (1998) |
Try It Yourself — Serial SGS demo
| Priority Rule | Makespan | Schedule | Time |
|---|
How Serial SGS Works
At each step, the Serial SGS selects the highest-priority eligible activity (all predecessors finished) and schedules it at the earliest time where both precedence and resource constraints are satisfied.
Flow Shop Variants
Three extensions of the permutation flow shop with additional real-world constraints
No-Wait Flow Shop
Jobs cannot wait between consecutive machines — processing must be contiguous across all stages. Reduces to an asymmetric TSP on the inter-job delay matrix: the delay D[i][j] gives the minimum start-to-start gap between jobs i and j, so finding the optimal sequence is equivalent to finding the shortest Hamiltonian path. Critical in industries where material cannot idle between processes without quality degradation.
Blocking Flow Shop
No intermediate buffers between machines — a completed job blocks its machine until the downstream machine is available. Uses departure time recursion instead of standard completion times. Models manufacturing environments with zero buffer capacity.
Sequence-Dependent Setup Times
Setup times depend on both the current and preceding job on each machine. Models real-world changeover times that vary by product sequence. The setup matrix adds an additional combinatorial dimension to the already NP-hard base problem.
Notation & Glossary
Graham et al. (1979) α | β | γ classification and key symbols
β — Job constraints: prmu (permutation), prec (precedence), rj (release dates), dj (due dates), no-wait, blocking, Ssd (sequence-dependent setup)
γ — Objective: Cmax (makespan), ΣCj (total completion), ΣwjCj (weighted completion), Lmax (max lateness), ΣTj (total tardiness), ΣUj (number of late jobs)
| Symbol | Meaning | Context |
|---|---|---|
| π | Job permutation (sequence) | PFSP, Single Machine |
| Π(n) | Set of all permutations of n elements | PFSP formulation |
| pj, pij, pπ(j),k | Processing time of job j (on machine i or k) | All problems |
| Cj, Cmax | Completion time of job j; makespan (max completion) | All problems |
| Tj = max(0, Cj − dj) | Tardiness of job j | Single Machine |
| Lmax = max(Cj − dj) | Maximum lateness | Single Machine |
| Uj | 1 if job j is late (Cj > dj), 0 otherwise | Single Machine |
| wj | Weight (priority) of job j | Weighted objectives |
| Mi | Set of jobs assigned to machine i | Parallel Machine |
| si | Speed of machine i | Uniform Parallel (Qm) |
| σij | Machine assigned to operation Oij | FJSP routing |
| Sj | Start time of activity j | RCPSP |
| A(t) | Set of activities in progress at time t | RCPSP resources |
| rjk, Rk | Resource requirement of activity j for type k; capacity of type k | RCPSP |
| D[i][j] | Delay matrix: minimum start-to-start gap between jobs i and j | No-Wait Flow Shop |
Complexity Comparison
How the six scheduling families compare in difficulty, structure, and solution approaches
Why Do These Problems Differ in Difficulty?
Single Machine is the foundation: one processor, one sequence, no routing. Some objectives (like ΣCj) yield to simple sorting rules, while others (like ΣwjTj) are strongly NP-hard — the complexity comes entirely from the objective function.
Parallel Machine adds an assignment dimension: which job goes to which machine? Even the simplest case (P2||Cmax) is NP-hard because it encodes the PARTITION problem — balancing two machine loads is equivalent to partitioning integers into two equal-sum subsets.
Flow Shop forces all jobs through the same machine sequence, creating interference between jobs waiting for the same machine. For 2 machines, Johnson's Rule exploits a special structure; for m ≥ 3, the interference patterns become combinatorially explosive (strongly NP-hard).
Job Shop removes the fixed-route constraint: each job has its own machine order. This creates disjunctive conflicts — pairs of operations competing for the same machine that must be resolved in one direction or the other. The solution space grows as O((n!)m), and even 2-machine JSP is NP-hard. The ft10 instance's 25+ year resistance to exact solution illustrates the combinatorial explosion.
Flexible Job Shop layers a routing decision on top of JSP's sequencing: each operation can go to multiple eligible machines. This creates a joint optimization over machine assignment and operation ordering — the search space is exponentially larger than JSP's.
RCPSP generalizes further by replacing machine constraints with renewable resource budgets and adding precedence constraints (a DAG). Activities compete for limited resources at each time step, making even 1-resource RCPSP strongly NP-hard.
| Family | Notation | Complexity | Key Decision | Best Exact | Best Heuristic | Benchmarks |
|---|---|---|---|---|---|---|
| Single Machine | 1 | β | γ | P to strongly NP-h | Sequence only | DP / B&B | SPT, EDD, ATC | — |
| Parallel Machine | Pm | | Cmax | NP-hard (P2||Cmax) | Job → machine | MIP | LPT, MULTIFIT | — |
| Flow Shop | Fm | prmu | Cmax | Str. NP-h (m≥3) | Permutation | B&B / MIP | NEH, IG | Taillard (120) |
| Job Shop | Jm | | Cmax | NP-hard (J2||Cmax) | Machine orderings | CP-SAT / B&B | Shifting Btlnk, TS | ft, LA, ABZ, ORB |
| Flexible Job Shop | FJm | | Cmax | NP-hard | Route + sequence | CP-SAT | GA, Hierarchical | Brandimarte, Kacem |
| RCPSP | PS | prec | Cmax | Str. NP-h (1 res.) | Priority + timing | B&B / SAT | SGS + GA | PSPLIB |
↓ add machines
P2 | | Cmax (NP-hard, reduces from PARTITION)
↓ force routing order
F3 | prmu | Cmax (strongly NP-hard)
↓ allow job-specific routes
J2 | | Cmax (NP-hard)
↓ allow machine flexibility
FJ | | Cmax (NP-hard, generalizes JSP)
↓ add resource constraints + precedence
PS | prec | Cmax (strongly NP-hard, 1 resource type)
Key References
Foundational works in scheduling theory and computation
Notation & Classification
Graham, R.L., Lawler, E.L., Lenstra, J.K. & Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.
Textbooks
Pinedo, M.L. (2016). Scheduling: Theory, Algorithms, and Systems. 5th ed., Springer.
Brucker, P. (2007). Scheduling Algorithms. 5th ed., Springer.
Flow Shop
Johnson, S.M. (1954). Optimal two- and three-stage production schedules. Naval Research Logistics.
Nawaz, M., Enscore, E.E. & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. EJOR, 47(1), 65–74.
Taillard, E. (1993). Benchmarks for basic scheduling problems. EJOR, 64(2), 278–285.
Ruiz, R. & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the PFSP. EJOR, 177(3), 2033–2049.
Job Shop & FJSP
Adams, J., Balas, E. & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391–401.
Nowicki, E. & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797–813.
Pezzella, F., Morganti, G. & Ciaschetti, G. (2008). A genetic algorithm for the FJSP. Computers & OR, 35(10), 3202–3212.
RCPSP
Blazewicz, J., Lenstra, J.K. & Rinnooy Kan, A.H.G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1), 11–24.
Kolisch, R. & Sprecher, A. (1996). PSPLIB — A project scheduling problem library. EJOR, 96(1), 205–216.
Hartmann, S. (1998). A competitive genetic algorithm for RCPSP. Naval Research Logistics, 45(7), 733–750.
Complexity
Lenstra, J.K., Rinnooy Kan, A.H.G. & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Explore the full repository with 57 problems across 10 families