🧩 Constraint Solving POTD:Job-Shop Scheduling

[github-actions[bot]]

Problem Statement

In the Job-Shop Scheduling Problem (JSSP), you have n jobs and m machines. Each job consists of an ordered sequence of operations, where operation (i,k) must be processed on a specific machine μ(i,k) for a known duration p(i,k). The constraints are:

• Precedence: within each job, operations must execute in order.
• No overlap: each machine can process at most one operation at a time.

The goal is to assign a start time s(i,k) to each operation so that all constraints are satisfied and the makespan (completion time of the last operation) is minimized.

Concrete Instance (3 jobs × 3 machines)

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

Input: processing times and machine routes per job.
Output: start times s(i,k) minimising Cmax = max_i C_i (where C_i is the completion time of job i).

---

Why It Matters

• Manufacturing: factory floors schedule batches of products through a sequence of machine tools — JSSP is the direct model.
• Cloud computing: workflow DAGs mapped onto heterogeneous servers share the same structure, with machines replaced by CPUs/GPUs.
• Compiler register allocation: instruction scheduling on pipelined processors is a close relative of JSSP.

---

Modeling Approaches

1. Constraint Programming (CP)

Decision variables:

• s[i][k] — start time of operation (i,k), domain [0, H] where H is a horizon upper bound.

Core constraints:

// Precedence
for each job i, consecutive ops k, k+1:
  s[i][k] + p[i][k] <= s[i][k+1]

// No-overlap on each machine (using the global NoOverlap constraint):
for each machine m:
  NoOverlap({ (s[i][k], p[i][k]) | μ(i,k) = m })

minimize max_i (s[i][last_k] + p[i][last_k])

Trade-offs: The NoOverlap (or Cumulative(capacity=1)) global constraint enables powerful edge-finding and not-first/not-last propagation. Horizon tightening via critical-path analysis reduces domains significantly before search.

2. Mixed-Integer Programming (MIP)

Introduce binary variables y[i][j][m] = 1 if operation i precedes operation j on machine m:

// Precedence (same as CP)
s[i][k] + p[i][k] <= s[i][k+1]

// Disjunctive (big-M formulation)
for each machine m, pair of ops (a,b) on m:
  s[a] + p[a] <= s[b] + M*(1 - y[a][b][m])
  s[b] + p[b] <= s[a] + M*y[a][b][m]

minimize Cmax

Trade-offs: MIP benefits from LP relaxation bounds and branch-and-bound, but the big-M weakens LP relaxations. Choosing tight M (e.g., horizon from critical path) is essential. MIP solvers scale poorly beyond ~20 jobs × 20 machines without additional cuts.

Example Model — OR-Tools CP-SAT (Python snippet)

from ortools.sat.python import cp_model

def solve_jssp(jobs_data):
    model = cp_model.CpModel()
    horizon = sum(t for job in jobs_data for _, t in job)

    task_type = collections.namedtuple('task_type', 'start end interval')
    all_tasks = {}
    machine_to_intervals = collections.defaultdict(list)

    for job_id, job in enumerate(jobs_data):
        for task_id, (machine, duration) in enumerate(job):
            start = model.NewIntVar(0, horizon, f's_{job_id}_{task_id}')
            end   = model.NewIntVar(0, horizon, f'e_{job_id}_{task_id}')
            iv    = model.NewIntervalVar(start, duration, end, f'iv_{job_id}_{task_id}')
            all_tasks[(job_id, task_id)] = task_type(start, end, iv)
            machine_to_intervals[machine].append(iv)

    # No-overlap on each machine
    for machine in machine_to_intervals:
        model.AddNoOverlap(machine_to_intervals[machine])

    # Precedence within each job
    for job_id, job in enumerate(jobs_data):
        for t in range(len(job) - 1):
            model.Add(all_tasks[(job_id, t)].end <= all_tasks[(job_id, t+1)].start)

    # Minimize makespan
    makespan = model.NewIntVar(0, horizon, 'makespan')
    model.AddMaxEquality(makespan, [all_tasks[(j, len(jobs_data[j])-1)].end
                                     for j in range(len(jobs_data))])
    model.Minimize(makespan)

    solver = cp_model.CpSolver()
    solver.Solve(model)
    return solver.ObjectiveValue()

---

Key Techniques

1. Edge-Finding Propagation

Given a set of tasks on one machine, edge-finding detects when a task t must execute before (or after) an entire group of other tasks, even if no individual pairwise constraint forces it. This quadratic-time algorithm (Vilím 2004) dramatically tightens start-time bounds and is the backbone of modern CP JSSP solvers.

2. Critical-Path / Energetic Reasoning

The critical path gives a lower bound on makespan by summing the longest chain of dependent operations. Energetic reasoning extends this: if the total work of tasks assigned to a time window exceeds the available machine capacity in that window, adjustments are mandatory. These bounds drive both propagation and branch-and-bound.

3. Disjunctive Scheduling & Branching Strategies

Search for JSSP typically uses disjunctive branching — at each node, pick a pair of conflicting operations on the same machine and branch on their relative order. The Shifting Bottleneck heuristic identifies the most-loaded machine first, solving sub-problems sequentially to guide search. Combined with Large Neighbourhood Search (LNS), this yields strong anytime performance on benchmark instances like the Taillard or Lawrence sets.

---

Challenge Corner

Symmetry & Dominance: In some JSSP instances, two jobs share identical machine routes and processing times. What symmetry-breaking constraints would you add, and how would they interact with edge-finding propagation?

Extension — Flexible JSSP: Suppose each operation can be processed on any machine from a given set (with possibly different durations). How would you extend the CP model? What new global constraints become relevant?

---

References

1. Applegate & Cook (1991) — A computational study of the job-shop scheduling problem. ORSA Journal on Computing — the landmark empirical study that established benchmark difficulty.
2. Vilím, P. (2004) — Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n). CPAIOR — the efficient edge-finding algorithm used in all modern CP solvers.
3. Pinedo, M. (2016) — Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer — comprehensive textbook covering JSSP and dozens of variants.
4. Google OR-Tools CP-SAT documentation — [developers.google.com/optimization]((developers.google.com/redacted) — practical tutorial with runnable Python code for JSSP.

Generated by 🧩 Constraint Solving — Problem of the Day · ● 2.1M · ◷

• expires on May 24, 2026, 11:47 AM UTC

[github-actions[bot]]

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

A newer discussion is available at Discussion #33026.