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

[github-actions[bot]]

Problem Statement

In a job-shop scheduling problem, you have:

• m machines and n jobs
• Each job consists of a sequence of tasks that must be completed in a fixed order
• Each task requires exactly one machine for a specified duration
• Goal: Schedule all tasks to minimize total completion time (makespan) while respecting:
  1. Precedence constraints (tasks within a job must follow their order)
  2. Machine capacity (each machine processes at most one task at a time)

Concrete Instance: 3 Jobs, 3 Machines

Job	Task Sequence
J1	M1 (3 units) → M2 (2 units) → M3 (2 units)
J2	M2 (4 units) → M1 (1 unit) → M3 (3 units)
J3	M3 (2 units) → M2 (1 unit) → M1 (4 units)

Question: What is the minimum makespan (total time to complete all jobs)?

Optimal solution: makespan = 11 units (one possible schedule places J1 on M1 at t=0, J2 on M2 at t=0, J3 on M3 at t=0, with careful sequencing to avoid conflicts).

---

Why It Matters

• Manufacturing: Production lines often process multiple products, each requiring specific machines in fixed order. Minimizing makespan reduces lead times and improves throughput.
• Semiconductor fabs: Wafer production involves dozens of steps on specialized equipment; scheduling determines factory utilization and delivery commitments.
• Operations research: Job-shop scheduling is NP-hard even for small instances, making it a canonical hard combinatorial problem with deep theoretical roots and practical impact.

---

Modeling Approaches

Approach 1: Constraint Programming (Disjunctive Model)

Key idea: Use binary variables to decide the order of tasks on each machine.

Decision Variables:

• start[i][j] ∈ [0, ∞) — start time of task i of job j
• order[i][j][k][l] ∈ {0,1} — binary: task (i,j) before task (k,l) on their shared machine?

Constraints:

1. Precedence: start[i+1][j] ≥ start[i][j] + duration[i][j] (tasks in a job follow order)
2. Disjunction: For tasks (i,j) and (k,l) on the same machine:
   • order[i][j][k][l] = 1 ⟹ start[k][l] ≥ start[i][j] + duration[i][j]
   • order[i][j][k][l] = 0 ⟹ start[i][j] ≥ start[k][l] + duration[k][l]
3. Objective: Minimize max_j(start[last_task][j] + duration[last_task][j])

Trade-offs: Explicit disjunctions are intuitive and support strong propagation (e.g., edge-finding). However, the number of binary variables grows as O(n2m2), which can be problematic for large instances.

---

Approach 2: MIP with Precedence Variables

Key idea: Linearize machine conflicts using Big-M constraints and continuous timing variables.

Decision Variables:

• start[i][j] ∈ [0, M] — start time (continuous)
• before[i,j,k,l] ∈ {0,1} — 1 if task (i,j) finishes before task (k,l) starts on a machine

Constraints:

1. Precedence: Same as CP model
2. Big-M disjunction: For tasks on the same machine, introduce:
   • start[k][l] ≥ start[i][j] + duration[i][j] - M·(1 - before[i,j,k,l])
   • start[i][j] ≥ start[k][l] + duration[k][l] - M·before[i,j,k,l]
3. Objective: Minimize makespan

Trade-offs: MIP formulations integrate naturally with standard solvers (CPLEX, Gurobi) and leverage cutting planes. However, Big-M values must be carefully tuned; loose bounds weaken the LP relaxation.

---

Example: Mini CP Model (Pseudo-code)

# Simplified job-shop scheduling in constraint programming style
from constraint_solver import Solver, IntVar, Constraint

m, n = 3, 3  # 3 machines, 3 jobs
jobs = [
    [(0, 3), (1, 2), (2, 2)],  # Job 0: M0 3u, M1 2u, M2 2u
    [(1, 4), (0, 1), (2, 3)],  # Job 1: M1 4u, M0 1u, M2 3u
    [(2, 2), (1, 1), (0, 4)]   # Job 2: M2 2u, M1 1u, M0 4u
]

solver = Solver()

# Decision: start time of each task
start = {}
for j in range(n):
    for i, (machine, duration) in enumerate(jobs[j]):
        start[(i, j)] = IntVar(0, 100)

# Constraints: precedence within jobs
for j in range(n):
    for i in range(len(jobs[j]) - 1):
        machine_i, dur_i = jobs[j][i]
        solver.add(start[(i+1, j)] >= start[(i, j)] + dur_i)

# Constraints: machine capacity (disjunction)
for machine in range(m):
    tasks_on_machine = [(i, j) for j in range(n) for i, (m_id, _) in enumerate(jobs[j]) if m_id == machine]
    for idx1, (i1, j1) in enumerate(tasks_on_machine):
        for i2, j2 in tasks_on_machine[idx1+1:]:
            dur1 = jobs[j1][i1][1]
            dur2 = jobs[j2][i2][1]
            # Either task 1 finishes before task 2 starts, or vice versa
            solver.add_disjunction([
                start[(i2, j2)] >= start[(i1, j1)] + dur1,
                start[(i1, j1)] >= start[(i2, j2)] + dur2
            ])

# Objective: minimize makespan
makespan = IntVar(0, 1000)
for j in range(n):
    last_task_idx = len(jobs[j]) - 1
    duration = jobs[j][last_task_idx][1]
    solver.add(makespan >= start[(last_task_idx, j)] + duration)

solver.minimize(makespan)
solution = solver.solve()
print(f"Optimal makespan: {solution[makespan]}")

---

Key Techniques

1. Disjunctive Constraint Propagation

Machine conflicts create disjunctions — at least one of two orderings must hold. Modern CP solvers implement arc consistency over disjunctions via:

• Edge-finding: If task A must complete before any other task on a machine, we can deduce tight bounds on when A finishes.
• Not-first / not-last rules: If a task cannot start first on a machine (due to makespan bounds), we know it must finish before some other task.

These propagation rules dramatically reduce search space compared to naive enumeration.

---

2. Variable and Value Ordering Heuristics

Search performance hinges on decision order:

• Critical path heuristic: Branch first on tasks on the longest projected path to completion.
• Most-constrained-variable: Prioritize tasks with smallest time windows (high degree of constraint).
• Earliest-start ordering: Select task with earliest feasible start time first (greedy lower bound).

In practice, combining these with impact-based search (branching on variables that most reduce search space) yields orders-of-magnitude speedup.

---

3. Symmetry Breaking and Lower Bounds

Job-shop has inherent symmetry (permuting jobs yields equivalent problems). Symmetries explode search trees:

• Add redundant constraints: "Job J1 starts before Job J2" eliminates symmetric branches.
• Compute strong lower bounds: Longest-path on the task precedence graph + per-machine load balancing gives a lower bound; if current upper bound matches, we can prune.
• Beam search + restarts: Alternate between greedy heuristic construction and exact search to escape local plateaus.

---

Challenge Corner

Question for you: The job-shop problem becomes open-shop if you remove the job-level precedence constraints—any task can be scheduled whenever its machine is free. How would this change the structure of the problem? Would standard CP propagation still be effective? Can you construct an instance where open-shop is easier to solve than job-shop?

Bonus: In practice, real factories have release times (a job cannot start until time r_j) and due dates (a job should complete by time d_j). How would you extend the model to penalize tardiness? Would you use weighted sum or constraint satisfaction?

---

References

1. Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Scheduling Computer and Manufacturing Processes (2nd ed.). Springer. — Comprehensive reference on scheduling problems including detailed coverage of job-shop algorithms.

2. Van Hentenryck, P. (1989). Constraint Satisfaction in Logic Programming. MIT Press. — Early foundation for CP approaches to scheduling; Chapters 4–5 cover disjunctive scheduling and propagation.

3. Carlier, J., & Pinson, E. (1989). "An Algorithm for Solving the Job-Shop Problem." Management Science, 35(2), 164–176. — Classic paper introducing edge-finding and state-of-the-art bounds for small instances.

4. OR-Tools Job-Shop Example: (developers.google.com/redacted) — Practical introduction with code examples in Python and C++.

---

What constraint-solving topic should we explore tomorrow? Reply with suggestions or vote on the next category!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 29.3K · ◷

• expires on Jun 7, 2026, 11:56 AM UTC