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

[github-actions[bot]]

Problem Statement

Job-Shop Scheduling is a classic scheduling problem where you must execute a fixed set of jobs on a set of machines, subject to two constraints:

1. Job precedence: Each job j consists of an ordered sequence of tasks that must execute on different machines in a fixed order.
2. Machine exclusivity: Each machine can process at most one task at a time.

Goal: Find a schedule (assignment of start times to all tasks) that minimizes makespan (the time when all jobs are complete).

Concrete Instance (3-job, 3-machine example)

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

Input: Processing times p[j][i], job precedence chains.
Output: Start times s[j][i] for each job-task, minimizing max(s[j][i] + p[j][i]).

---

Why It Matters

Manufacturing: Job-shop models production planning in factories where different products must visit machines in different orders. A bad schedule wastes time and capacity; a good one can reduce production time by 20–40%.

Project management: Multi-phase projects with dependencies and shared resources (equipment, personnel) can be modeled as job-shop variants.

Data centers: Batch job scheduling across heterogeneous computational resources resembles job-shop structure, especially with precedence constraints.

---

Modeling Approaches

Approach 1: Disjunctive Constraint Programming

Decision variables:

• s[j][i] = start time of task i in job j (integer, ≥ 0)
• C = makespan (objective to minimize)

Constraints (pseudo-code):

// Precedence: task i must finish before task i+1 in job j
for each job j and task i:
    s[j][i] + p[j][i] <= s[j][i+1]

// Disjunctive: for each machine m and any two tasks on m
for each machine m and tasks (j1,i1), (j2,i2) on m:
    s[j1][i1] + p[j1][i1] <= s[j2][i2]  OR
    s[j2][i2] + p[j2][i2] <= s[j1][i1]

// Makespan
for each job j and final task f[j]:
    s[j][f[j]] + p[j][f[j]] <= C

Strengths: Concise formulation; global constraints (cumulative, disjunctive) propagate powerfully.
Trade-off: Disjunctive constraints are NP-hard to propagate; solvers branch on disjunctions, potentially creating many search nodes.

Example (MiniZinc-style pseudo-code)

int: n_jobs, n_machines;
array[1..n_jobs, 1..n_machines] of int: p;  % processing times

var int: C;  % makespan
var 0..max_time: s[1..n_jobs, 1..n_machines];

% Precedence constraints
constraint forall (j in 1..n_jobs, i in 1..n_machines-1) (
    s[j,i] + p[j,i] <= s[j,i+1]
);

% Disjunctive per machine
constraint forall (m in 1..n_machines, 
    (j1,i1) in tasks_on_m, (j2,i2) in tasks_on_m where (j1,i1) < (j2,i2)) (
    disjunctive([s[j1,i1], s[j2,i2]], [p[j1,i1], p[j2,i2]])
);

% Makespan
constraint forall (j in 1..n_jobs) (
    s[j,n_machines] + p[j,n_machines] <= C
);

minimize C;

Approach 2: Mixed-Integer Linear Programming (MIP)

Decision variables:

• s[j][i] = start time of task (j,i) (continuous or integer)
• x[j1,i1,j2,i2] = binary: 1 iff task (j1,i1) starts before (j2,i2) on the same machine

Constraints:

// Precedence
s[j,i] + p[j,i] <= s[j,i+1]

// Disjunctive (linearized via big-M)
for each machine m and conflicting tasks (j1,i1), (j2,i2):
    s[j1,i1] + p[j1,i1] <= s[j2,i2] + M*(1 - x[j1,i1,j2,i2])
    s[j2,i2] + p[j2,i2] <= s[j1,i1] + M*x[j1,i1,j2,i2]

C >= s[j,i] + p[j,i]  for all (j,i)

Strengths: Standard MIP solvers (CPLEX, Gurobi) apply cutting planes and heuristics; scales to large instances when M is tight.
Trade-off: Big-M constant adds tightness issues; relaxation gap can be poor without careful tuning; fewer global constraints than CP.

---

Key Techniques

1. Constraint Propagation & Arc Consistency

Job-shop solvers use edge-finding and not-first/not-last algorithms to infer that a task cannot start within a certain time window. For instance, if task (j2,i2) cannot complete before time t, then all tasks requiring the same machine and starting before t are infeasible.

2. Branching on Disjunctions

Rather than enumerate task orderings, solvers branch on the disjunctive constraint: assume one task precedes another and propagate. This refines the search space without explicitly considering all permutations.

3. Symmetry-Breaking & Dominance

Job-shop instances have symmetric permutations of job order on each machine. Posting symmetry-breaking constraints (e.g., lexicographic orderings) or detecting dominated solutions can prune vast search regions.

---

Challenge Corner

Open Questions:

1. Variable reduction: The classical disjunctive formulation has one variable per (job, task). Can you reformulate using only one variable per job (e.g., a job-completion time) and recover the task-level schedule?

2. Makespan lower bound: The makespan is at least the length of the longest job sequence and the maximum machine load. Can you tighten this bound using Lagrangian relaxation or LP?

3. Online variant: What if new jobs arrive during execution? How would you design a re-optimization strategy that minimizes disruption to the current schedule?

---

References

1. Pinedo, M. (2016). Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer. — Comprehensive textbook covering job-shop fundamentals, algorithms, and complexity.

2. Carlier, J., & Pinson, E. (1989). "An algorithm for solving the job-shop problem." Management Science, 35(2), 164–176. — Seminal paper on edge-finding algorithms for propagation.

3. Baptiste, P., Pape, C. Le, & Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer Academic Publishers. — CP perspective with global constraints and search strategies.

4. OR-Tools Routing Guide (Google). (developers.google.com/redacted) — Practical solver examples and model templates.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 5.56 AIC · ⌖ 7.03 AIC · ⊞ 6.2K · ◷

• expires on Aug 30, 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 #55368.