# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 3 Problem Formulation  
A manufacturing system with \(n\) jobs from the set \(\mathcal{J}=\{1,2,\ldots,n\}\) and \(m\) machines from the set \(\mathcal{M}=\{1,2,\ldots,m\}\) is considered. Each job \(i\) has to be processed on all machines with \(p_{i}^{a}>0\) denoting the processing time of job \(i\) on machine \(a\). Moreover, for each machine \(a\), the values \(r_{a}\geq 0\) and \(d_{a}\geq r_{a}\) denote the minimal and maximal idle time, respectively. Thus, after completing the processing of one job and before starting the processing of the next one, machine \(a\) has to wait for time \(t\), such that \(t\geq r_{a}\) and \(t\leq d_{a}\). Each job has to be processed on machines in the order of increasing machine number: \(1\to 2\to\cdots\to m\). This order is fixed and represents the technological process. On the other hand, the order of the processing of jobs is the same for each machine and is a decision variable of the problem. This order is described by \(n\)-element tuple \(\pi\) where the element \(\pi(i)\) denotes the job that is processed as \(i\)-th. Henceforth, \(\pi\) will be called the solution. Furthermore, a few additional constraints exist. Namely, at any given time, a job can be processed by at most one machine. Similarly, at any given time, a machine can process at most one job. Finally, the processing of jobs cannot be interrupted. From the solution \(\pi\), one can construct a schedule as the sequence \(S\):  
\[S=(S^{1},S^{2},\ldots,S^{m}), \tag{1}\]  
where \(S^{a}\) is in turn another sequence describing the starting time of jobs on machine \(a\):  
\[S^{a}=(S^{a}_{1},S^{a}_{2},\ldots,S^{a}_{n}). \tag{2}\]  
Thus, \(S^{a}_{i}\) is the starting time of job \(\pi(i)\) on machine \(a\). Similarly, one can define sequence \(C\) of the job completion times, such that \(C^{a}_{i}\) is the completion time of job \(\pi(i)\) on machine \(a\). For the simplicity of the notation value, \(\rho^{a}_{i}\) will be used as shorthand for \(p^{a}_{\pi(i)}\). As such, the schedule \(S\) is feasible if and only if all the following constraints are met:  
\[\forall a\in\mathcal{M}\ \ \forall i\in\mathcal{J} \ \ \ C^{a}_{i}=S^{a}_{i}+\rho^{a}_{i}, \tag{3}\] \[\forall a\in\mathcal{M}\setminus\{1\}\ \ \forall i\in\mathcal{J} \ \ \ S^{a}_{i}\geq C^{a-1}_{i},\] (4) \[\forall a\in\mathcal{M}\ \ \forall i\in\mathcal{J}\setminus\{1\} \ \ r_{a}\leq S^{a}_{i}-C^{a}_{i-1}\leq d_{a}. \tag{5}\]  
Constraint (3) ensures that the processing of jobs is not interrupted. Due to constraint (4), a job is completed on machine \(a-1\) before it starts processing on machine \(a\) (enforcing compliance with the technological process). Finally, constraint (5) ensures that jobs on machine \(a\) are processed in the order given by solution \(\pi\) and that the minimum and maximum idle times \(r_{a}\) and \(d_{a}\) on machine \(a\) are respected. It should be noted that due to (3), both \(S\) and \(C\) can unambiguously describe the schedule. A possible method of constructing schedule \(C\) from solution \(\pi\) is described by Algorithm 1. The method is nearly identical to the one shown for the non-permutation variant of the problem in [23]. In line 1, the completion time for processing job \(\pi(1)\) on machine 1 is set, since that job has no constraints. In lines 2-3, the completion times for the remaining jobs on machine 1 in order from \(\pi(2)\) to \(\pi(n)\) are set. Since there is no previous machine and \(d_{a}\geq r_{a}\), only the constraint (3) and the left side of constraint (5) have to be met. In lines 4-9, the completion times on the remaining machines are calculated, always finishing the calculations on machine \(a-1\) before moving to machine \(a\). Lines 5-7 are similar to lines 1-3, except the completion time of the same job from the previous machine (terms \(C_{1}^{a-1}\) and \(C_{i}^{a-1}\)) is also taken into account. After this, all constraints on machine \(a\) are met except for the right side of constraint (5).