🧩 Constraint Solving POTD:Flow-Shop Scheduling

[github-actions[bot]]

Category: Scheduling | Date: 2026-04-15

All machines, all jobs, same order — how fast can you finish?

---

Problem Statement

In the Flow-Shop Scheduling problem you have n jobs and m machines. Every job must be processed on every machine in the same fixed order (machine 1 → machine 2 → ... → machine m). Each job j has a processing time p[j][i] on machine i. No machine can process more than one job at a time, and once a job starts on a machine it cannot be interrupted (no preemption). The goal is to find an ordering of jobs that minimises the makespan — the time at which the last job finishes on the last machine.

Concrete Instance (3 machines, 4 jobs)

Job	Machine 1	Machine 2	Machine 3
A	3	2	5
B	5	4	1
C	2	6	4
D	4	3	2

Input: processing times p[j][i] for each job j and machine i.
Output: a permutation of jobs (the same permutation is used on every machine) that minimises the makespan C_max.

Key property: unlike Job-Shop scheduling, the job ordering decision can be encoded as a single permutation — all machines process jobs in the same sequence. This makes the problem structurally richer than it first appears (it is still NP-hard for m ≥ 3).

---

Why It Matters

• Manufacturing & assembly lines. Printed circuit board assembly, automotive paint shops, and textile production all run jobs through a sequence of stations in a fixed order. Shaving minutes off the schedule compounds into significant throughput gains at scale.
• Data centre batch pipelines. Multi-stage ETL workflows (extract → transform → load) pass tasks through fixed pipeline stages; minimising total pipeline completion time reduces SLA violations.
• Compiler/HPC job queues. High-performance computing centres submit multi-phase jobs (compile → link → simulate) through a fixed set of node types — flow-shop models map directly onto queue scheduling policies.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:

• start[j][i] ∈ [0..UB] — start time of job j on machine i
• rank[j] ∈ {0..n-1} — position of job j in the permutation
  (all machines share the same ordering)

Core constraints:

// Precedence within a job (technology order)
start[j][i+1] >= start[j][i] + p[j][i]   ∀ j, i

// Machine capacity: no two jobs overlap on the same machine
// captured by a NoOverlap / Disjunctive global constraint per machine
NoOverlap({ interval(start[j][i], p[j][i]) | j ∈ Jobs })  ∀ i

// Permutation consistency: if rank[j1] < rank[j2]
//   then job j1 starts before j2 on every machine
rank[j1] < rank[j2] → start[j2][i] >= start[j1][i] + p[j1][i]  ∀ i, j1≠j2

AllDifferent(rank)
```

**Objective:** `minimise C_max = max_j ( start[j][m-1] + p[j][m-1] )`

*Trade-offs:* The `NoOverlap` / `Disjunctive` global constraint enables powerful **Edge-Finding** and **Not-First/Not-Last** propagation. CP handles the combinatorial structure elegantly and can prove optimality on moderately-sized instances. Scaling to hundreds of jobs requires aggressive symmetry breaking and good search heuristics.

---

#### Approach 2 — Mixed Integer Programming (MIP)

Use **positional assignment variables** (the classic Manne/Wagner formulation):

**Decision variables:**
- `x[j][k]` ∈ `{0,1}` — job `j` is placed in position `k`
- `C[k][i]` ∈ `R≥0` — completion time of the job in position `k` on machine `i`

**Constraints:**
```
// Assignment: each job to exactly one position, each position one job
∑_k x[j][k] = 1   ∀ j
∑_j x[j][k] = 1   ∀ k

// Completion time recurrence
C[k][i] >= C[k-1][i] + ∑_j x[j][k] * p[j][i]   ∀ k>1, i   (same machine, next job)
C[k][i] >= C[k][i-1] + ∑_j x[j][k] * p[j][i]   ∀ k, i>1   (same job, next machine)

C_max >= C[n][m]

Objective: minimise C_max

Trade-offs: The LP relaxation provides strong lower bounds exploitable in branch-and-bound. However, the formulation grows as O(n2 + n·m) binary variables and the big-M coefficients in linearised products can weaken LP bounds. MIP solvers like Gurobi/CPLEX excel when the LP bound is tight; CP typically outperforms on purely combinatorial instances.

Example Model (OR-Tools CP-SAT, Python)

from ortools.sat.python import cp_model

def solve_flowshop(p):
    """p[j][i] = processing time of job j on machine i."""
    n, m = len(p), len(p[0])
    model = cp_model.CpModel()
    horizon = sum(p[j][i] for j in range(n) for i in range(m))

    # Interval variables
    start = [[model.NewIntVar(0, horizon, f's_{j}_{i}') for i in range(m)] for j in range(n)]
    end   = [[model.NewIntVar(0, horizon, f'e_{j}_{i}') for i in range(m)] for j in range(n)]
    ivars = [[model.NewIntervalVar(start[j][i], p[j][i], end[j][i], f'iv_{j}_{i}')
              for i in range(m)] for j in range(n)]

    # Technology order within each job
    for j in range(n):
        for i in range(m - 1):
            model.Add(start[j][i + 1] >= end[j][i])

    # No overlap on each machine
    for i in range(m):
        model.AddNoOverlap([ivars[j][i] for j in range(n)])

    # Makespan
    makespan = model.NewIntVar(0, horizon, 'makespan')
    model.AddMaxEquality(makespan, [end[j][m - 1] for j in range(n)])
    model.Minimize(makespan)

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30.0
    status = solver.Solve(model)
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f'Makespan = {solver.Value(makespan)}')
        for j in range(n):
            print(f'  Job {j}: ' + ', '.join(
                f'M{i}@{solver.Value(start[j][i])}' for i in range(m)))

---

Key Techniques

1. Johnson's Algorithm (m = 2 special case)

For two machines, S. M. Johnson's 1954 algorithm finds the optimal permutation in O(n log n). It partitions jobs by whether p[j][1] ≤ p[j][2] and sequences them accordingly. Understanding Johnson's rule builds intuition for why permutation structure matters and motivates NEH (see below) as a greedy heuristic.

2. NEH Heuristic + Iterated Local Search

The Nawaz-Enscore-Ham (NEH) heuristic inserts jobs in decreasing order of total processing time into the best position found so far. It typically finds solutions within 2–5 % of optimum in milliseconds. For CP/MIP, NEH provides an excellent initial upper bound that tightens the search immediately. Wrapping NEH inside an iterated local search (random restart after local optimum) scales to thousands of jobs while maintaining quality.

3. Edge-Finding & Energetic Reasoning

Within CP, the Disjunctive / CumulativeConstraint propagators use edge-finding: given an interval, determine whether it must be scheduled before or after a set of other intervals based on energy arguments. For flow-shop, this prunes large portions of the search tree without branching — often reducing solve time by orders of magnitude compared to a naïve model.

4. Symmetry Breaking

If all processing times are equal for some jobs, permuting those jobs yields identical makespans. Adding lex-order constraints (rank[j1] < rank[j2] for symmetric job pairs) prunes symmetric branches without losing any optimal solution.

---

Challenge Corner

The no-wait flow-shop variant forbids any idle time between a job's consecutive operations — once job j finishes on machine i, it must start immediately on machine i+1 (e.g., hot-metal processing where cooling is prohibited).

Challenge: How would you modify the CP model above to enforce the no-wait constraint? Does the permutation structure still hold? Can Johnson's algorithm be adapted for the no-wait two-machine case?

Bonus: The blocking flow-shop goes further — a machine cannot start the next job until the current job has moved to the next machine (no buffer between machines). How does this change the energy argument in edge-finding?

---

References

1. Johnson, S. M. (1954). "Optimal two- and three-stage production schedules with setup times included." Naval Research Logistics Quarterly, 1(1), 61–68. — The foundational result; still the cleanest example of a greedy optimality proof.

2. 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. — Introduced the NEH heuristic; a must-read for practitioners.

3. Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer. — Chapters 4–6 give a comprehensive treatment of flow-shop variants, exact methods, and approximations.

4. Vilím, P. (2007). "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)." CP 2007, LNCS 4741. — The canonical reference for edge-finding propagation used in modern CP solvers.

Generated by Constraint Solving — Problem of the Day · ● 368.7K · ◷

• expires on Apr 22, 2026, 12:57 PM UTC