# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 4 A Literature Review and Closed Results
### Closed Results
: _If \(\mathcal{J}=\mathcal{J}^{*}\cup\mathcal{J}^{1}\cup\mathcal{J}^{2}\), then there exists a \(J\)-solution \(S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) such that \(\pi^{\prime}\in\Pi(\mathcal{G})\) for all pairs of job permutations, \(\{(\pi^{\prime},\pi^{\prime})\}\in S(T)\)._  
In Reference [42], it was studied how to construct a minimal dominant set \(S(T)=\{(\pi^{\prime},\pi^{\prime})\}\), \(\pi^{\prime}\in\Pi(\mathcal{G})\). Two types of redundant permutations were examined, and the following claim was proven. **Lemma 1**. : _Let \(\mathcal{J}=\mathcal{J}^{*}\cup\mathcal{J}_{1}\cup\mathcal{J}_{2}\). If permutation \(\pi_{t}\in\Pi(\mathcal{G})\) is redundant in the set \(\Pi(\mathcal{G})\), then \(\pi_{t}\) is a redundant permutation either of type 1 or type 2._  
Testing whether set \(\Pi(\mathcal{G})\) contains a redundant permutation of type 1 takes \(O(n^{2})\) time, and testing whether permutation \(\pi_{g}\in\Pi(\mathcal{G})\) is a redundant permutation of type 2 takes \(O(n)\) time. In Reference [42], it is shown how to delete all redundant permutations from the set \(\Pi(\mathcal{G})\). Let \(\Pi^{*}(\mathcal{G})\) denote a set of permutations remaining in the set \(\Pi(\mathcal{G})\) after deleting all redundant permutations of type 1 and type 2. **Theorem 6**. : _Assume the following condition:_  
\[\max\{l_{i,3-k},l_{j,3-k}\}<l_{ik}=u_{ik}=l_{jk}=u_{jk}<\min\{u_{i,3-k},u_{j,3- k}\}. \tag{6}\]  
_If set \(\mathcal{J}=\mathcal{J}^{*}\cup\mathcal{J}^{1}\cup\mathcal{J}^{2}\) does not contain a pair of jobs \(J_{i}\in\mathcal{J}^{k}\) and \(J_{j}\in\mathcal{J}^{k},k\in\{1,2\},\) such that the above condition holds, then \(S(T)=<\Pi^{*}(\mathcal{G}),\Pi^{*}(\mathcal{G})>\)._  
To test conditions of Theorem 6 takes \(O(n)\) time. Due to Theorem 6 and Lemma 1, if there are no jobs such that condition (6) holds, then a \(J\)-solution can be constructed via deleting redundant permutations from set \(\Pi(\mathcal{G})\). Since the set \(\Pi^{*}(\mathcal{G})\) is uniquely determined [42], we obtain Corollary 2. **Corollary 2** ([42]). : _If set \(\mathcal{J}=\mathcal{J}^{*}\cup\mathcal{J}^{1}\cup\mathcal{J}^{2}\) does not contain a pair of jobs \(J_{i}\) and \(J_{j}\) such that condition (6) holds, then the binary relation \(\mathcal{A}_{<}\) determines a unique \(J\)-solution \(S(T)=<\Pi^{*}(\mathcal{G}),\Pi^{*}(\mathcal{G})>\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\)._  
The condition of Theorem 6 is sufficient for the uniqueness of a \(J\)-solution \(\Pi^{*}(\mathcal{G})=S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\). Due to Theorem 1, one can construct a digraph \(\mathcal{G}=(\mathcal{J},\mathcal{A}_{<})\) in \(O(n^{2})\) time. The digraph \(\mathcal{G}=(\mathcal{J},\mathcal{A}_{<})\) determines a set \(S(T)\) and may be considered a condensed form of a \(J\)-solution for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\). The results presented in this section are used in Section 5 for constructing precedence digraphs for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\).