Flexible Flow Shop Pattern

Intent

A set of jobs is to be processed on a set of machines. There is a fixed number of stages and each job needs to be processed in each of the stages exactly once in a predetermined order, which is the same for all jobs. In each stage there are some number of identical machines that can process the job at this stage. Each machine can only ever process one job at a time.

Motivation

Flexible flow shop machine environments regularly occur in manufacturing.

Applicability

Necessary conditions: Elementary Scheduling Problem
Sufficient conditions: The necessary conditions and let $j_1 \in J_E$ be a job in the event log. For all $j_2 \in J_E$ and all $m\in M_E$ :
(a) Every job $j_2$ is processed on every machine at most once, so for all $h, i \in \{1, \dots, |ops^p(j_2)|\}$ such that $h \neq i$ : $\texttt{\#}_{\mbox{machine}}(op^p_h(j_2)) \neq \texttt{\#}_{\mbox{machine}} (op^p_i(j_2))$ .
(b) Every job $j_2$ consists of the same number of operations, so $|ops^p(j_2)| = |ops^p(j_1)|$ .
(c) Each machine belongs to exactly one stage and the order through the stages is the same for all jobs, so for all $i_1, i_2 \in \{1, \dots, |ops^p(j_2)|\}$ where $i_1 \neq i_2$ we have
$\texttt{\#}_{\mbox{machine}}(op^p_{i_1}(j_1)) \neq \texttt{\#}_{\mbox{machine}}(op^p_{i_2}(j_2))$ .

Participants

A set of jobs consisting of operations, and a set of machines partitioned into stages.

Collaborations

The machines are partitioned into stages. Each job has to be processed on one machine of each stage exactly once in a predetermined order of the stages, which is the same across all jobs.

Diagram

Gantt chart showing four jobs being processed in three stages, where machines 1 and 2 belong to stage 1, machine 3 belongs to stage 2 and machines 4 and 5 belong to stage 3.

Consequences

Each operation belongs to a fixed and pedermined stage and can be processed on any of the (identical) machines belonging to this stage. Each job visits each stage exactly once and the order in which stages are visited by jobs is the same for all jobs.

Modelling variants

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

Forces

Elementary Scheduling Pattern

Enables

Flow Shop Pattern, Permutation Pattern, 1-Blocking Pattern

Compatible with

No Wait Pattern, Machine Setup Pattern, Distinguishable Resources Pattern, Indistinguishable Resources Pattern