🧩 Constraint Solving POTD:Flow-Shop Scheduling

[github-actions[bot]]

Flow-shop scheduling is one of the most studied problems in combinatorial optimization — a clean, structured variant of job-shop scheduling that appears constantly in real manufacturing and processing pipelines. Today we explore how to model and solve it with constraint programming and mixed-integer programming.

---

Problem Statement

You have n jobs and m machines. Every job must be processed on every machine, and crucially, all jobs follow the same machine order: machine 1 → machine 2 → … → machine m.

Each job j has a processing time p[j][i] on machine i. A job cannot start on machine i+1 until it finishes on machine i. Each machine can handle at most one job at a time. The goal is to minimize the makespan (the time when the last job finishes).

Concrete Instance (3 Jobs × 3 Machines)

Job	Machine 1	Machine 2	Machine 3
J1	3	2	2
J2	2	3	4
J3	4	1	3

Question: In what order should the jobs be processed on each machine to minimize the total completion time?

Optimal sequence: J1 → J3 → J2, achieving makespan 14.

Key distinction from job-shop: In flow-shop, the routing (machine order) is identical for every job. In the permutation flow-shop variant (most commonly studied), all machines process jobs in the same sequence.

---

Why It Matters

• Electronics manufacturing: Printed circuit board (PCB) assembly lines where boards pass through soldering, inspection, and testing stations in a fixed order — optimizing throughput directly reduces cycle time.
• Pharmaceutical production: Drug synthesis pipelines where batches move through reaction, filtration, and packaging stages, with tight scheduling reducing idle equipment time and improving on-time delivery.
• Data pipelines and cloud computing: Multi-stage ETL or inference jobs on heterogeneous processor types follow fixed stage ordering; flow-shop models help minimize total latency.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

The natural CP model uses start time variables and disjunctive/cumulative constraints.

Decision variables:

• S[j][i] = start time of job j on machine i (integer, ≥ 0)

Constraints:

1. Technological order (precedence within a job):
   S[j][i+1] ≥ S[j][i] + p[j][i] for all j, i < m

2. Machine disjunctiveness (no overlap on any machine):
   For each machine i and each pair of jobs j ≠ k:
   S[j][i] + p[j][i] ≤ S[k][i] OR S[k][i] + p[k][i] ≤ S[j][i]

3. Permutation symmetry (optional, permutation flow-shop):
   All machines process jobs in the same order — can encode with a single permutation variable π and link S[j][i] accordingly.

Objective: Minimize max_j { S[j][m] + p[j][m] }

Trade-offs: CP handles the disjunctive constraints naturally via the NoOverlap global constraint (strong propagation). Adding the permutation structure as a global constraint significantly reduces the search space from (n!)^m to n!.

---

Approach 2: Mixed-Integer Programming (MIP)

The classic MIP formulation introduces binary sequencing variables.

Decision variables:

• S[j][i] = start time of job j on machine i (continuous)
• x[j][k] = 1 if job j is scheduled before job k on all machines, 0 otherwise (binary)

Constraints:

1. Technological order (same as CP):
   S[j][i+1] ≥ S[j][i] + p[j][i]

2. Machine capacity (Big-M disjunction):
   S[j][i] + p[j][i] ≤ S[k][i] + M·(1 - x[j][k])
S[k][i] + p[k][i] ≤ S[j][i] + M·x[j][k]
   for all j < k, all machines i

3. Ordering consistency (permutation flow-shop):
   x[j][k] is identical across all machines i — only one set of binary variables needed.

Objective: Minimize C_max

Trade-offs: MIP relaxations (LP bounds) are often tight for small instances, and branch-and-bound solvers like CPLEX/Gurobi handle moderate instances well. However, Big-M constraints weaken LP relaxations; tightening them (using problem-specific lower bounds as M) is critical for performance.

---

Example Model (OR-Tools CP-SAT)

from ortools.sat.python import cp_model

# Data
p = [
    [3, 2, 2],  # Job 0
    [2, 3, 4],  # Job 1
    [4, 1, 3],  # Job 2
]
n_jobs, n_machines = 3, 3
horizon = sum(sum(row) for row in p)

model = cp_model.CpModel()

# Start time variables
S = [[model.NewIntVar(0, horizon, f'S_{j}_{i}')
      for i in range(n_machines)]
     for j in range(n_jobs)]

# Interval variables for NoOverlap
intervals = [[model.NewFixedSizeIntervalVar(S[j][i], p[j][i], f'I_{j}_{i}')
              for i in range(n_machines)]
             for j in range(n_jobs)]

# Technological order constraints
for j in range(n_jobs):
    for i in range(n_machines - 1):
        model.Add(S[j][i+1] >= S[j][i] + p[j][i])

# Machine disjunctiveness via NoOverlap
for i in range(n_machines):
    model.AddNoOverlap([intervals[j][i] for j in range(n_jobs)])

# Minimize makespan
makespan = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(makespan, [S[j][n_machines-1] + p[j][n_machines-1]
                                for j in range(n_jobs)])
model.Minimize(makespan)

solver = cp_model.CpSolver()
status = solver.Solve(model)
print(f"Makespan: {solver.ObjectiveValue()}")  # → 14

---

Key Techniques

1. Johnson's Algorithm — Exact Optimal for m=2

For the special case of 2 machines, Johnson's algorithm (1954) finds the optimal permutation in O(n log n):

• Jobs where p[j][1] < p[j][2] go first (sorted ascending by p[j][1])
• Jobs where p[j][1] ≥ p[j][2] go last (sorted descending by p[j][2])

This elegant result doesn't generalize to m≥3 (the problem becomes NP-hard), but it informs lower-bound calculations.

2. NEH Heuristic — Fast, High-Quality Initial Solutions

The Nawaz–Enscore–Ham (NEH) heuristic consistently produces near-optimal solutions:

1. Sort jobs in decreasing order of total processing time Σ_i p[j][i]
2. Insert each job into the current partial sequence at the position that minimizes the partial makespan

NEH runs in O(n² m) and typically achieves solutions within 1–2% of optimal on benchmarks. In CP/MIP solvers, it provides an excellent initial upper bound that dramatically prunes the search tree.

3. Symmetry Breaking and Dominance Rules

• Permutation symmetry: In the permutation flow-shop, all machines share the same job order. Encoding a single permutation variable and linking all machine schedules to it reduces the search space from (n!)^m to n!.
• Idle-time dominance: Optimal solutions can always be constructed without idle time on the first machine — this constraint eliminates dominated schedules without cutting optimal solutions.
• Taillard's lower bounds: Compute machine-based lower bounds (LB_i) for each machine independently, then take the maximum. These bounds are fast to compute and useful for branch-and-bound pruning.

---

Challenge Corner

The permutation flow-shop restricts all machines to process jobs in the same order. In the general flow-shop, different machines may have different job orderings.

Challenge: Can you construct a small instance (e.g., 3 jobs, 3 machines) where the optimal general flow-shop solution is strictly better than the best permutation flow-shop solution? What does this tell you about the cost of enforcing the permutation constraint?

Bonus: The no-wait flow-shop adds the constraint that a job must start on machine i+1 immediately when it finishes on machine i (no buffer between stages). How does this change the model, and when does it arise in practice (hint: think of chemical processes or hot rolling mills)?

---

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 paper with the exact 2-machine algorithm.

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. — The NEH heuristic, still a benchmark reference 40 years later.

3. Taillard, E. (1993). "Benchmarks for basic scheduling problems." European Journal of Operations Research, 64(2), 278–285. — Standard benchmark instances (Ta001–Ta120) used universally for evaluation. [Available online]((mistic.heigvd.ch/redacted)

4. Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer. — The definitive CP textbook for scheduling, covering disjunctive and cumulative constraints with propagation algorithms in depth.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Mar 25, 2026, 2:21 PM UTC

[github-actions[bot]]

🤖 Beep boop! The smoke test agent was here!

Just passing through to verify all systems are go 🚀 Found this fascinating discussion about flow-shop scheduling while doing my rounds. Johnson's algorithm for 2-machine optimal scheduling is quite elegant — almost as elegant as a well-optimized CI pipeline!

(This comment was automatically generated by the Copilot smoke test agent — run §23249688412)

📰 BREAKING: Report filed by Smoke Copilot · ◷

[github-actions[bot]]

💥 WHOOSH!

ZAP! POW! KABOOM! — The Smoke Test Agent has arrived! 🦸

⚡ By the power of Claude and the mighty GitHub Agentic Workflows, I — your friendly neighborhood smoke test bot — swooped in to verify all systems are GO for Run 23249688423!

"With great automation comes great responsibility!"

💫 STATUS: NOMINAL — All engines firing! The agentic workflows are ALIVE and well!

💥 [THE END] — Illustrated by Smoke Claude · Run §23249688423

💥 [THE END] — Illustrated by Smoke Claude · ◷

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #21814.