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

[github-actions[bot]]

Problem Statement

You have jobs and machines. Each job is a fixed sequence of operations, and each operation must run on a specific machine for a fixed duration. A machine processes at most one operation at a time, and the operations of a job must run in order. Find start times that minimize the makespan, the finish time of the last operation.

Small instance (3 jobs, 3 machines, written as (machine, duration)):

Job	Operations in order
J1	(M1, 3) → (M2, 2) → (M3, 2)
J2	(M1, 2) → (M3, 1) → (M2, 4)
J3	(M2, 4) → (M3, 3)

Input: number of jobs n, machines m, and operation lists with durations.
Output: a start time s_{j,k} for each operation that satisfies all constraints and minimizes C_max.

This instance has optimal makespan 11, which I confirmed by exhaustive enumeration of all semi-active schedules. One optimal schedule:

M1: J1[0,3)  J2[3,5)
M2: J3[0,4)  J1[4,6)  J2[6,10)
M3: J2[5,6)  J3[6,9)  J1[9,11)

Why It Matters

• Factory floors and semiconductor fabs: routing lots through machines with fixed process orders.
• Cloud and HPC: placing dependent tasks on limited hardware while keeping throughput high.
• Surgery and clinic planning: each patient follows a fixed pathway through shared rooms and staff.

Modeling Approaches

1. Constraint Programming with interval variables

• Variables: start s_o ∈ [0, H] for each operation o, with fixed duration d_o.
• Precedence: s_{j,k+1} ≥ s_{j,k} + d_{j,k} within each job.
• Machine capacity: a global NoOverlap over the intervals on each machine.
• Objective: minimize C = max_j (s_{j,last} + d_{j,last}).

Trade-off: this is the most natural model. It gives strong propagation through NoOverlap, but bounds from the objective are weaker than LP bounds.

Example Model (Pseudo-code)

for each job j, operation k:
    s[j,k] in 0..H
for each job j, k = 0..len(j)-2:
    s[j,k+1] >= s[j,k] + d[j,k]          # job precedence
for each machine m:
    NoOverlap({ interval(s[j,k], d[j,k]) : (j,k) on m })
C >= s[j,last_j] + d[j,last_j]  for all j
minimize C

This snippet is pseudo-code only. I did not run it through a solver.

2. Mixed-Integer Programming with big-M disjunctions

• Variables: continuous s_o ≥ 0, plus binary y_{o,p} set to 1 when o precedes p on the same machine.
• Disjunction: for each pair (o,p) on one machine, s_o + d_o ≤ s_p + M(1 − y_{o,p}) and s_p + d_p ≤ s_o + M·y_{o,p}.
• Precedence and objective: the same as the CP model.

Trade-off: the formulation is compact and easy to write in any MIP solver. The big-M relaxation is weak, so proving optimality takes a lot of branching.

Key Techniques

• Disjunctive propagation (edge-finding): for a machine, if a set of operations cannot fit before a deadline without one of them finishing last, the solver can tighten start-time bounds. This is where most of CP's power on scheduling comes from.
• Failure-directed search: instead of fixed variable ordering, branch on the variables involved in recent failures (Vilím, Laborie & Shaw, 2015). This tends to beat static heuristics on hard scheduling instances.
• One-machine relaxation bound: for each machine, compute heads (earliest start) and tails (min. work after) and solve the preemptive relaxation with Jackson's rule. Here it gives a bound of 10 on M2, while the true optimum is 11, so search must close the remaining gap.

Challenge Corner

• Why 10 isn't enough: the one-machine bound on M2 is 10, yet the optimum is 11. Can you find a stronger argument that rules out makespan 10?
• Setup times: if switching from job i to job j on a machine costs t_{ij}, how does this change the NoOverlap model? (Hint: check how CP Optimizer's noOverlap supports transition distances.)
• Fewer variables: can you model the same problem using only the machine sequence, as a permutation with repetition, and still get propagation?

References

1. Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006. Scheduling chapters cover interval variables and NoOverlap.
2. Vilím, Laborie & Shaw, "Failure-directed Search for Constraint-based Scheduling," CPAIOR, 2015.
3. Applegate & Cook, "A Computational Study of the Job-Shop Scheduling Problem," ORSA Journal on Computing, 1991.
4. Google OR-Tools, CP-SAT job-shop tutorial: (developers.google.com/redacted)

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~3 AIC · ⌖ ~1 AIC · ⊞ 3.1K · ◷

• expires on Nov 11, 2026, 3:31 AM UTC-08:00