p8 | Job Shop Scheduling Problem (JSSP)¶
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.
The EC3 cut in
v1of Yazdani et al. [2] has an ambiguous interpretation and is excluded.
NP-hard: yes
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)¶
Note
This is the JSSP formulation from
v1of Yazdani et al. [2]. To fit the FormulationBench JSON format, we represent the shared-machine relation \(\mathcal{P}\) using \(Om_{j,k}\), the machine assigned to the \(k\)-th operation of job \(j\).
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of jobs |
integer |
scalar |
|
Number of machines |
integer |
scalar |
|
Processing time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
Machine index assigned to the \(k\)-th operation of job \(j\) |
integer |
|
Definitions¶
Name |
Description |
Formulation |
|---|---|---|
|
Set of conflict pairs: all \(((j_1,k_1),(j_2,k_2))\) with \(j_1 \neq j_2\) or \(k_1 \neq k_2\) 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)\}\) |
|
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 |
|---|---|---|---|
|
Start time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
\(1\) if operation \((j_1,k_1)\) is scheduled before \((j_2,k_2)\) on their shared machine, \(0\) otherwise; indexed over conflict pairs \(P\) |
binary |
|
|
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 \((j_1,k_1)\) precedes \((j_2,k_2)\) 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 \((j_2,k_2)\) precedes \((j_1,k_1)\) 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.
Formulation b (valid)¶
Note
This is the JSSP formulation from
v1of Yazdani et al. [2] augmented with acceleration cut EC1, which is unchanged inv2.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of jobs |
integer |
scalar |
|
Number of machines |
integer |
scalar |
|
Processing time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
Machine index assigned to the \(k\)-th operation of job \(j\) |
integer |
|
Definitions¶
Name |
Description |
Formulation |
|---|---|---|
|
Set of conflict pairs: all \(((j_1,k_1),(j_2,k_2))\) with \(j_1 \neq j_2\) or \(k_1 \neq k_2\) 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)\}\) |
|
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 |
|---|---|---|---|
|
Start time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
\(1\) if operation \((j_1,k_1)\) is scheduled before \((j_2,k_2)\) on their shared machine, \(0\) otherwise; indexed over conflict pairs \(P\) |
binary |
|
|
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 \((j_1,k_1)\) precedes \((j_2,k_2)\) 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 \((j_2,k_2)\) precedes \((j_1,k_1)\) 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.
Formulation c (valid)¶
Note
This is the JSSP formulation from
v1of Yazdani et al. [2] augmented with acceleration cut EC2, which is unchanged inv2.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of jobs |
integer |
scalar |
|
Number of machines |
integer |
scalar |
|
Processing time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
Machine index assigned to the \(k\)-th operation of job \(j\) |
integer |
|
Definitions¶
Name |
Description |
Formulation |
|---|---|---|
|
Set of conflict pairs: all \(((j_1,k_1),(j_2,k_2))\) with \(j_1 \neq j_2\) or \(k_1 \neq k_2\) 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)\}\) |
|
Big-M constant: sum of all processing times |
\(M = \sum_{j=0}^{n-1} \sum_{k=0}^{m-1} p_{j,k}\) |
|
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\}\) |
|
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\) |
|
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 |
|---|---|---|---|
|
Start time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
\(1\) if operation \((j_1,k_1)\) is scheduled before \((j_2,k_2)\) on their shared machine, \(0\) otherwise; indexed over conflict pairs \(P\) |
binary |
|
|
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 \((j_1,k_1)\) precedes \((j_2,k_2)\) 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 \((j_2,k_2)\) precedes \((j_1,k_1)\) 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.
Formulation d (valid)¶
Note
This is the JSSP formulation from
v2of Yazdani et al. [2] augmented with acceleration cut EC3.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of jobs |
integer |
scalar |
|
Number of machines |
integer |
scalar |
|
Processing time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
Machine index assigned to the \(k\)-th operation of job \(j\) |
integer |
|
Definitions¶
Name |
Description |
Formulation |
|---|---|---|
|
Set of conflict pairs: all \(((j_1,k_1),(j_2,k_2))\) with \(j_1 \neq j_2\) or \(k_1 \neq k_2\) 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)\}\) |
|
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 |
|---|---|---|---|
|
Start time of the \(k\)-th operation of job \(j\) |
continuous |
|
|
\(1\) if operation \((j_1,k_1)\) is scheduled before \((j_2,k_2)\) on their shared machine, \(0\) otherwise; indexed over conflict pairs \(P\) |
binary |
|
|
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 \((j_1,k_1)\) precedes \((j_2,k_2)\) 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 \((j_2,k_2)\) precedes \((j_1,k_1)\) 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.
Reformulations¶
Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.
a → b (valid)¶
Note
Formulation
bhas the same parameters as formulationa; the map is the identity.
Parameter map
Name |
Definition in terms of |
|---|---|
|
\(n = n\) |
|
\(m = m\) |
|
\(p_{ij} = p_{ij}\) |
|
\(Om_{ij} = Om_{ij}\) |
a → c (valid)¶
Note
Formulation
chas the same parameters as formulationa; the map is the identity.
Parameter map
Name |
Definition in terms of |
|---|---|
|
\(n = n\) |
|
\(m = m\) |
|
\(p_{ij} = p_{ij}\) |
|
\(Om_{ij} = Om_{ij}\) |
a → d (valid)¶
Note
Formulation
dhas the same parameters as formulationa; the map is the identity.
Parameter map
Name |
Definition in terms of |
|---|---|
|
\(n = n\) |
|
\(m = m\) |
|
\(p_{ij} = p_{ij}\) |
|
\(Om_{ij} = Om_{ij}\) |