# Model Predictive Control for Flexible Job Shop Scheduling in Industry 4.0 +
## 2 Problem Description
### Restrictions and Flexibility in the Scheduling Problem  
In the considered scheduling problem, there are restrictions concerning the three basic elements, i.e., tasks, machines, and jobs. To begin with, the sequence of tasks in a job is generally free. However, as there might be dependencies between the different steps in the production process of a product, these dependencies needs to be considered in the manufacturing problem such that only production sequences are scheduled which can be executed in the real production process. This is achieved through the following four restrictions in the scheduling problem related to the tasks:* A task \(\tau\) might not be independent, but require all tasks \(\tau^{\prime}\in\mathcal{T}_{\tau}\) in the set of its required tasks \(\mathcal{T}_{\tau}\subset\mathcal{T}\) to be finished before it can be started. * A task \(\tau\in\mathcal{T}_{j}\) in a job \(J\) can only depend on tasks \(\tau^{\prime}\in\mathcal{T}_{j}\) in the same job \(J\), i.e., \(\mathcal{T}_{\tau}\subset\mathcal{T}_{j}\) for every task \(\tau\in\mathcal{T}_{j}\). If a task \(\tau\) depends on another task \(\tau^{\prime}\), i.e., \(\tau^{\prime}\in\mathcal{T}_{\tau}\), \(\tau\in\mathcal{T}_{j}\), then the operations \(O=(\tau,J)\) and \(O^{\prime}=(\tau^{\prime},J)\) exist and it is said that \(O\) depends \(O^{\prime}\). Operations \(O=(\tau,J)\) and \(\tilde{O}=(\tau^{\prime},\tilde{J})\) in different jobs \(J\) and \(\tilde{J}\) are independent from one another. * Two tasks \(\tau\) and \(\tau^{\prime}\) must not be mutually dependent. * Preemption of tasks is not allowed, i.e., once a task has been started it must be completed without interruption. The restriction to a non-preemptive setup is the general case in literature and therefore adopted in the considered problem [19; 20; 21; 22; 23]. In the description of the dependencies of a task \(\tau\) on other tasks (R1), only _direct_ dependencies are provided in the sets \(\mathcal{T}_{\tau}\). Indirect dependencies with one or more other tasks in between can be recursively determined with an algorithm presented in our previous work [17]. The set of all tasks on which a task \(\tau\) depends directly or indirectly is denoted with \(\mathcal{T}_{\tau}\). From the different sets \(\mathcal{T}_{\tau}\) of the tasks \(\tau\in\mathcal{T}_{j}\) of a job \(J\), a precedence graph \(G_{J}=(\mathcal{T}_{j},E_{J})\) can be generated to represent the relations between the tasks of the job by considering the tasks \(\tau\in\mathcal{T}_{j}\) as nodes and constructing the directed edges \(E_{J}=\{(\tau^{\prime},\tau)|\tau^{\prime}\in\mathcal{T}_{\tau},\tau\in \mathcal{T}_{j}\}\) according to the precedence relations in the sets \(\mathcal{T}_{\tau}\). Due to Restriction (R3), this graph is acyclic, which is important as otherwise none of the tasks in a cycle could ever start due to a circular wait condition. To summarize, all precedence relations that can be represented by an arbitrary acyclic graph can be considered in the scheduling problem, as it is the case for some closely related scheduling problems [24; 25]. Furthermore, the machines and jobs are restricted in the real-world production process. Every machine has a limited production capacity, which we assume to be one for simplicity, and we assume that every machine has an infinite output buffer. For the jobs, we assume that they represent products that can only be at one place, and thus they can only be handled by a single machine at a time. Together with the limited capabilities of the machines, the following restrictions are present, which are all the general case in the literature on scheduling of FJSs, despite they are not always stated explicitly [19; 20; 21; 23]:  
* Every machine \(M\) can only execute a subset of tasks, which is specified as \(\mathcal{T}_{M}\ \subset\ \mathcal{T}\). * A machine can only execute one task at a time. * Only one task per job can be executed at a time.