---
tocdepth: 3
---

# p8 | Job Shop Scheduling Problem (JSSP)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- We add the implicit assumptions: there is at least one job and machine, processing times $p_{j,k} \ge 0$, and $Om$ encodes a valid JSSP instance. To be a valid JSSP instance, each job has exactly one operation assigned per machine.
- EvoCut arXiv submissions `v1` cut EC3 has an ambiguous interpretation and is excluded.
```


## Description

The Job Shop Scheduling Problem (JSSP) is a classic NP-hard combinatorial optimization problem. It involves scheduling a set of jobs on multiple machines, where each job comprises a sequence of operations that must be processed in a specified order on designated machines. The objective is to minimize the makespan (the completion time of the last operation), ensuring that each machine handles at most one operation at a time.

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- This is the MILP formulation given in Section F.4 of EvoCut arXiv submissions `v1`. We make one modification to better match the FormulationBench JSON format. The original formulation defines $\mathcal{P}$ as the set of distinct ordered pairs $(j_1, k_1), (j_2, k_2)$ that require the same machine. Instead, we define $Om_{j,k}$ to be the machine that the $k$-th operation of job $j$ is assigned to.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of jobs | integer | *scalar* |
| `m` | Number of machines | integer | *scalar* |
| `p` | Processing time of the k-th operation of job j | continuous | `[n, m]` |
| `Om` | Machine index assigned to the k-th operation of job j | integer | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `P` | Set of conflict pairs: all ((j1,k1),(j2,k2)) with j1!=j2 or k1!=k2 that share the same machine | $\mathcal{P} = \{((j_1,k_1),(j_2,k_2)) : Om_{j_1,k_1} = Om_{j_2,k_2},\; (j_1,k_1) \prec_{\mathrm{lex}} (j_2,k_2)\}$ |
| `M` | Big-M constant: sum of all processing times | $M = \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `S` | Start time of the k-th operation of job j | continuous | `[n, m]` |
| `y` | 1 if operation (j1,k1) is scheduled before (j2,k2) on their shared machine, 0 otherwise; indexed over conflict pairs P | binary | `(j1, k1, j2, k2) for (j1, k1), (j2, k2) in P` |
| `C_max` | Makespan: completion time of the last operation across all jobs | continuous | *scalar* |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Processing times are non-negative. | $p_{j,k} \geq 0 \quad \forall j,k$ | yes |
| There is at least one job and one machine. | $n \geq 1, \; m \geq 1$ | yes |
| Each operation is assigned to exactly one machine (Om is a total function into machines). | $\forall j,k: \; \exists!\, i: \; Om_{j,k} = i$ | yes |
| For each job, its operations visit every machine exactly once (Om[j] is a permutation of the machine set). | $\forall j, i: \; \exists!\, k: \; Om_{j,k} = i$ | yes |


#### Constraints

- Technological ordering: each operation in a job must start after the previous operation finishes.

  $$ S_{j,k+1} \ge S_{j,k} + p_{j,k} \quad \forall j,\; k = 0,\dots,m-2 $$

- Machine non-overlap (forward): if y=1, operation (j1,k1) precedes (j2,k2) on their shared machine.

  $$ S_{j_1,k_1} + p_{j_1,k_1} \le S_{j_2,k_2} + M(1 - y_{j_1,k_1,j_2,k_2}) \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Machine non-overlap (reverse): if y=0, operation (j2,k2) precedes (j1,k1) on their shared machine.

  $$ S_{j_2,k_2} + p_{j_2,k_2} \le S_{j_1,k_1} + M\,y_{j_1,k_1,j_2,k_2} \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Makespan lower bound: the makespan is at least the completion time of each job's last operation.

  $$ C_{\max} \ge S_{j,m-1} + p_{j,m-1} \quad \forall j $$

- Start times are non-negative.

  $$ S_{j,k} \ge 0 \quad \forall j, k $$

- Makespan is non-negative.

  $$ C_{\max} \ge 0 $$

#### Objective

Minimize the makespan.

$$ \min\; C_{\max} $$

### Formulation `b` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC1).
```

```{note}
- The makespan is at least the average per-machine processing time, taken across all operations and machines.
- EC1 is identical in EvoCut arXiv submissions `v1` and `v2` and is included once as this formulation.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of jobs | integer | *scalar* |
| `m` | Number of machines | integer | *scalar* |
| `p` | Processing time of the k-th operation of job j | continuous | `[n, m]` |
| `Om` | Machine index assigned to the k-th operation of job j | integer | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `P` | Set of conflict pairs: all ((j1,k1),(j2,k2)) with j1!=j2 or k1!=k2 that share the same machine | $\mathcal{P} = \{((j_1,k_1),(j_2,k_2)) : Om_{j_1,k_1} = Om_{j_2,k_2},\; (j_1,k_1) \prec_{\mathrm{lex}} (j_2,k_2)\}$ |
| `M` | Big-M constant: sum of all processing times | $M = \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `S` | Start time of the k-th operation of job j | continuous | `[n, m]` |
| `y` | 1 if operation (j1,k1) is scheduled before (j2,k2) on their shared machine, 0 otherwise; indexed over conflict pairs P | binary | `(j1, k1, j2, k2) for (j1, k1), (j2, k2) in P` |
| `C_max` | Makespan: completion time of the last operation across all jobs | continuous | *scalar* |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Processing times are non-negative. | $p_{j,k} \geq 0 \quad \forall j,k$ | yes |
| There is at least one job and one machine. | $n \geq 1, \; m \geq 1$ | yes |
| Each operation is assigned to exactly one machine (Om is a total function into machines). | $\forall j,k: \; \exists!\, i: \; Om_{j,k} = i$ | yes |
| For each job, its operations visit every machine exactly once (Om[j] is a permutation of the machine set). | $\forall j, i: \; \exists!\, k: \; Om_{j,k} = i$ | yes |


#### Constraints

- Technological ordering: each operation in a job must start after the previous operation finishes.

  $$ S_{j,k+1} \ge S_{j,k} + p_{j,k} \quad \forall j,\; k = 0,\dots,m-2 $$

- Machine non-overlap (forward): if y=1, operation (j1,k1) precedes (j2,k2) on their shared machine.

  $$ S_{j_1,k_1} + p_{j_1,k_1} \le S_{j_2,k_2} + M(1 - y_{j_1,k_1,j_2,k_2}) \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Machine non-overlap (reverse): if y=0, operation (j2,k2) precedes (j1,k1) on their shared machine.

  $$ S_{j_2,k_2} + p_{j_2,k_2} \le S_{j_1,k_1} + M\,y_{j_1,k_1,j_2,k_2} \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Makespan lower bound: the makespan is at least the completion time of each job's last operation.

  $$ C_{\max} \ge S_{j,m-1} + p_{j,m-1} \quad \forall j $$

- Start times are non-negative.

  $$ S_{j,k} \ge 0 \quad \forall j, k $$

- Makespan is non-negative.

  $$ C_{\max} \ge 0 $$

- Average Load Bound (EC1): the makespan is at least the average total processing time per machine.

  $$ C_{\max} \ge \frac{1}{m} \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k} $$

#### Objective

Minimize the makespan.

$$ \min\; C_{\max} $$

### Formulation `c` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC2).
```

```{note}
- For each machine, the makespan is at least the total processing time of operations assigned to it, plus the minimum head (earliest a machine's operation can start within its job) and minimum tail (latest a machine's operation finishes before its job ends) across those operations.
- EC2 is identical in EvoCut arXiv submissions `v1` and `v2` and is included once as this formulation.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of jobs | integer | *scalar* |
| `m` | Number of machines | integer | *scalar* |
| `p` | Processing time of the k-th operation of job j | continuous | `[n, m]` |
| `Om` | Machine index assigned to the k-th operation of job j | integer | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `P` | Set of conflict pairs: all ((j1,k1),(j2,k2)) with j1!=j2 or k1!=k2 that share the same machine | $\mathcal{P} = \{((j_1,k_1),(j_2,k_2)) : Om_{j_1,k_1} = Om_{j_2,k_2},\; (j_1,k_1) \prec_{\mathrm{lex}} (j_2,k_2)\}$ |
| `M` | Big-M constant: sum of all processing times | $M = \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k}$ |
| `O` | Set of operations assigned to machine i: pairs (j,k) with Om_{j,k} = i | $O_i = \{ (j,k) : Om_{j,k} = i \} \quad \forall i \in \{0, \dots, m-1\}$ |
| `h` | Head of operation (j,k): total processing time of earlier operations in job j | $h_{j,k} = \sum_{t=0}^{k-1} p_{j,t} \quad \forall j, k$ |
| `tau` | Tail of operation (j,k): total processing time of later operations in job j | $\tau_{j,k} = \sum_{t=k+1}^{m-1} p_{j,t} \quad \forall j, k$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `S` | Start time of the k-th operation of job j | continuous | `[n, m]` |
| `y` | 1 if operation (j1,k1) is scheduled before (j2,k2) on their shared machine, 0 otherwise; indexed over conflict pairs P | binary | `(j1, k1, j2, k2) for (j1, k1), (j2, k2) in P` |
| `C_max` | Makespan: completion time of the last operation across all jobs | continuous | *scalar* |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Processing times are non-negative. | $p_{j,k} \geq 0 \quad \forall j,k$ | yes |
| There is at least one job and one machine. | $n \geq 1, \; m \geq 1$ | yes |
| Each operation is assigned to exactly one machine (Om is a total function into machines). | $\forall j,k: \; \exists!\, i: \; Om_{j,k} = i$ | yes |
| For each job, its operations visit every machine exactly once (Om[j] is a permutation of the machine set). | $\forall j, i: \; \exists!\, k: \; Om_{j,k} = i$ | yes |


#### Constraints

- Technological ordering: each operation in a job must start after the previous operation finishes.

  $$ S_{j,k+1} \ge S_{j,k} + p_{j,k} \quad \forall j,\; k = 0,\dots,m-2 $$

- Machine non-overlap (forward): if y=1, operation (j1,k1) precedes (j2,k2) on their shared machine.

  $$ S_{j_1,k_1} + p_{j_1,k_1} \le S_{j_2,k_2} + M(1 - y_{j_1,k_1,j_2,k_2}) \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Machine non-overlap (reverse): if y=0, operation (j2,k2) precedes (j1,k1) on their shared machine.

  $$ S_{j_2,k_2} + p_{j_2,k_2} \le S_{j_1,k_1} + M\,y_{j_1,k_1,j_2,k_2} \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Makespan lower bound: the makespan is at least the completion time of each job's last operation.

  $$ C_{\max} \ge S_{j,m-1} + p_{j,m-1} \quad \forall j $$

- Start times are non-negative.

  $$ S_{j,k} \ge 0 \quad \forall j, k $$

- Makespan is non-negative.

  $$ C_{\max} \ge 0 $$

- Machine Critical-Path Bound (EC2): for each machine, the makespan is at least the total load on that machine plus the minimum head and minimum tail of its operations across all jobs.

  $$ C_{\max} \ge \sum_{(j,k)\in O_i} p_{j,k} + \min_{(j,k)\in O_i} h_{j,k} + \min_{(j,k)\in O_i} \tau_{j,k} \quad \forall i \in \{0, \dots, m-1\} $$

#### Objective

Minimize the makespan.

$$ \min\; C_{\max} $$

### Formulation `d` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC3).
```

```{note}
- The makespan is at least the total processing time of each individual job's chain of operations.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of jobs | integer | *scalar* |
| `m` | Number of machines | integer | *scalar* |
| `p` | Processing time of the k-th operation of job j | continuous | `[n, m]` |
| `Om` | Machine index assigned to the k-th operation of job j | integer | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `P` | Set of conflict pairs: all ((j1,k1),(j2,k2)) with j1!=j2 or k1!=k2 that share the same machine | $\mathcal{P} = \{((j_1,k_1),(j_2,k_2)) : Om_{j_1,k_1} = Om_{j_2,k_2},\; (j_1,k_1) \prec_{\mathrm{lex}} (j_2,k_2)\}$ |
| `M` | Big-M constant: sum of all processing times | $M = \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `S` | Start time of the k-th operation of job j | continuous | `[n, m]` |
| `y` | 1 if operation (j1,k1) is scheduled before (j2,k2) on their shared machine, 0 otherwise; indexed over conflict pairs P | binary | `(j1, k1, j2, k2) for (j1, k1), (j2, k2) in P` |
| `C_max` | Makespan: completion time of the last operation across all jobs | continuous | *scalar* |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Processing times are non-negative. | $p_{j,k} \geq 0 \quad \forall j,k$ | yes |
| There is at least one job and one machine. | $n \geq 1, \; m \geq 1$ | yes |
| Each operation is assigned to exactly one machine (Om is a total function into machines). | $\forall j,k: \; \exists!\, i: \; Om_{j,k} = i$ | yes |
| For each job, its operations visit every machine exactly once (Om[j] is a permutation of the machine set). | $\forall j, i: \; \exists!\, k: \; Om_{j,k} = i$ | yes |


#### Constraints

- Technological ordering: each operation in a job must start after the previous operation finishes.

  $$ S_{j,k+1} \ge S_{j,k} + p_{j,k} \quad \forall j,\; k = 0,\dots,m-2 $$

- Machine non-overlap (forward): if y=1, operation (j1,k1) precedes (j2,k2) on their shared machine.

  $$ S_{j_1,k_1} + p_{j_1,k_1} \le S_{j_2,k_2} + M(1 - y_{j_1,k_1,j_2,k_2}) \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Machine non-overlap (reverse): if y=0, operation (j2,k2) precedes (j1,k1) on their shared machine.

  $$ S_{j_2,k_2} + p_{j_2,k_2} \le S_{j_1,k_1} + M\,y_{j_1,k_1,j_2,k_2} \quad \forall ((j_1,k_1),(j_2,k_2)) \in \mathcal{P} $$

- Makespan lower bound: the makespan is at least the completion time of each job's last operation.

  $$ C_{\max} \ge S_{j,m-1} + p_{j,m-1} \quad \forall j $$

- Start times are non-negative.

  $$ S_{j,k} \ge 0 \quad \forall j, k $$

- Makespan is non-negative.

  $$ C_{\max} \ge 0 $$

- Longest Job Bound (EC3): the makespan is at least the total processing time of each job chain.

  $$ C_{\max} \ge \sum_{k=0}^{m-1} p_{j,k} \quad \forall j $$

#### Objective

Minimize the makespan.

$$ \min\; C_{\max} $$