# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 5 Properties of the Optimal Pairs of Job Permutations
### Precedence Digraphs Determining a Minimal Dominant Set of Schedules
We can determine a dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|\mathrm{C}_{max}\) with job set \(\mathcal{J}\) as follows: \(<\Pi(G_{1,2}),\Pi(G_{2,1})>\subseteq S\). The following theorems allow us to reduce a dominant set for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|\mathrm{C}_{max}\). We use the following notation: \(L_{2}=\sum_{l_{i}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}l_{i2}\). Theorem 10: _Let the strict order \(A_{<}^{1,2}\) over set \(\mathcal{J}_{1,2}=\mathcal{J}_{1,2}^{*}\cup\mathcal{J}_{1,2}^{1}\cup\mathcal{J} _{1,2}^{2}\) be determined as follows: \(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}}\). Consider the following inequality:_  
\[\sum_{i=1}^{k+r}u_{i1}\ \leq L_{2}+\sum_{i=1}^{k}l_{i2}, \tag{11}\]  
_If the above inequality holds, then set \(S^{\prime}=\prec\{\pi\},\Pi(G_{2,1})>\subset S\) with \(\pi\in\Pi(G_{1,2})\) is a dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|\mathrm{C}_{max}\) with job set \(\mathcal{J}\)._Proof. : We consider an arbitrary vector \(p\in T\) of the job durations and an arbitrary permutation \(\pi\) from the set \(\Pi(G_{1,2})\). The set \(\Pi(G_{2,1})\) contains at least one optimal [PERSON]'s permutation \(\pi_{2,1}^{*}\) for the problem \(F2|p_{2,1}|C_{max}\) with job set \(\mathcal{J}_{2,1}\) and vector \(p_{2,1}\) of the job durations (components of this vector are equal to the corresponding components of the vector \(p\)). We consider a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})=((\pi,\pi_{1},\pi_{2,1}^{*}),(\pi_{2,1}^{*},\pi_{2,\pi}))\in\ S^{\prime}\) and show that it is an optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with set \(\mathcal{J}\) of the jobs and scenario \(p\). To this end, we show that the value of \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=\max\{c_{1}(\pi^{\prime}),c_{2}(\pi^ {\prime\prime})\}\) cannot be reduced. Indeed, an idle time for machine \(M_{1}\) is only possible if some job \(J_{j}\) from the set \(\mathcal{J}_{2,1}\) is processed on machine \(M_{2}\) at the same time when job \(J_{j}\) could be processed on machine \(M_{1}\). In such a case, \(c_{1}(\pi^{\prime})\) is equal to the makespan \(C_{max}(\pi_{2,1}^{*})\) for the problem \(F2|p_{2,1}|C_{max}\) with job set \(\mathcal{J}_{2,1}\) and vector \(p_{2,1}\) of the job durations. As permutation \(\pi_{2,1}^{*}\) is a Johnson's permutation, the value of  
\[c_{1}(\pi^{\prime})=\max\{\sum_{j_{i}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2,1} \cup\mathcal{J}_{1}}p_{11},C_{max}(\pi_{2,1}^{*})\}\]  
cannot be reduced. In the beginning of the permutation \(\pi\), the jobs of set \(\{J_{1},J_{2},\ldots,J_{k}\}\) are arranged in the [PERSON]'s order. Thus, if machine \(M_{2}\) has an idle time while processing these jobs, this idle time cannot be reduced. From Inequality (11), it follows that machine \(M_{2}\) has no idle time while processing jobs from the conflict set. In the end of the permutation \(\pi\), jobs of set \(\{J_{k+r+1},\ldots,J_{m_{1,2}}\}\) are arranged in [PERSON]'s order. Therefore, if machine \(M_{2}\) has an idle time while processing these jobs, this idle time cannot be reduced. Thus, the value of \(c_{2}(\pi^{\prime\prime})\) cannot be reduced by changing the order of jobs in the conflict set. We obtain the qualities \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=\max\{c_{1}(\pi^{\prime}),c_{2}(\pi^ {\prime\prime})\}=C_{max}\). The pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})=((\pi,\pi_{1},\pi_{2,1}^{*}),(\pi_{2,1}^{*},\pi_{2},\pi))\) is optimal for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\). Thus, set \(S^{\prime}=<\{\pi\},\Pi(G_{2,1})>\) contains an optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\). As vector \(p\) is an arbitrary vector in set \(T\), set \(S^{\prime}\) contains an optimal pair of job permutations for each vector from set \(T\).