# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 2 Literature Overview
### Problem Constraints  
Additional problem constraints are common for scheduling problems. The focus will be on problem constraints that include additional dependencies between the starting or completion times of jobs. First, some authors consider a constraint that forbids starting of a job on any machine before a designated time. Such a constraint is referred to as \"ready times\", \"release times\" or \"arrival times\" [26; 27]. Ready times are common constraints for scheduling on parallel machines [28] and online scheduling [19]. Conversely, the time by which the entire job is expected to be finished, prevalent in construction and civil engineering projects, is commonly called the \"due date\" or \"deadline\" [29; 30; 31].  
The next class of constraints are dependencies between the completion of a job on one machine and the starting time of the same job on the next machine, commonly called \"wait times\". Two sub-variants are \"no-wait\", where the starting time on the next machine is the same as the completion time on the previous machine [32; 33; 34; 35] and \"limited wait\", where there is a maximal allowed time before completion and starting on the next machine [27; 36]. Some papers also consider both minimal and maximal wait times, sometimes referred to as \"time lag\" [37; 38]. Another type of constraint is the time required to move the job to the next machine, called the \"transportation time\" [12; 39]. It is often used with certain types of manufacturing systems, e.g., ones employing automated guided vehicles (AGVs).  
Another group of constraints are dependencies between the completion time of a job on some machine and the starting time of the next job on the same machine. Some very common examples are \"setups\" or \"changeovers\". Setups usually represent the time needed to change the setting of the machine and let it cool down or load the next item. In the simplest form, the setup time depends only on the job that follows it. Such a setup can simply be modeled by extending the processing time of the job. However, it is more common to consider sequence-dependent setup times (SDSTs), where the setup time is dependent on the duration of both the next and previous job [12; 13; 40].  
In general, the time between the processing of subsequent jobs on the same machine is called \"idle time\". Similarly to wait times, several sub-variants of this constraint exist. The \"no-idle\" variant [41; 42; 43] allows for the maximization of machine utility. This can be useful when the machine cannot be turned off readily or without additional costs. It should also be noted that, while it is rare, it is possible to apply both no-wait and no-idle constraints at the same time [44]. Another type is \"minimal idle\"-though in practice this is modeled similarly to setups. Similarly, a \"limited idle\" or \"maximal idle\" time can be imposed as well [15]. Finally, both the minimal and maximal idle time constraints can be enforced at the same time. This can be used to model some time-sensitive processes in construction, for example, the concreting process [23].