# 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
The more job pairs are involved in the binary relations \(A_{<}^{1,2}\) and \(A_{<}^{2,1}\), the more job permutations will be deleted from set \(S\) while constructing a \(J\)-solution \(S(T)\subseteq S\) for the problems \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job sets \(\mathcal{J}_{1,2}\) and \(\mathcal{J}_{2,1}\). ```
Input: Lower bounds \(l_{ij}\) and upper bounds \(u_{ij}\), \(0<l_{ij}\leq u_{ij}\), of the durations of all operations \(O_{ij}\) of jobs \(J_{i}\in\mathcal{J}\) processed on machines \(M_{j}\in\mathcal{M}=\{M_{1},M_{2}\}\). Output: EITHER pair of permutations \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}),(\pi_{2,1}, \pi_{2},\pi_{1,2}))\), where \(\pi^{\prime}\) is a permutation of jobs from set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{1}\cup\mathcal{J}_{2,1}\) on machine \(M_{1}\), \(\pi^{\prime\prime}\) is a permutation of jobs from set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{2}\cup\mathcal{J}_{2,1}\) on machine \(M_{2}\), such that \(\{(\pi^{\prime},\pi^{\prime\prime})\}=DS(T)\), (see STOP 0), OR permutation \(\pi_{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\) on machines \(M_{1}\) and \(M_{2}\) and a partial strict order \(A_{<}^{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\), OR permutation \(\pi_{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\) on machines \(M_{1}\) and \(M_{2}\) and a partial strict order \(A_{<}^{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\), OR a partial strict order \(A_{<}^{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\) and a partial strict order \(A_{<}^{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\), (see STOP 1). Step 1: Determine a partition \(\mathcal{J}=\mathcal{J}_{1}\cup\mathcal{J}_{2}\cup\mathcal{J}_{1,2}\cup \mathcal{J}_{2,1}\) of the job set \(\mathcal{J}\), permutation \(\pi_{1}\) of jobs from set \(\mathcal{J}_{1}\) and permutation \(\pi_{2}\) of jobs from set \(\mathcal{J}_{2}\), arrange the jobs in the increasing order of their indexes. Step 2: IF the first inequality in condition (7) of Theorem 7 holds THEN BEGIN  Construct a permutation \(\pi_{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\), arrange them in the increasing order of their indexes; IF the second inequality in condition (7) of Theorem 7 holds THEN construct a permutation \(\pi_{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\), arrange them in the increasing order of their indexes GOTO Step 10 END  IF the first inequality in condition (8) of Theorem 7 holds THEN BEGIN  Construct a permutation \(\pi_{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\), arrange them in the increasing order of their indexes; IF the second inequality in condition (8) of Theorem 7 holds THEN  construct a permutation \(\pi_{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\), arrange the jobs in the increasing order of their indexes END  Step 4: IF both permutations \(\pi_{1,2}\) and \(\pi_{2,1}\) are constructed THEN GOTO Step 10. Step 5: IF permutation \(\pi_{1,2}\) is not constructed THEN fulfill Algorithm 3. Step 6: IF permutation \(\pi_{2,1}\) is not constructed THEN fulfill Algorithm 4. Step 7: IF both permutations \(\pi_{1,2}\) and \(\pi_{2,1}\) are constructed THEN GOTO Step 10. Step 8: IF permutation \(\pi_{2,1}\) is constructed THEN GOTO Step 11. Step 9: IF permutation \(\pi_{1,2}\) is constructed THEN GOTO Step 12 ELSE GOTO Step 13. Step 10: RETURN pair of permutations \((\pi^{\prime},\pi^{\prime\prime})\), where \(\pi^{\prime}\) is the permutation of jobs from set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{1}\cup\mathcal{J}_{2,1}\) processed on machine \(M_{1}\) and \(\pi^{\prime\prime}\) is the permutation of jobs from set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{2}\cup\mathcal{J}_{2,1}\) processed on machine \(M_{2}\) such that \(\{(\pi^{\prime},\pi^{\prime\prime})\}=DS(T)\) STOP 0. Step 11: RETURN the permutation \(\pi_{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\) processed on machines \(M_{1}\) and \(M_{2}\), the partial strict order \(A_{<}^{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\) GOTO Step 14.