🧩 Constraint Solving POTD:Job-Shop Scheduling — 2026-04-02

[github-actions[bot]]

Today's problem comes from the Scheduling category. Previous topics: Graph Coloring, Bin Packing, Nurse Rostering, TSP.

---

Problem Statement

You have n jobs and m machines. Each job consists of a sequence of operations that must be processed in a fixed order, each on a specific machine. No two operations can run on the same machine at the same time, and a job's operations must execute one after another (no overlap within a job).

Goal: Find a start time for every operation to minimize the makespan — the time at which the last operation finishes.

Small concrete instance (3 jobs × 3 machines)

Job	Op 1 (machine, duration)	Op 2	Op 3
J1	M1, 3	M2, 2	M3, 2
J2	M1, 2	M3, 1	M2, 4
J3	M2, 4	M1, 1	M3, 3

Input: For each job j and operation index k: the machine μ(j,k) and processing time p(j,k).
Output: Start times s(j,k) ≥ 0 minimising Cmax = max_{j,k} (s(j,k) + p(j,k)).

---

Why It Matters

• Manufacturing floors: Sequencing parts through CNC machines, welders, and paint booths is a daily job-shop problem at scale.
• Cloud computing: Allocating CPU-bound tasks across heterogeneous cores with data-locality constraints maps directly to flexible job-shop variants.
• Semiconductor fabrication: Wafer processing involves hundreds of steps across specialised tools — even small makespan improvements translate to significant yield gains.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables
s(j,k) ∈ [0, UB] — start time of operation (j,k), where UB is a loose upper bound (e.g., sum of all durations).

Constraints

// Precedence within each job
∀ j, k < last:  s(j,k) + p(j,k) ≤ s(j,k+1)

// Non-overlap on each machine  (disjunctive resource)
∀ machine M, ∀ (j,k) ≠ (j',k') with μ(j,k)=μ(j',k')=M:
    s(j,k) + p(j,k) ≤ s(j',k')  OR  s(j',k') + p(j',k') ≤ s(j,k)

// Makespan definition
Cmax ≥ s(j,k) + p(j,k)   ∀ j, k
```

The non-overlap constraints are best expressed as a **`no_overlap`** global constraint (or `cumulative` with capacity 1), enabling powerful **Edge-Finding** and **Not-First/Not-Last** propagation.

**Trade-offs**: Extremely expressive; global constraints make propagation very strong; excellent on tight instances. Search can be expensive on large, loosely-constrained problems.

---

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

Introduce binary variable `y(j,k,j',k') ∈ {0,1}` — equals 1 if `(j,k)` is scheduled before `(j',k')` on the same machine.

**Key constraints**

```
// Precedence within jobs (same as CP)
s(j,k+1) ≥ s(j,k) + p(j,k)

// Disjunctive sequencing (big-M formulation)
s(j,k) + p(j,k) ≤ s(j',k') + M·(1 - y(j,k,j',k'))
s(j',k') + p(j',k') ≤ s(j,k) + M·y(j,k,j',k')

// Makespan
Cmax ≥ s(j,k) + p(j,k)

with M = UB (a sufficiently large constant).

Trade-offs: Standard MIP solvers (Gurobi, CPLEX) apply LP relaxations and branch-and-bound automatically. The big-M weakens LP bounds; tightening with time-indexed or positional formulations improves this at the cost of more variables.

---

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

from ortools.sat.python import cp_model

# jobs[j] = list of (machine, duration) pairs
jobs = [
    [(0, 3), (1, 2), (2, 2)],  # J1
    [(0, 2), (2, 1), (1, 4)],  # J2
    [(1, 4), (0, 1), (2, 3)],  # J3
]
horizon = sum(d for job in jobs for _, d in job)

model = cp_model.CpModel()

# Build interval variables
all_tasks = {}
machine_to_intervals = {m: [] for m in range(3)}

for j, job in enumerate(jobs):
    for k, (machine, duration) in enumerate(job):
        start = model.new_int_var(0, horizon, f's_{j}_{k}')
        end   = model.new_int_var(0, horizon, f'e_{j}_{k}')
        interval = model.new_interval_var(start, duration, end, f'i_{j}_{k}')
        all_tasks[(j, k)] = (start, end, interval)
        machine_to_intervals[machine].append(interval)

# No-overlap per machine
for m in range(3):
    model.add_no_overlap(machine_to_intervals[m])

# Precedence within each job
for j, job in enumerate(jobs):
    for k in range(len(job) - 1):
        model.add(all_tasks[(j, k+1)][0] >= all_tasks[(j, k)][1])

# Minimize makespan
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, [all_tasks[(j, len(job)-1)][1]
                                   for j, job in enumerate(jobs)])
model.minimize(makespan)

solver = cp_model.CpSolver()
status = solver.solve(model)
print(f'Makespan = {solver.objective_value}')

---

Key Techniques

1. Edge-Finding Propagation

Given a set of tasks on a machine, Edge-Finding deduces that if a task t cannot fit between any subset S of other tasks and the end of the schedule, then t must be scheduled after all of S. This tightens lower bounds on start times far beyond simple pairwise reasoning.

2. Symmetry Breaking & Dominance Rules

When two operations on the same machine have no ordering constraint between them, we can fix their relative order without loss of generality (e.g., shorter first when durations are equal). More generally, active schedules — where no operation can be started earlier without delaying another — always contain an optimal solution, reducing the search space dramatically.

3. Branch-and-Bound with Shifting Bottleneck Decomposition

The Shifting Bottleneck heuristic solves a single-machine subproblem (1|r_j|L_max) for each machine in turn, treating already-scheduled machines as release-time constraints. This produces very good primal solutions quickly and is used as an upper-bound oracle inside B&B.

---

Challenge Corner

Think about this: The classic job-shop assumes each job visits each machine at most once. In the Flexible Job-Shop variant, each operation can be processed on any machine from a given set (with possibly different durations). How would you extend the CP model above to handle this? What new global constraints or symmetry-breaking strategies become available?

Bonus: For the 3-job × 3-machine instance above, what is the optimal makespan? Can you prove it via a lower-bounding argument without running a solver?

---

References

1. Pinedo, M. L. — Scheduling: Theory, Algorithms, and Systems (5th ed., Springer, 2016). The definitive textbook for scheduling problems.
2. Applegate, D. & Cook, W. — "A Computational Study of the Job-Shop Scheduling Problem", INFORMS Journal on Computing, 1991. Classic B&B baseline with benchmark instances.
3. Vilím, P. — "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)", CP 2009. The paper behind modern CP propagation for scheduling.
4. Google OR-Tools CP-SAT documentation — [developers.google.com/optimization/scheduling/job_shop]((developers.google.com/redacted) Hands-on solver tutorial for this exact problem.

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

• expires on Apr 9, 2026, 12:55 PM UTC