# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 2 Problem Description
### Restrictions and Flexibility in the Scheduling Problem
Despite these restrictions, which are rather few compared with other scheduling problems in manufacturing, the production problem still has a lot of flexibility. As in most scheduling problems, the production of different products, i.e., different jobs, is considered to be independent. This is the case as the tasks in different jobs are independent from one another as specified in Restriction (R2). In line with [PERSON] and [PERSON] [24], we consider the interdependence between different jobs to be rare in practice. In our setup they only arise as the jobs are manufactured in the same production facility and share the same machine pool. In general, we consider as flexibility of a manufacturing system its ability to adapt, or to be adapted, as a response to changing external conditions [26]. An operator or operating system needs to have the possibility to exploit the flexibility in order to improve the system behavior with respect to some desired criteria as for example the efficiency and profitability of the manufacturing system. The most significant types of flexibility of the considered description of an FMS are  
* the possibility to execute the same task on different machines,
* the ability of one machine to execute different tasks,
* the possibility to change the sequence in which the tasks in one job are executed, only restricted by (R1),* the possibility to change the sequence in which different operations are executed on a machine,
* the possibility to execute different types of jobs in the same manufacturing system. More in-depth analyses of different types of flexibility in manufacturing were, among others, done by [PERSON] et al. (2016); [PERSON] and [PERSON] (2017); [PERSON] et al. (2018). In the search of a unified taxonomy they identified more than 50 different terms for various types of flexibility and there are different terms for the same type of flexibility as well as different meanings of the same terms ([PERSON] et al., 2017). This is why we do not set specific terms for the flexibilities (F1)-(F5), but rather refer to their numbers (F1)-(F5) when referring to the different types of flexibility. With respect to the taxonomy of [PERSON] and [PERSON] (2017), who distinguishes eleven types of flexibility, the manufacturing system described above offers routing flexibility (F1), machine flexibility (F2), operation flexibility (F3) and (F4), and process, product and production flexibility (F5). Implicitly, also material handling flexibility is assumed as the jobs can be transferred from one machine to another. The setup also allows for expansion flexibility, which allows to introduce new machines to the system, due to the automatic generation of the scheduling problem in Section 3.3. The benefit of the different types of flexibility is that they offer the potential to find an improved schedule with respect to a nominal one. On the other hand the complexity of the scheduling problem increases and it is harder to find an optimal solution ([PERSON] et al., 2017; [PERSON] et al., 2017). In fact, the considered problem is NP-hard as it is a generalization of the flexible job shop (FJS), which we will discuss in Section 2.3, and since the FJS is NP-hard itself ([PERSON] et al., 2017; [PERSON] et al., 2017; [PERSON] et al., 2017). Increasing the flexibility of the FJS makes a hard to solve problem even harder.