# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Generation of the Discrete Time Petri Net Model
As the production problem is feasible due to Assumption 2, all operations can be executed and since it is finite due to Assumption 1, there is only a finite number of possible operations to be started, so eventually all operations had been started. Due to Property (P8) another steady state will be reached. As \(x^{F}\) is the only steady state for which the preconditions of Lemma 4 are not fulfilled, it is the only steady state in which the system can remain. The condition in Lemma 5 that there only exists a single final state \(x^{F}\) is more restrictive than necessary. In general, also for a fixed production problem there is a set \(\mathbb{X}_{F}\) of final states, in which no further production is possible and all jobs are completed. The convergence to this set can be shown with similar arguments. Having stated very general conditions when an MPC executes operations and ultimately completes the production problem, we will now formulate more specific conditions on the prediction horizon \(N\) and the cost function \(c(x,u)\) which guarantee the completion of an operation \(O=(\tau,J)\). As proposed in [18], we will use the cost function \(c(x,u)\) in the MPC problem (6) to determine a sufficiently long prediction horizon \(N_{O}\) to guarantee the completion of the operation \(O\) for all prediction horizons \(N\geq N_{O}\). In order to proof the finalization of every operation, we first define the sets \(\mathbb{X}_{O,S}\) and \(\mathbb{X}_{O,C}\) to classify the steady states in which an operation \(O\) can be started and the steady states in which it was just finished, respectively. **Definition 2** ([18]). : _For every \(O=(\tau,J)\) with \(\tau\in\mathcal{T}_{J},J\in\mathcal{J}\), the set \(\mathbb{X}_{O,S}\) is defined as the set of steady states in which the operation \(O\) can be directly started and which is reachable from the initial state of the production system \(x^{0}\) through a legal input trajectory._

**Definition 3** ([18]). : _For every \(O=(\tau,J)\) with \(\tau\in\mathcal{T}_{J},J\in\mathcal{J}\), the set \(\mathbb{X}_{O,C}\) is defined as the set of steady states right after the operation \(O\) was completed starting from a state \(x^{O,S}\in\mathbb{X}_{O,S}\) without executing any further task._

**Theorem 1** (Completion of an operation [18]). : _Given a Petri Net of a flexible manufacturing system in its state space form (3), (4) generated with the Algorithms 1 and 2 that fulfills the Assumptions 1 and 2. If for an operation \(O=(\tau,J)\) and a cost function \(c(x,u)\) holds that for every state \(x^{O,S}\in\mathbb{X}_{O,S}\) there exists a state \(x^{O,C}\in\mathbb{X}_{O,C}\) reachable from \(x^{O,S}\) with_

\[c(x^{O,S},0)>c(x^{O,C},0) \tag{8}\]

_then there exists a shortest sufficient prediction horizon \(N_{O}\in\mathbb{N}_{>0}\) with the property that for every \(N\geq N_{O}\) the operation \(O\) will eventually be executed when starting from any \(x^{0}\in\mathbb{X}_{O,S}\) and applying the optimal solution to the MPC problem (6) in closed loop (7)._Proof of Theorem 1.: As shown in Lemma 4, an optimal input trajectory \(u^{*}(\cdot|k)\) with the first predicted input \(u^{*}(0|k)\
eq 0\) is required such that some operation is started. In order to prove that the investigated operation \(O\) is started, we need to show that the closed loop system always enters a state in which the optimal input trajectory has an input \(u^{*}(0|k)\in\mathbb{U}_{O,S}\) as first planned input, where \(\mathbb{U}_{O,S}\) is the set of all input vectors \(u\) that start the execution of operation \(O\). _Part I:_

We only investigate the point in time when the operation \(O\) is started in this part of the proof. Therefore, we assume that the considered operation \(O=(\tau,J)\) is the _only_ operation that can be started and also the only one that needs to be executed in \(x^{O,S}\). For this case, we split all possible predicted trajectories into four categories and compare their resulting cost over the prediction horizon \(N\).