# 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
Due to Definition 4, set \(S^{\prime}\) is a dominant set of schedules for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) with job set \(\mathcal{J}\). Theorem 4.1: _Let the partial strict order \(A_{<}^{1,2}\) over set \(\mathcal{J}_{1,2}=\mathcal{J}_{1,2}^{*}\cup\mathcal{J}_{1,2}^{1}\) 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:_  
\[u_{k+s,1}\leq L_{2}+\sum_{i=1}^{k+s-1}(l_{i2}-u_{i1}) \tag{12}\]  
_If the above inequality holds for all \(s\in\{1,2,\ldots,r\}\), then the set \(S^{\prime}=<\{\pi\},S_{2,1}>\), where \(\pi=(I_{1},\ldots,I_{k-1},I_{k},I_{k+1},I_{k+2},\ldots,I_{k+r},I_{k+r+1}, \ldots,J_{m_{1,2}})\in\Pi(G_{1,2})\), is a dominant set for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) with job set \(\mathcal{J}\)._  
Proof. : We consider an arbitrary scenario \(p\in T\) and 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}\), where \(\pi_{2,1}^{*}\in S_{2,1}\) is a [PERSON]'s permutation of the jobs from the set \(\mathcal{J}_{2,1}\) with vector \(p_{2,1}\) of the job durations (components of this vector are equal to the corresponding components of vector \(p\)). We next show that this pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) is optimal for the individual deterministic problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\), i.e., \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=C_{max}\). If conditions of Theorem 4.1 hold, then machine \(M_{2}\) processes jobs from the conflict set \(\{J_{k+1},I_{k+2},\ldots,J_{k+r}\}\) without idle times. At the initial time \(t=0\), machine \(M_{1}\) begins to process jobs from the permutation \(\pi\) without idle times. Let a time moment \(t_{1}\) be as follows: \(t_{1}=\sum_{i=1}^{k+1}p_{i1}\). At the time moment \(t_{1}\), job \(J_{k+1}\) is ready for processing on machine \(M_{2}\). On the other hand, at the time \(t=0\), machine \(M_{2}\) begins to process jobs from the set \(\mathcal{J}_{2,1}\cup\mathcal{J}_{2}\) without idle times and then jobs from the permutation \((J_{1},J_{2},\ldots,J_{k+1})\). Let \(t_{2}\) denote the first time moment when machine \(M_{2}\) is ready for processing job \(J_{k+1}\). Obviously, the following inequality holds: \(t_{2}\geq L_{2}+\sum_{i=1}^{k+1}p_{i2}\). From the condition in Inequality (12) with \(s=1\), we obtain inequality \(\sum_{i=1}^{k+1}u_{i1}\leq L_{2}+\sum_{i=1}^{k}l_{i2}\). Therefore, the following relations hold:  
\[t_{1}=\sum_{i=1}^{k+1}p_{i1}\leq\sum_{i=1}^{k+1}u_{i1}\leq L_{2}+\sum_{i=1}^{k} l_{i2}\leq L_{2}+\sum_{i=1}^{k+1}p_{i2}=t_{2}.\]  
Machine \(M_{2}\) processes job \(J_{k+1}\) without an idle time between job \(J_{k}\) and job \(J_{k+1}\). Analogously, using \(s\in\{2,3,\ldots,r\}\), one can show that machine \(M_{2}\) processes jobs from the conflict set \(\{J_{k+1},J_{k+2},\ldots,J_{k+r}\}\) without idle times between jobs \(J_{k+1}\) and \(J_{k+2}\), between jobs \(J_{k+2}\) and \(J_{k+3}\), and so on to between jobs \(J_{k+r-1}\) and \(J_{k+r}\). To end this proof, we have to 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. An idle time for machine \(M_{1}\) is only possible between some jobs from the set \(\mathcal{J}_{2,1}\). However, the permutation \(\pi_{2,1}^{*}\) is a [PERSON]'s permutation of the jobs from the set \(\mathcal{J}_{2,1}\) for the vector \(p_{2,1}\) of the job durations. Therefore, the value of \(c_{1}(\pi^{\prime})\) cannot be reduced. On the other hand, in the permutation \(\pi\), all jobs \(J_{1},J_{2},\ldots,J_{k}\) and all jobs \(J_{k+r+1},\ldots,J_{m_{1,2}}\) are arranged in [PERSON]'s orders. Therefore, if machine \(M_{2}\) has an idle time while processing these jobs, this idle time cannot be reduced. It is clear that machine \(M_{2}\) has no idle time while processing jobs from the conflict set.