# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 4 A Literature Review and Closed Results
### Closed Results  
Since each permutation \(\pi^{\prime}\) uniquely determines a set of the earliest completion times \(C_{i}(\pi^{\prime})\) of the jobs \(J_{i}\in\mathcal{J}\) for the problem \(F2||C_{max}\), one can identify the permutation \(\pi^{\prime}\), \(((\pi^{\prime},\pi^{\prime})\in S)\), with the semi-active schedule [1; 25; 26] determined by the permutation \(\pi^{\prime}\). Thus, the set \(S\) becomes a set of \(n!\) pairs \((\pi^{\prime},\pi^{\prime})\) of identical permutations of \(n=m_{1,2}\) jobs from the set \(\mathcal{J}=\mathcal{J}_{1,2}\) since the order forprocessing jobs \(\mathcal{J}_{1,2}\) on both machines may be the same in the optimal schedule [28]. Therefore, the above Definition 1 is supplemented by the following remark. **Remark 2**. : _For the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) considered in this section, it is assumed that a \(J\)-solution \(S(T)\) is a minimal dominant set of [PERSON]'s permutations of all jobs from the set \(\mathcal{J}_{1,2}\), i.e., for each scenario \(p\in T\), the set \(S(T)\) contains at least one optimal pair \((\pi_{k},\pi_{k})\) of identical [PERSON]'s permutations \(\pi_{k}\) such that the inequality in Equation (1) holds._  
In Reference [36], it is shown how to delete redundant pairs of (identical) permutations from the set \(S\) for constructing a \(J\)-solution for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}=\mathcal{J}_{1,2}\). The order of jobs \(J_{v}\in\mathcal{J}_{1,2}\) and \(J_{w}\in\mathcal{J}_{1,2}\) is fixed in the \(J\)-solution if there exists at least one [PERSON]'s permutation of the form \(\pi_{k}=(s_{1},J_{v},s_{2},J_{w},s_{3})\) for any scenario \(p\in T\). In Reference [29], the sufficient conditions are proven for fixing the order of two jobs from set \(\mathcal{J}=\mathcal{J}_{1,2}\). If one of the following conditions holds, then for each scenario \(p\in T\), there exists a permutation \(\pi_{k}=(s_{1},J_{v},s_{2},J_{w},s_{3})\) that is a [PERSON]'s one for the problem \(F2|p|C_{max}\) associated with scenario \(p\):  
\[u_{p1}\leq l_{v2}\text{ and }u_{w2}\leq l_{w1}, \tag{3}\]  
\[u_{p1}\leq l_{v2}\text{ and }u_{v1}\leq l_{w1}, \tag{4}\]  
\[u_{w2}\leq l_{w1}\text{ and }u_{w2}\leq l_{v2}. \tag{5}\]  
If at least one condition in Inequalities (3)-(5) holds, then there exists a \(J\)-solution \(S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with fixed order \(J_{v}\to J_{w}\) of jobs, i.e., job \(J_{v}\) has to be located before job \(J_{w}\) in any permutation \(\pi_{i}\), \((\pi_{i},\pi_{i})\in S(T)\). If both conditions in Inequalities (4) and (5) do not hold, then there is no \(J\)-solution \(S(T)\) with fixed order \(J_{v}\to J_{w}\) in all permutations \(\pi_{i}\), \((\pi_{i},\pi_{i})\in S(T)\). If no analogous condition holds for the opposite order \(J_{w}\to J_{v}\), then at least one permutation with job \(J_{v}\) located before job \(J_{w}\) or that with job \(J_{w}\) located before job \(J_{v}\) have to be included in any \(J\)-solution \(S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\). Theorem 1 is proven in Reference [41]. **Theorem 1**. : _There exists a \(J\)-solution \(S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with fixed order \(J_{v}\to J_{w}\) of the jobs \(J_{v}\) and \(J_{w}\) in all permutations \(\pi_{k}\), \((\pi_{k},\pi_{k})\in S(T)\) if and only if at least one condition of Inequalities (4) or (5) holds._  
In Reference [41], the necessary and sufficient conditions have been proven for the case when a single-element \(J\)-solution \(S(T)=\{(\pi_{k},\pi_{k})\}\) exists for the problem \(F2|l_{jm}\leq p_{jm}\leq u_{jm}|C_{max}\).