# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Generation of the Discrete Time Petri Net Model
The number of production steps  
\[k_{\mathrm{P}}(M,\tau)=\left|\frac{\mathrm{tp}(M,\tau)}{\mathrm{t}_{\mathrm{s}}}\right| \tag{5}\]  
for the execution of the task \(\tau\) on the machine \(M\) is calculated with respect to the _sampling time_\(\mathrm{t}_{\mathrm{s}}\), which is also called _sampling period_. It is rounded to the next larger integer which means that for a large sampling time \(\mathrm{t}_{\mathrm{s}}\) the resulting production time \(\mathrm{t}_{\mathrm{p}}=k_{\mathrm{P}}\mathrm{t}_{\mathrm{s}}\) might be larger than the true production time \(\mathrm{t}_{\mathrm{p}}\), i.e., \(\mathrm{t}_{\mathrm{p}}\geq\mathrm{t}_{\mathrm{p}}\). ```
input :A set of machines \(\mathcal{M}\), a set of tasks \(\mathcal{T}\), a set of jobs \(\mathcal{J}\) output :A set of places \(\mathbb{P}\) marked with the initial states \(x^{0}\)
1 foreverymachine\(M\in\mathcal{M}\)do
2 Add an idle place \(P_{(M,0,0,I)}\) to \(\mathbb{P}\) holding one token;
3 end for
4 foreveryjob\(J\in\mathcal{J}\)do
5 Add the starting place \(P_{(0,0,J,S)}\) to \(\mathbb{P}\) holding one token;
6 foreverytask\(\tau\in\mathcal{T}\)do
7 Add an unmarked completion place \(P_{(0,\tau,J,C)}\) and a necessity place \(P_{(0,\tau,J,N)}\) holding one token to \(\mathbb{P}\);
8 foreverymachine\(M\in\mathcal{M}\)do
9 iftask\(\tau\in\mathcal{T}_{M}\)then
10 Add \(k_{\mathrm{P}}(M,\tau)\) unmarked production places \(P_{(M,\tau,J,P_{\mathrm{kp}})}\), \(\cdots\), \(P_{(M,\tau,J,P_{\mathrm{kp}}(M,\tau))}\)
11 end if
12
13 end for
14
15 end for
16
17 end for
```  
**Algorithm 1**Create Places [17]. Algorithm 1 generates the set of places \(\mathbb{P}\) for the Petri Net. First, in lines 1-3, the _idle places_\(P_{(M,0,0,I)}\), which indicate whether a machine is working or not, are created for all machines \(M\in\mathcal{M}\). As it is assumed that all machines are idle at initialization, the idle places are marked with one token. This token is consumed by every transition starting the execution of a task on the respective machine and returned once the production is finished. Due to this mechanism it is guaranteed that every machine only executes one task at a time and therefore respects Restriction (R6). In lines 4-14, the places for the statuses of the jobs \(J\in\mathcal{J}\) are created. Every job \(J\) has a _starting place_\(P_{(0,0,J,S)}\), initialized in line 5 with one token, indicating that the production of the respective job has not yet been started. Once the production of a job starts, its token is moved according to the production process. Despite the token is not labeled and it can not be said that it stays the \"same\" token, the machine at which the job is being processed or was processed last can be deduced from the identifiers and the markings of the production and buffer places related to it. Those places are created in line 10. For every machine \(M\) with \(\tau\in\mathcal{T}_{M}\), the _production places_\(P_{(M,\tau,J,P)}\), \(i=1\ldots k_{\mathrm{P}}(M,\tau)\) are created. They indicate at which machine \(M\) the task \(\tau\) of job \(J\) is executed and how far its execution already proceeded. At the end of line 10, the _buffer places_\(P_{(M,\tau,J,B)}\) are created. If a buffer place \(P_{(M,\tau,J,B)}\) is marked, this shows that the task \(\tau\) of the job \(J\) was processed on machine \(M\) at last and that the semi-finished product of the job \(J\) is currently in the output buffer of machine \(M\). By generating the production and buffer places for all possible machines that can execute each task, the selection of the machine that will eventually execute it is not predefined a priori and can be chosen during runtime. This structure enables the Flexibility (F1). In line 7, _necessity places_\(P_{(0,\tau,J,N)}\) and _completion places_\(P_{(0,\tau,J,C)}\) are created for all tasks \(\tau\in\mathcal{T}_{J}\)which indicate the production progress of the job \(J\). Besides that, the completion places are used to ensure that the precedence relations between the tasks are met and Restriction (R1) is respected.