# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 5 Properties of the Optimal Pairs of Job Permutations
### An Algorithm for Checking Conditions for the Existence of a Single-Element Dominant Set  
We describe Algorithm 1 for checking the existence of an optimal permutation for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) if the partial strict order \(A^{1,2}_{\prec}\) on the set \(\mathcal{J}_{1,2}\) has the following form: \(J_{1}\prec\ldots\prec J_{k}\prec\{J_{k+1},J_{k+2},\ldots,J_{k+r}\}\prec J_{k +r+1}\prec\ldots\prec J_{m_{1,2}}\). Algorithm 1 considers a set of conflict jobs and checks whether the sufficient conditions given in Section 5.2 hold. For a conflict set of jobs, it is needed to construct two permutations and to check the condition in Inequality (12) for the first permutation and the condition in Inequality (13) for the second one. If at least one of these conditions holds, Algorithm 1 constructs a permutation which is optimal for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with any scenario \(p\in T\). Obviously, testing the conditions of Theorems 11 and 12 takes \(O(r)\), where the conflict set contains \(r\) jobs. The construction of the permutation of \(r\) jobs takes \(O(r\log r)\). Therefore, the total complexity of Algorithm 1 is \(O(r\log r)\). **Remark 3**. : _If Algorithm 1 is completed at Step 7 (STOP 1), we suggest to consider a set of conflict jobs \(\{J_{k+1},J_{k+2},\ldots,J_{k+r}\}\) and construct a [PERSON]'s permutation for the deterministic problem \(F2|p^{\prime}|C_{max}\) with job set \(\mathcal{J}^{\prime}=\{J_{k+1},J_{k+2},\ldots J_{k+r}\}\), where vector \(p^{\prime}=(p^{\prime}_{k+1,1},p^{\prime}_{k+1,2},\ldots p^{\prime}_{k+r,1},p^ {\prime}_{k+r,2})\) of the durations of conflict jobs \(\{J_{k+1},J_{k+2},\ldots J_{k+r}\}\) is calculated for each operation \(O_{ij}\) of the conflict job \(J_{i}\in\{J_{k+1},J_{k+2},\ldots J_{k+r}\}\) on the corresponding machine \(M_{j}\in\mathcal{M}\) as follows:_  
\[p^{\prime}_{ij}=(u_{ij}+l_{ij})/2 \tag{16}\]  
Theorem 11 and Theorem 12 imply the following claim. **Corollary 7**. : _Algorithm 1 constructs a permutation \(\pi^{*}\) either satisfying conditions of Theorem 11 or Theorem 12 (such permutation \(\pi^{*}\) is optimal for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and any scenario \(p\in T\)) or establishes that an optimal job permutation for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with any scenario \(p\in T\) does not exist._  
The set of jobs \(\mathcal{J}_{2,1}\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}=\mathcal{J}_{2,1}\) can be tested similarly to the set of jobs \(\mathcal{J}_{1,2}\). ```
Input: Segments \([l_{ij},u_{ij}]\) for all jobs \(J_{i}\in\mathcal{J}\) and machines \(M_{j}\in\mathcal{M}\), a partial strict order \(A^{1,2}_{\prec}\) on the set \(\mathcal{J}_{1,2}=\mathcal{J}^{*}_{1,2}\cup\mathcal{J}^{1}_{1,2}\cup\mathcal{J}^ {2}_{1,2}\) in the form \(J_{1}\prec\ldots\prec J_{k}\prec\{J_{k+1},J_{k+2},\ldots,J_{k+r}\}\prec J_{k+r+1} \prec\ldots\prec J_{m_{1,2}}\). Output: EITHER an optimal job permutation for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and any scenario \(p\in T\), (see STOP 0) OR three no permutation \(\pi_{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\), which is optimal for all scenarios \(p\in T\), (see STOP 1). Step 1: Set \(\delta_{s}=l_{k+s2}-u_{k+s,1}\) for all \(s\in\{1,2,\ldots,r\}\)  construct a partition of the set of conflicting jobs into two subsets \(X_{1}\) and \(X_{2}\), where \(J_{k+s}\in X_{1}\) if \(\delta_{s}\geq 0\), and \(J_{k+s}\in X_{2}\), otherwise.