# 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
Step 2: Construct a permutation \(\pi^{1}=(J_{1},J_{2},\ldots,J_{k},\pi_{1},\pi_{2},J_{k+r+1},\ldots,J_{m_{1,2}})\), where the permutation \(\pi_{1}\) contains jobs from the set \(X_{1}\) in the non-decreasing order of the values \(u_{k+i,1}\) and the permutation \(\pi_{2}\) contains jobs from the set \(X_{2}\) in the non-increasing order of the values \(l_{k+i,2}\), number jobs in the permutations \(\pi_{1}\) and \(\pi_{2}\) based on their orders. Step 3: IF for the permutation \(\pi^{1}\) conditions of Theorem 4.1 hold THENGOTO step 8. Step 4: Set \(\delta_{s}=l_{k+s1}-u_{k+s,2}\) for all \(s\in\{1,2,\ldots,r\}\)  construct a partition of the set of conflicting jobs into two subsets \(Y_{1}\) and \(Y_{2}\), where \(J_{k+s}\in Y_{1}\) if \(\delta_{s}\geq 0\), and \(J_{k+s}\in Y_{2}\), otherwise. Step 5: Construct a permutation \(\pi^{2}=(J_{1},J_{2},\ldots,J_{k},\pi_{2},\pi_{1},J_{k+r+1},\ldots,J_{m_{1,2}})\), where the permutation \(\pi_{1}\) contains jobs from the set \(Y_{1}\) in the non-increasing order of the values \(u_{k+i,2}\), and the permutation \(\pi_{2}\) contains jobs from the set \(Y_{2}\) in the non-decreasing order of the values \(l_{k+i,1}\), number jobs in the permutations \(\pi_{1}\) and \(\pi_{2}\) based on their orders. Step 6: IF for the permutation \(\pi^{2}\) conditions of Theorem 4.1 hold THENGOTO step 9. Step 7: ELSE there is no a single dominant permutation for 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\)STOP 1. Step 8: RETURN permutation \(\pi^{1}\), which is a single dominant permutation for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\)STOP 0. Step 9: RETURN permutation \(\pi^{2}\), which is a single dominant permutation for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\)STOP 0. ```  
**Algorithm 1**Checking conditions for the existence of a single-element dominant set of schedules for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\)  
In this section, we describe Algorithm 2 for constructing a small dominant set \(DS(T)\) of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). Algorithm 2 is developed for use at the off-line phase of scheduling (before processing any job from the set \(\mathcal{J}\)). Based on the initial data, Algorithm 2 checks the conditions of Theorem 4.1 for a single optimal pair of job permutations for the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). If the sufficient conditions of Theorem 4.1 do not hold, Algorithm 2 proceeds to consider the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{2,1}\). For each of these problems, the conditions of Theorem 4.1 are checked. If these conditions do not hold, then strict orders of the jobs \(\mathcal{J}\) based on Inequalities (4) and (5) are constructed. In this general case, Algorithm 2 constructs a partial strict order \(A^{1,2}_{\prec}\) of the jobs from set \(\mathcal{J}_{1,2}\) and a partial strict order \(A^{2,1}_{\prec}\) of the jobs from set \(\mathcal{J}_{2,1}\). Each of these partial orders may contain one or several conflict sets of jobs. For each such conflict set of jobs, Algorithm 2 checks whether the sufficient conditions given in Section 5.2 hold. Thus, if some sufficient conditions for a schedule optimality presented in Sections 4 and 5 are satisfied, then there exists a pair of permutations of jobs from set \(\mathcal{J}\) which is optimal for any scenario \(p\in T\). Algorithm 2 constructs such a pair of job permutations \(\{(\pi^{\prime},\pi^{\prime\prime})\}=DS(T)\). Otherwise, the precedence digraphs determining a minimal dominant set \(DS(T)\) of schedules is constructed by Algorithm 2.