# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Introduction to Petri Nets  
Before describing the automatic generation of the PN model of the JMPMSF, we formally introduce Petri Nets analogous to [17].  
**Definition 1** (Petri Net).: _A Petri Net is a tuple \(PN=(\mathbb{P},\mathbb{T},\mathbb{E},w,x^{0})\), where_  
* \(\mathbb{P}=\{P_{1},...,P_{n}\}\) _is a finite set of_ places_,_ \(n\in\mathbb{N}_{>0}\)_, graphically represented as circles,_
* \(\mathbb{T}=\{T_{1},...,T_{m}\}\) _is a finite set of_ transitions_,_ \(m\in\mathbb{N}_{>0}\)_, graphically represented as bars,_
* \(\mathbb{E}\subseteq(\mathbb{P}\times\mathbb{T})\bigcup(\mathbb{T}\times \mathbb{P})\) _is a set of_ arcs _from places to transitions and from transitions to places, graphically represented as arrows,_
* \(w:\mathbb{E}\rightarrow\mathbb{N}_{>0}\) _is an_ arc weight function_, graphically represented as numbers labeling the arcs (if an arc has the weight \(1\) it is not labeled) and_
* \(x^{0}\in\mathbb{N}^{n}\) _is the_ initial marking _of the Petri Net, from now on called_ initial state_; the initial state of a place \(P_{i}\) is graphically indicated by \(x^{0}_{i}\) dots (\"tokens\") in the circle corresponding to \(P_{i}\)._  
The dynamics of a PN is driven by the _firing_ of the transitions and captured by the evolution of the state vector \(x(k)\in\mathbb{N}^{n}\) at the time instants \(k\in\mathbb{N}\) and is initialized with \(x(0)=x^{0}\). The firing of a transition \(T\) removes tokens according to the weights \(w(P_{i},T)\) of the arcs \((P_{i},T)\in\mathbb{E}\) from its input places \(P_{i}\in\mathbb{P}\) and adds token to its output places \(P_{o}\in\mathbb{P}\) according to the weights \(w(T,P_{o})\) of the arcs \((T,P_{o})\in\mathbb{E}\). The number of times each transition fires at instant \(k\) is expressed with the _firing count vector_\(u(k)\in\mathbb{N}^{m}\). We introduce the incidence matrix \(B=B^{+}-B^{-}\) which is composed of the two matrices \(B^{+}\in\mathbb{N}^{n\times m}\) and \(B^{-}\in\mathbb{N}^{n\times m}\) that are defined as  
\[B^{+}_{i,j}:=\begin{cases}w(T_{j},P_{i})&if\ (T_{j},P_{i})\in\mathbb{E}\\ 0&else\end{cases}\qquad\qquad B^{-}_{i,j}:=\begin{cases}w(P_{i},T_{j})&if\ (P_{i},T_{j})\in\mathbb{E}\\ 0&else\end{cases}. \tag{1}\]  
We can now compactly describe the Petri Net dynamics by  
\[x(k+1)=x(k)+Bu(k),\qquad x(0)=x^{0}. \tag{2}\]  
As the places are not allowed to have a negative number of tokens, the Petri Net dynamics needs to be further restricted by only allowing transitions to fire if they do not generate negative tokens in any place. We say a transition \(T\) is _enabled_ at a state \(x(k)\) if all of its input places \(P_{i}\) connected through an arc \((P_{i},T)\in\mathbb{E}\) hold as least as many tokens as the arc weight \(w(P_{i},T)\), i.e., \(x_{i}\geq w(P_{i},T)\). Two transitions, \(T_{i}\) and \(T_{j}\), might be concurrently enabled at state \(x(k)\), but if they both fire simultaneously they would consume the same token resulting in a negative entry in the state vector \(x(k+1)\). This situation is called _conflict_ between the transitions \(T_{i}\) and \(T_{j}\)[39]. To prevent negative tokens in this case, a non-negativity condition on the basis of the firing count vector \(u(k)\) is introduced. With the matrix \(B^{-}\) and the state vector \(x(k)\) all allowed firing count vectors \(u(k)\) must satisfy the non-negativity constraint  
\[0\leq x(k)-B^{-}u(k). \tag{3}\]