# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 3 Model Generation
### Generation of the Discrete Time Petri Net Model
First, for every task \(\tau\in\mathcal{T}_{\hat{J}}\) of the new job it is investigated whether a smallest sufficient prediction horizon \(N_{O}/N_{O}^{+}\) of the operation \(O=(\tau,\hat{J})\) can be found. If this is the case for all operations, a smallest sufficient prediction horizon \(N_{\hat{J}}/N_{\hat{J}}^{+}\) of the new job can be computed according to Corollary 2. If this is smaller than the existing smallest sufficient prediction horizon \(N_{\min}/N_{\min}^{+}\), the convergence properties are preserved despite the new job. If \(N_{\hat{J}}/N_{\hat{J}}^{+}\) is lager, the smallest sufficient prediction horizon can be adjusted accordingly. If necessary, the prediction horizon \(N\) or the extended prediction horizon \(N^{+}\) needs to be extended to restore the convergence guarantee despite the new job. The most challenging part in providing the convergence guarantees is certainly to determine the shortest sufficient prediction horizon \(N_{O}/N_{O}^{+}\), as for all states \(x^{O,S}\in\mathbb{X}_{O,S}\) a corresponding state \(x^{O,C}\in\mathbb{X}_{O,C}\) satisfying condition (8) needs to be found. Only then a value for \(N_{O}/N_{O}^{+}\) can be computed based on the pair \((x^{O,S},x^{O,C})\). By exploiting Properties (P4), (P5) and (P8), the state \(x^{O,C}\) can be characterized based on the state \(x^{O,S}\) and the transitions in the PN description, as described in [18]. With this characterization, condition (8) can be expressed solely based on the steady state \(x^{O,S}\) and an input vector \(u_{T}\in\mathbb{U}_{O,S}\), which only fires a single starting transition, without the need to determine the set \(\mathbb{X}_{O,C}\)

\[\text{subset to} x\big{(}\bar{k}+1|k\big{)}=Ax\big{(}\bar{k}|k\big{)}+Bu\big{(} \bar{k}|k\big{)}\]1

Despite the slightly more restricting definition of the set \(\mathbb{X}_{O,S}\) in Definition 2 compared with [18], it might still be too large in practice such that it is practically impossible to check all conditions to prove the completion of a single operation. To make this endeavor feasible, we provided a condition for the case of a linear cost function \(c(x,u)=c_{x}^{\top}x+c_{u}^{\top}u\) in our previous work [18]. This is done by exploiting Property (P4) and the linearity of the cost function and thereby reducing the number of conditions to be investigated. For a given transition \(T\), there are many possible steady states \(x^{O,S}\in\mathbb{X}_{O,S}\) in which an input \(u_{T}\in\mathbb{U}_{O,S}\) firing only the transition \(T\) can be applied without violating the non-negativity constraint (3). With the result in [18], instead of investigating all steady states \(x^{O,S}\in\mathbb{X}_{O,S}\), only one condition needs to be checked for each transition \(T\) with \(u_{T}\in\mathbb{U}_{O,S}\) and thereby number of conditions to check is significantly reduced. Due to linearity of the cost function, condition (19) reduces to

\[\text{subset to} x\big{(}\bar{k}+1|k\big{)}=Ax\big{(}\bar{k}|k\big{)}+Bu\big{(} \bar{k}|k\big{)}\]2

If this condition holds for at least one input \(u_{T}\in\mathbb{U}_{O,S}\), Theorem 1 and Corollary 1 can be used to conclude the existence of a smallest sufficient prediction horizon \(N_{NP-hard. They are finite horizon approximations of the overall optimization problem that solves the whole scheduling problem until completion and therefore less computationally expensive. Nevertheless, their solution space still grows exponentially with the number of jobs and alternative machines. Thus, the computation of the optimal input trajectory \(u^{*}(\cdot|k)\) is computationally demanding. However, this optimization problem does not need to be solved completely in every time step. On the one hand, the last \(N-1\) steps of the solution computed at time step \(k\) can be used as the first \(N-1\) steps of a candidate solution at time step \(k+1\) as it is common in MPC [14].