🧩 Constraint Solving POTD:Problem of the Day: Flow-Shop Scheduling

[github-actions[bot]]

Problem Statement

The Flow-Shop Scheduling Problem

What is it? Flow-shop scheduling is a classic optimization problem where n jobs must be processed sequentially through m machines in a fixed order. Each job j requires a specific processing time on each machine, and no job can move ahead in the queue—every job must visit machines in exactly the same order.

A concrete instance: Imagine a manufacturing line with 3 machines (paint, assemble, test) and 5 products to manufacture. Each product requires a certain time at each station, and no product can skip or reorder its visits:

Job	Machine 1 (paint)	Machine 2 (assemble)	Machine 3 (test)
1	3 hours	2 hours	1 hour
2	2 hours	4 hours	3 hours
3	4 hours	1 hour	2 hours
4	1 hour	3 hours	2 hours
5	2 hours	2 hours	2 hours

Goal: Find a permutation (order) of jobs that minimizes makespan—the total time from when the first job starts until the last job finishes. Constraints:

• Each job visits machines 1, 2, 3 in that fixed order.
• No machine can process more than one job at a time.
• No job can move backward in the sequence.

Why It Matters

Manufacturing & Production: Flow-shop models are used in real automotive plants, electronics assembly lines, and steel mills where jobs flow through standardized process sequences. Optimizing the sequence can save millions annually by reducing idle time and equipment downtime.

Semiconductor Fabrication: Wafer processing follows fixed stages (photolithography, etching, deposition, testing). Scheduling thousands of wafer lots through fabs is a critical bottleneck; even 1% improvement in throughput yields substantial cost reduction.

Food & Beverage Processing: Production lines have fixed stages (cooking, packaging, labeling). Optimizing job order reduces energy consumption and product waste.

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision Variables:

• succ[j] ∈ {0, 1, ..., n-1}: position of job j in the sequence
• start[j][m]: start time of job j on machine m
• end[j][m] = start[j][m] + duration[j][m]: end time

Key Constraints:

• Sequence: succ is a permutation of {0, 1, ..., n-1}
• Precedence (machine order): end[j][m] ≤ start[j][m+1] for all jobs j and machines m
• Machine capacity: For any two jobs j1, j2 on machine m, either end[j1][m] ≤ start[j2][m] or end[j2][m] ≤ start[j1][m]

Why use CP? Strong propagation of global constraints like cumulative can efficiently prune the search space. Disjunctive constraints model mutual exclusion on machines elegantly.

Example Model (MiniZinc-style pseudo-code)

int: n_jobs = 5;
int: n_machines = 3;
array[1..n_jobs, 1..n_machines] of int: duration;

array[1..n_jobs] of var 0..n_jobs-1: job_position;  % sequence
array[1..n_jobs, 1..n_machines] of var int: start;

% Sequence constraint
constraint all_different(job_position);

% Precedence on machines (machine order)
constraint forall(j in 1..n_jobs, m in 1..n_machines-1) (
  start[j, m] + duration[j, m] <= start[j, m+1]
);

% Machine capacity (disjunctive)
constraint forall(m in 1..n_machines) (
  cumulative([start[j, m] | j in 1..n_jobs],
             [duration[j, m] | j in 1..n_jobs],
             [1 | j in 1..n_jobs], 1)
);

% Objective: minimize makespan
var int: makespan = max(j in 1..n_jobs)(
  start[j, n_machines] + duration[j, n_machines]
);

solve minimize makespan;

Approach 2: Mixed-Integer Linear Programming (MILP)

Decision Variables:

• x[j][k] ∈ {0, 1}: binary variable = 1 iff job j is in position k
• start[j][m] ≥ 0: start time of job j on machine m
• makespan ≥ 0

Key Constraints:

• Assignment: ∑_k x[j][k] = 1 (each job assigned exactly once)
• Order: ∑_j j·x[j][k] = k (position assignment)
• Precedence: start[j][m+1] ≥ start[j][m] + duration[j][m]
• Disjunctive (big-M): For positions k1 < k2 on machine m:

  start[job_at_k2][m] ≥ start[job_at_k1][m] + duration[job_at_k1][m] - M(1 - x[j1][k1])
  

Why use MILP? Commercial solvers (CPLEX, Gurobi) are robust and can scale to moderate sizes. Relaxations provide strong bounds for branch-and-bound. Easy to add side constraints (resource limits, due dates).

Key Techniques

1. Precedence and Disjunctive Propagation

Arc consistency on precedence edges (end[j][m] ≤ start[j][m+1]) tightens time windows early. Disjunctive constraint propagation on machines uses "edge-finding" and "not-first/not-last" rules to infer bounds on start times and detect infeasibility.

2. Idle-Time and Edge-Finding Heuristics

Modern CP solvers detect "idle time"—gaps between consecutive jobs on a machine that cannot be filled by any later job. This prunes the search dramatically. Edge-finding identifies which jobs must precede others on each machine, strengthening the model.

3. Search Strategies

• Variable Ordering: Branch on the position with highest priority (e.g., first available position) or on critical machines first.
• Value Ordering: Try jobs with smallest (or largest) processing times first.
• Restart Policies: Geometric restarts with learned clauses (from failed nodes) guide search away from bad regions.

4. Symmetry Breaking

When multiple jobs have identical processing times, the search space grows exponentially. Breaking symmetry early (e.g., forcing job i before job i+1 when durations are equal) reduces redundant search.

Challenge Corner

Can you think of this variant? Most real flow-shops have setup times—additional delays when switching from one job to another on a machine (e.g., cleaning, recalibration). How would you modify the model and search strategy to handle setup times that depend on the sequence of jobs (job i followed by job j has a specific setup penalty setup[i][j])?

Bonus: What happens if jobs are allowed to skip machines? (Some products don't need testing, or some skip painting.) How does your model adapt?

References

• Pinedo, M. Scheduling: Theory, Algorithms, and Systems (5th ed., 2016). Classic reference for all scheduling paradigms, with detailed flow-shop chapters.
• Brucker, P. Scheduling Algorithms (5th ed., 2007). Theoretical foundations and polynomial-time special cases (e.g., 2-machine flow-shop, Johnsons algorithm).
• van Laarhoven, P. J. M., & Aarts, E. H. L. "Simulated Annealing: Theory and Applications" (1987). Applies metaheuristics to flow-shop and other scheduling NP-hard problems.
• Baptiste, P., Le Pape, C., & Nuijten, W. Constraint-Based Scheduling (2001). Deep dive into CP techniques for scheduling, including propagation and global constraints.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.84 AIC · ⌖ 6.88 AIC · ⊞ 6.2K · ◷

• expires on Sep 14, 2026, 3:36 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #59439.