# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Generation of the Discrete Time Petri Net Model
If no precedence relation between the tasks \(\tau\) and \(\tau^{\prime}\) is present, both transitions \(T_{(M,M^{\prime},\tau,\tau^{\prime},J,S)}\), starting \(\tau^{\prime}\) after \(\tau\), and \(T_{(M^{\prime},M,\tau^{\prime},\tau,J,S)}\), starting \(\tau\) after \(\tau^{\prime}\), are present in the PN. It is guaranteed that only one of them can fire since each of them requires a token at the buffer place after the execution of the respective other task. Without sequence flexibility, the if-statement in line 13 of Algorithm 2 would only be true for the single task \(\tau^{\prime}\) that follows after the task \(\tau\), leading to a single starting transition of \(\tau^{\prime}\) and recovering the given production sequence. Furthermore, the necessity places and completion places created in line 7 of Algorithm 1 would be obsolete in this special case. The presented mechanism of creating a Petri Net model for a scheduling problem is not unique. With similar algorithms, further mechanisms and properties of a manufacturing system can be represented, as, for example, a limited buffer at every machine, production capacities of the machines larger than one, or maintenance tasks that are represented by transitions that are not related to any job. The automatically created Petri Net and the resulting mixed integer programming model is not the smallest one that would be possible for the given _JMPMSF_. For example, the size of the state vector could be reduced by summarizing all the buffer places \(P_{(M,\tau_{i},J,B)}\) for the different tasks \(\tau_{i}\in\mathcal{T}_{I}\) of the same job 1 that can be executed at the same machine \(M\) into one buffer place \(P_{(M,0,J,B)}\). By that, however, the information which task in job 1 was executed last is removed from the state of the PN. ## 4 Model Predictive Control

On the basis of the state space description of the automatically generated Petri Net, we will now develop two similar scheduling schemes for the job shop with multipurpose machines and sequence flexibility (JMPMSF) based on Model Predictive Control (MPC). One of them was first described and analyzed in our previous work [18], and the other one is a more efficient adaption thereof. Although they are specifically designed for JMPMSFs as defined in Section 2, they are exemplary for arbitrary scheduling problems formulated as a PN of the form introduced in Section 3.2. Using systems and control theory to analyze and influence PNs is not uncommon in the literature [41; 42], and also MPC techniques are used [43; 44; 45]. In the context of MPC for PNs, usually either continuous or hybrid PNs are considered from the start, or _fluidification_ of the Petri Net is used, meaning that the integer constraint is relaxed and the tokens are considered to be a fluid. Instead of a state \(x\in\mathbb{N}^{n}\) and a firing count vector \(u\in\mathbb{N}^{m}\), a state \(\tilde{x}\in\mathbb{R}^{n}_{\geq 0}\) and a _flow_ vector \(\tilde{u}\in\mathbb{R}^{m}_{\geq 0}\) are considered. This relaxation is used to avoid a high dimensional state space and simplify the problem [43; 45]. It is known that this adaptation changes the properties of the PN and that it is mostly suited for models with a large number of tokens [46; 47]. In our particular case, it violates the notion of the production problem defined in Section 2. In order to illustrate this, let us only consider a starting transition that fires by a non-integer amount smaller than one, e.g., \(\tilde{u}(0)\in(0,1)\) at instant \(k=0\). This would mean that a task is only partially started and therefore also only partially executed through the independent part of the PN dynamics (4) with \(\tilde{u}(k)=0\) for \(k>0\). The result is a partially completed task. Although it is not completely equivalent, this is comparable to the violation of Restriction (R4), i.e., that a task must not be interrupted, as an interruption would also lead to a partially completed task.