Job Shop Pattern

Intent

A set of jobs is to be processed on a set of machines. Each job is to be processed on a subset of the machines in a predetermined order which might be different between the jobs.

Motivation

Job shop machine environments regularly occur in manufacturing scenarios.

Applicability

Sufficient conditions: For all $j\in J_E$ and all $m\in M_E$ , the following sufficient conditions must hold:
(a) Jobs cannot be processed without a machine, so for all
$\hspace{5mm} i \in \{1, \dots, |ops^p(j)|\}$ : $\texttt{\#}_{\mbox{machine}}(op^p_i(j)) \neq \bot$ .
(b) No two operations of a job $j$ can be processed at the same time, so for all $i \in \{1, \dots, |ops^p(j)|-1\}$ : $\texttt{\#}_{\mbox{end}}(op^p_i(j)) \leq \texttt{\#}_{\mbox{start}}(op^p_{i+1}(j))$ .
(c) No machine can process two operations at the same time,
so for all $i \in \{1,\dots, |\mathfrak{ops}^p(m)|-1\}$ : $\texttt{\#}_{\mbox{end}}(\mathfrak{op}^p_i(m)) \leq \texttt{\#}_{\mbox{start}}(\mathfrak{op}^p_{i+1}(m))$ .
(d) Each activity occurs on a fixed machine, so for all $j_2 \in J_E$ and all $i_1 \in \{1, \dots, |ops^p(j)|\}$ and $i_2 \in \{1, \dots, |ops^p(j_2)|\}$ : if $\texttt{\#}_{\mbox{activity}}(op^p_{i_1}(j)) = \texttt{\#}_{ \mbox{activity}}(op^p_{i_2}(j_2))$ then $\texttt{\#}_{\mbox{machine}}(op^p_{i_1}(j)) = \texttt{\#}_{\mbox{machine}}(op^p_{i_2}(j_2))$

Participants

A set of jobs consisting of operations, and a set of machines.

Collaborations

Each operation of a job has to be processed on a predetermined machine. The operations of a job have to be processed in a predetermined order. The operations and route through the machines can differ between jobs.

Diagram

Gantt chart showing four jobs being processed on three machines:

Consequences

The machine on which each operation is to be processed is predetermined and fixed.

Modelling variants

(1) OPL for Cplex CP Download
(2) MiniZinc Download

Forces

Scheduing Problem Pattern

Enables

Flow Shop Pattern, No Wait Pattern

Compatible with

Machine Setup Pattern, Distinguishable Resources Pattern, Indistinguishable Resources Pattern

Search Strategies

Makespan optimisation: Set start times by choosing the job that can start earliest and setting it to that time. If the total end time is not fixed, we set it to its minimal possible value.