# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Modified Petri Net Dynamics  
So far, we only introduced common notions for Petri Nets that can be found in literature, for example, in [39; 40]. However, in order to describe the scheduling problem introduced in Section 2, we will slightly adapt the role of the transitions as proposed in our previous work [17]. In most literature on Petri Nets, the firing of transitions is initiated by predefined rules, considered to be stochastic, or the dynamics is even seen as the set of all possible sequences in which the transitions can fire [39; 41]. In contrast to that, we will use a subset \(\mathbb{T}_{C}\subset\mathbb{T}\) of the transitions as controlled inputs to actively influence the dynamics of the Petri Net, which we will call _controlled part_ of the PN, and another subset \(\mathbb{T}_{I}\subset\mathbb{T}\) of the transitions is defined to fire as soon as they are enabled, which we will call _independent part_ of the PN. As discussed by [PERSON] and [PERSON] [42], the PN dynamics (2) is a special case of the dynamics of a linear discrete time system \(x(k+1)=Ax(k)+Bu(k)\) with \(A=I\), where \(I\) is the identity matrix of appropriate dimension. We will now exploit the possibility to change the matrix \(A\) such that it holds the influence of the so-called _independent transitions_ in the set \(\mathbb{T}_{I}\). The matrix \(B\) then merely considers the actively _controlled transitions_ in the set \(\mathbb{T}_{C}\) and the control decisions are captured in the firing count vector \(u\). Whether it is possible to represent the firing of a transition \"as soon as it is enabled\" and without violating the constraint (3) by means of a matrix multiplication \(Ax\) of the PN's state \(x\) with a matrix \(A\), depends on its interconnection with the rest of the PN. Therefore, we introduce two restrictions on the independent transitions. A transition \(T\) can only be considered to be independent if  
1. it only has one input place \(P_{i}\),
2. its only input place \(P_{i}\) has no second output transition,
3. the weight of the arc \((P_{i},T)\) connecting the place \(P_{i}\) to its output transition \(T\) must be \(w(P_{i},T)=1\). With those restrictions, only the basic Petri Net elements depicted in Figure 1, i.e., _sequence_, _merging_, and _splitting_, can be assigned to the independent part of the Petri Net, i.e., to the set \(\mathbb{T}_{I}\). On the other hand, _conflict_ and _synchronization_ depicted in Figure 2_must_ be controlled actively and the corresponding transitions always belong to the set \(\mathbb{T}_{C}\). This obviously also holds for the combination of synchronization and conflict in a so called _non free-choice conflict_[41]. With the distinction between independent transitions and controlled transitions, the Petri Net dynamics is described as  
\[x(k+1)=Ax(k)+Bu(k),\qquad x(0)=x^{0}. \tag{4}\]  
As the places must not hold a negative number of tokens, i.e., constraint (3) must still be satisfied, and as there always has to be an integer number of tokens, for the newly introduced dynamics matrix must hold \(A\in\mathbb{N}^{n\times n}\). The dynamics (4) together with the non-negativity constraint (3) is called _state space description_ or _state space form_ of the PN. If the output transition \(T_{i}\) of the place \(P_{i}\) is handled as an independent transition, the i-th column of the matrix \(A\) is changed, starting from an identity matrix \(I\) for a completely controlled PN. The input arc \((P_{i},T_{i})\) of transition \(T_{i}\) sets the diagonal entry to zero, i.e., \(A_{i,i}=0\), and the output arcs \((T_{i},P_{0})\) of the transition \(T_{i}\) introduce the weight \(w(T_{i},P_{0})\) in the entry \(A_{o,i}=w(T_{i},P_{o})\). If a place has no independent output transition, a one in the corresponding diagonal entry in \(A\) keeps its number of tokens constant when no controlled transition fires. **Example 1**. : _The matrices corresponding the the elementary PN structures in Figure 1 are_  
\[A_{(a)}= \begin{bmatrix}0&0\\ 1&1\end{bmatrix} ,\qquad\quad A_{(b)}=