p8 | Job Shop Scheduling Problem (JSSP)

See also

This problem is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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} \]