# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 2 Problem Description
### Classification of the Scheduling Problem  
A common classification of scheduling problems was introduced by [PERSON] et al. [31] and further refined as then [15; 30; 32]. It systematically categorizes various scheduling problems by their machine environment, their job characteristics and their optimality criterion. For the classification of the problem at hand we mainly focus on the machine environment, since the job characteristics in the sense of the classification scheme are not completely specified and the optimality criterion can be arbitrary, except for the properties required for the proofs in Section 4.  
According to this classification scheme, the machine environment of the scheduling problem described above can be classified as a generalization of the most common specification of the flexible job shop (FJS) [21] and at the same time as a generalization of the partial job shop (PJS) [24]. The FJS as well as the PJS generalize the ordinary job shop (JS) [15], which restricts the problem formulation above in two ways. First, every task can only be executed by one distinct machine, i.e., it does not offer machine flexibility (F1). Secondly, every job has a predefined process plan in the form of a fixed sequence in which the tasks of the job have to be executed, i.e., it does not offer sequence flexibility (F3).  
There is a large amount of literature on the FJS and it is not always defined in the exactly the same way [20; 21; 23]. The most common specification introduces machine flexibility (F1) with respect to the ordinary JS by allowing every task to be executed by multiple machines and is also called job shop with multipurpose machines (JMPM) [15]. In a more restrictive definition by [PERSON] [30] the FJS consists of distinct work centers with identical parallel machines. The sequence flexibility (F3) is not introduced and the tasks of every job have a predetermined sequential order in which they have to be executed [21; 33].  
In the PJS, which was introduced by [PERSON] and [PERSON] [24] and is rarely considered in literature [34], sequence flexibility (F3) was introduced with respect to the ordinary, non-flexible JS. The fixed sequence of tasks in a job is relaxed such that arbitrary precedence relations in the form of an acyclic graph are allowed. The machine flexibility (F1) to choose on which machine a certain operation will be executed is not available in the PJS.  
In order to arrive at an understandable denomination that speaks for itself, we follow the definition of the JMPM and categorize the machine environment in our scheduling problem as _job shop with multipurpose machines and sequence flexibility (JMPMSF)_. It combines the two types of flexibilities (F1) and (F3) that were introduced in the JMPM and the PJS, respectively, with respect to the ordinary JS. In the literature no unique name was given to the JMPMSF. Among other names, it is called _extended FJS_[25], or _FJS with process plan flexibility_[35]. [PERSON] et al. [25] and [PERSON] et al. [35] present two different mixed integer linear programming (MILP) models to find a schedule that minimizes the makespan of a JMPMSF. Due to its complexity, however, it is mostly solved by means of heuristic approaches [16; 29; 36]. Its practical relevance was shown by [PERSON] et al. [37] who consider a JMPMSF from online printing industry that is subject to additional challenges. Theypresent a MILP and a constraint programming model for it, after providing a concise literature review on the JMPMSF.