# 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 12: RETURN the permutation \(\pi_{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\) processed on machines \(M_{1}\) and \(M_{2}\), the partial strict order \(A_{<}^{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\)  Step 13: RETURN the partial strict order \(A_{<}^{1,2}\) of jobs from set \(\mathcal{J}_{1,2}\)  and the partial strict order \(A_{<}^{2,1}\) of jobs from set \(\mathcal{J}_{2,1}\)  Step 14: STOP 1. ```  
**Algorithm 2**Construction of a small dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\)  
Algorithm 2 may be applied for solving the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) exactly or approximately as follows. If at least one of the sufficient conditions proven in Section 5.1 hold, then Algorithm 2 constructs a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}),(\pi_{2,1},\pi_{2 },\pi_{1,2}))\), which is optimal for any scenario \(p\in T\) (Step 10). It may happen that the constructed strict order on the set \(\mathcal{J}_{1,2}\) or on the set \(\mathcal{J}_{2,1}\) is not a linear strict order. If for at least one of the sets \(\mathcal{J}_{1,2}\) or \(\mathcal{J}_{2,1}\), the constructed partial strict order is not a linear one, a heuristic solution for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) is constructed similar to that for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) solved by Algorithm 1 (see Section 5.4). If Algorithm 2 is completed at Steps 11-13 (STOP 1), we consider a set of conflict jobs \(\{l_{k+1},l_{k+2},\ldots,l_{k+r}\}\) and construct a Jackson's pair of job permutation for the deterministic problem \(J2|p^{\prime},n_{i}\leq 2|C_{max}\) with job set \(\mathcal{J}=\{l_{k+1},l_{k+2},\ldots J_{k+r}\}\), where the 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 \(\{l_{k+1},l_{k+2},\ldots J_{k+r}\}\) is calculated using the equality of Equation (16) for each operation \(O_{ij}\) of the conflict job \(j_{i}\in\{l_{k+1},l_{k+2},\ldots J_{k+r}\}\) on the corresponding machine \(M_{j}\in\mathcal{M}\) (Remark 3). ```
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}\) on machines \(M_{j}\in\mathcal{M}=\{M_{1},M_{2}\}\). Output: EITHER permutation \(\pi_{1,2}\), which is optimal for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with any scenario \(p\in T\) for the jobs \(\mathcal{J}_{1,2}\), OR partial strict order \(A^{1,2}_{\prec}\) on the set \(\mathcal{J}_{1,2}\). Step 1: Construct a partition \(\mathcal{J}_{1,2}=\mathcal{J}^{1}_{1,2}\cup\mathcal{J}^{1}_{1,2}\cup\mathcal{J }^{s}_{1,2}\) of the set \(\mathcal{J}_{1,2}\) of the jobs. Step 2: IF conditions of Theorem 2 hold THEN Step 3: Construct permutation \(\pi_{1,2}=(\pi^{1}_{1,2},\pi^{s}_{1,2},\pi^{s}_{1,2})\), where \(\pi^{1}_{1,2}\) is a permutation for processing jobs from the set \(\mathcal{J}^{1}_{1,2}\) in the non-decreasing order of the values \(u_{i1}\), \(\pi^{2}_{1,2}\) is a permutation for processing jobs from the set \(\mathcal{J}^{1}_{1,2}\) in the non-increasing order of the values \(u_{i2}\)GOTO Step 7 ELSE Step 4: FOR each pair of jobs \(J_{v}\in\mathcal{J}_{1,2}\) and \(J_{w}\in\mathcal{J}_{1,2}\), \(v\
eq w\), DO IF at least one of two conditions (4) and (5) holds THEN  determine the relation \(J_{v}\prec J_{w}\) END FOR Step 5: Renumber jobs in the set \(\mathcal{J}_{1,2}\) such that relation \(v<w\) holds if \(J_{v}\prec J_{w}\). Step 6: FOR each conflict set of jobs DO IF condition of Theorem 10 holds THEN  Order jobs in the conflict set in the increasing order of their indexes GOTO Step 7 ELSE fulfill Algorithm 1 END FOR Step 7: IF the partial strict order \(A^{1,2}_{\prec}\) is linear THEN  construct a permutation \(\pi_{1,2}\) generated by the linear order \(A^{1,2}_{\prec}\) STOP.