🧩 Constraint Solving POTD:Open-Shop Scheduling

[github-actions[bot]]

Welcome to today's Constraint Solving Problem of the Day! Today we complete the classic scheduling trilogy — after Job-Shop and Flow-Shop, it's time for Open-Shop Scheduling.

---

Problem Statement

You have n jobs and m machines. Each job j has exactly one operation to perform on each machine i, with a known processing time p[i][j]. Unlike Job-Shop scheduling:

• There is no prescribed order in which a job must visit machines — operations of a job can execute in any sequence.
• Each machine can process at most one job at a time.
• Each job can be processed on at most one machine at a time.

Goal: Assign start times to all operations so that the makespan (time when the last operation finishes) is minimized.

Concrete Instance (3 jobs × 3 machines)

	Machine 1	Machine 2	Machine 3
Job A	3	2	2
Job B	2	1	4
Job C	2	3	1

Processing times are given; there is no forced operation order within any job.

Input: n × m matrix of non-negative processing times p[i][j]
Output: Start time s[i][j] for each operation (i, j) minimizing max_{i,j}(s[i][j] + p[i][j])

A simple lower bound on the makespan is: C* ≥ max(max_j Σ_i p[i][j], max_i Σ_j p[i][j]), i.e., the maximum total load on any single machine or any single job.

---

Why It Matters

Manufacturing & semiconductor fabrication: Wafer processing steps can often be performed in flexible order on different machines, making open-shop a natural fit for fab scheduling.

Healthcare & service systems: Patient tests (blood work, imaging, consultation) need to happen on different "machines" (departments) but have no required visit order — the open-shop captures this flexibility.

Parallel computing: Task graphs with independent subtasks mapped to processors, where execution order within a task is free, fit the open-shop model well.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:

• s[i][j] ∈ 0..UB — start time of operation (machine i, job j)
• C_max ∈ 0..UB — makespan to minimize

Constraints:

// No-overlap on each machine (disjunctive resource):
for each machine i:
  NoOverlap({ Interval(s[i,j], p[i,j]) | j = 1..n })

// No-overlap per job (each job on at most one machine at a time):
for each job j:
  NoOverlap({ Interval(s[i,j], p[i,j]) | i = 1..m })

// Makespan:
for all i, j: s[i,j] + p[i,j] <= C_max
```

**Trade-offs:** CP propagation with `NoOverlap` / `Cumulative` global constraints is very effective for medium instances (n, m ≤ 20). The absence of sequencing constraints makes the search space *larger* than Job-Shop — there are more valid orderings, but also more symmetry to break.

---

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

Introduce binary variables to model pairwise orderings on each machine and per job:

**Variables:**
- `s[i][j] ≥ 0` — start time (continuous)
- `y[i][j1][j2] ∈ {0,1}` — 1 if job `j1` precedes job `j2` on machine `i`
- `z[i1][i2][j] ∈ {0,1}` — 1 if operation `(i1,j)` precedes `(i2,j)` in job `j`'s schedule
- `C_max` — makespan

**Constraints (using big-M `M`):**
```
// Machine disjunctive:
s[i,j1] + p[i,j1] ≤ s[i,j2] + M·(1 - y[i,j1,j2])   ∀ i, j1≠j2
s[i,j2] + p[i,j2] ≤ s[i,j1] + M·y[i,j1,j2]           ∀ i, j1<j2

// Job disjunctive (intra-job ordering):
s[i1,j] + p[i1,j] ≤ s[i2,j] + M·(1 - z[i1,i2,j])    ∀ j, i1≠i2
s[i2,j] + p[i2,j] ≤ s[i1,j] + M·z[i1,i2,j]           ∀ j, i1<i2

Trade-offs: MIP LP relaxations can provide strong bounds, but big-M formulations weaken them. The number of binary variables grows as O(n²m + nm²), so MIP scales less gracefully than CP for large instances. However, branch-and-bound with strong cuts can outperform CP on certain structured instances.

---

Example Model (MiniZinc CP)

include "globals.mzn";

int: n = 3;  % jobs
int: m = 3;  % machines
array[1..m, 1..n] of int: p = [| 3,2,2 | 2,1,4 | 2,3,1 |];

int: UB = sum(i in 1..m, j in 1..n)(p[i,j]);
array[1..m, 1..n] of var 0..UB: s;
var 0..UB: C_max;

% No overlap on each machine
constraint forall(i in 1..m)(
  disjunctive([s[i,j] | j in 1..n], [p[i,j] | j in 1..n])
);

% No overlap per job (job can only be on one machine at a time)
constraint forall(j in 1..n)(
  disjunctive([s[i,j] | i in 1..m], [p[i,j] | i in 1..m])
);

% Makespan definition
constraint forall(i in 1..m, j in 1..n)(
  s[i,j] + p[i,j] <= C_max
);

solve minimize C_max;

---

Key Techniques

1. Edge-Finding and Not-First/Not-Last Propagation

Since both machines and jobs impose disjunctive constraints, edge-finding is critical: if the total processing time of a subset of operations on a machine exceeds available time before a deadline, their order can be fixed. Open-shop benefits from applying edge-finding in both dimensions (per machine and per job) simultaneously.

2. Symmetry Breaking

Open-shop has significant symmetry: permuting job IDs or machine IDs yields equivalent solutions. Adding lexicographic ordering constraints on start times (e.g., s[1,1] ≤ s[1,2]) prunes the symmetric portion of the search tree substantially. However, over-constraining can cut optimal solutions, so care is needed with partial symmetry breaking.

3. Lower Bound Tightening via Preemptive Relaxation

The preemptive open-shop (where operations can be interrupted and resumed) is solvable in polynomial time (Gonzalez & Sahni, 1976). Its optimal makespan is max(max_j Σ_i p[i,j], max_i Σ_j p[i,j], max_{i,j} p[i,j]). Using the preemptive optimum as a lower bound during branch-and-bound dramatically narrows the search — it's an unusually tight bound for a combinatorial problem.

---

Challenge Corner

The Gonzalez–Sahni bound tells us that in the preemptive relaxation, the optimal makespan equals the lower bound. But in the non-preemptive version, this bound can be achieved too for small instances:

🤔 Can you prove (or find a counterexample) that for 2-machine open-shop, the preemptive lower bound is always tight? That is, for any 2 × n instance, is the optimal non-preemptive makespan always equal to max(max_j (p[1,j]+p[2,j]), Σ_j p[1,j], Σ_j p[2,j])?

Bonus: How would you extend the CP model to handle flexible processing times — where each operation has a range [p_min[i,j], p_max[i,j]] and we choose the duration to minimize makespan?

---

References

1. Gonzalez, T. & Sahni, S. (1976). "Open shop scheduling to minimize finish time." Journal of the ACM, 23(4), 665–679. — The foundational paper proving the preemptive case is polynomial.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of Constraint Programming, Elsevier. — Chapter 20 covers scheduling constraints including disjunctive and cumulative resources.

3. Brucker, P. (2007). Scheduling Algorithms (5th ed.), Springer. — Comprehensive treatment of open-shop, job-shop, and flow-shop complexity and algorithms.

4. CP-SAT Solver (Google OR-Tools). [developers.google.com/optimization]((developers.google.com/redacted) — Modern solver with NewIntervalVar and AddNoOverlap natively supporting open-shop models.

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

• expires on Apr 3, 2026, 12:54 PM 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 #23350.