# 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  
In Section 4.2, it is assumed that \(\mathcal{J}_{1,2}=\mathcal{J}_{1,2}^{1}\cup\mathcal{J}_{1,2}^{2}\cup\mathcal{J}_{ 1,2}^{*}\) and \(\mathcal{J}_{2,1}=\mathcal{J}_{2,1}^{1}\cup\mathcal{J}_{2,1}^{2}\cup\mathcal{J}_ {2,1}^{*}\), i.e., \(\mathcal{J}_{1,2}^{0}=\mathcal{J}_{2,1}^{0}=\emptyset\). Based on the results presented in Section 4.2, we can determine a binary relation \(A_{<}^{1,2}\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{1,2}\) and a binary relation \(A_{<}^{2,1}\) for this problem with job set \(\mathcal{J}_{2,1}\). For job set \(\mathcal{J}_{1,2}\), the binary relation \(A_{<}^{1,2}\) determines the digraph \(G_{1,2}=(\mathcal{J}_{1,2},A_{<}^{1,2})\) with the vertex set \(\mathcal{J}_{1,2}\) and the arc set \(A_{<}^{1,2}\). For job set \(\mathcal{J}_{2,1}\), the binary relation \(A_{<}^{2,1}\) determines the digraph \(G_{2,1}=(\mathcal{J}_{2,1},A_{<}^{2,1})\) with the vertex set \(\mathcal{J}_{2,1}\) and the arc set \(A_{<}^{2,1}\). Let us consider the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{1,2}\) and the corresponding digraph \(G_{1,2}=(\mathcal{J}_{1,2},A_{<}^{1,2})\) (the same results for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{2,1}\) can be derived in a similar way). Definition 5: Two jobs, \(J_{x}\in\mathcal{J}_{1,2}\) and \(J_{y}\in\mathcal{J}_{1,2}\), \(x\
eq y\), are called conflict jobs if they are not in the relation \(A_{<}^{1,2}\), i.e., \((J_{x},J_{y})\
ot\in A_{<}^{1,2}\) and \((J_{y},J_{x})\
ot\in A_{<}^{1,2}\). Due to Definitions 2 and 3, for the conflict jobs \(J_{x}\in\mathcal{J}_{1,2}\) and \(J_{y}\in\mathcal{J}_{1,2}\), \(x\
eq y\), Inequalities (4) and (5) do not hold either for the case \(v=x\) with \(w=y\) or for the case \(v=y\) with \(w=x\). Definition 6: The subset \(\mathcal{J}_{x}\subseteq\mathcal{J}_{1,2}\) is called a conflict set of jobs if, for any job \(J_{y}\in\mathcal{J}_{1,2}\setminus\mathcal{J}_{x}\), either relation \((J_{x},J_{y})\in A_{<}^{1,2}\) or relation \((J_{y},J_{x})\in A_{<}^{1,2}\) holds for each job \(J_{x}\in\mathcal{J}_{x}\) (provided that any proper subset of the set \(\mathcal{J}_{x}\) does not possess such a property). From Definition 6, it follows that the conflict set \(\mathcal{J}_{x}\) is a minimal set (with respect to the inclusion). Obviously, there may exist several conflict sets in the set \(\mathcal{J}_{1,2}\). (A conflict set of the jobs \(\mathcal{J}_{x}\subseteq\mathcal{J}_{2,1}\) can be determined similarly.) Let the strict order \(A_{\prec}^{1,2}\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{1,2}\) be represented as follows:  
\[J_{1}\prec J_{2}\prec\ldots\prec J_{k}\prec\{J_{k+1},J_{k+2},\ldots,J_{k+r}\} \prec J_{k+r+1}\prec J_{k+r+2}\prec\ldots\prec J_{m_{1,2}}, \tag{10}\]  
where all jobs between braces are conflict ones and each of these jobs is in relation \(A_{<}^{1,2}\) with any job located outside the brackets in Relation (10). In such a case, an optimal order for processing jobs from the set \(\{J_{1},J_{2},\ldots,J_{k}\}\) is determined as follows: \((J_{1},J_{2},\ldots,J_{k})\). Due to Theorem 5, we obtain that set \(\Pi(G_{1,2})\) of the permutations generated by the digraph \(G_{1,2}\) contains an optimal [PERSON]'s permutation for each vector \(p_{1,2}\) of the durations of jobs from the set \(\mathcal{J}_{1,2}\). Thus, due to Definition 1, the singleton \(\{(\pi_{1,2},\pi_{1,2})\}\), where \(\pi_{1,2}\in\Pi(G_{1,2})\), is a J-solution for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{1,2}\). Analogously, the singleton \(\{(\pi_{2,1},\pi_{2,1})\}\), where \(\pi_{2,1}\in\Pi(G_{2,1})\), is a J-solution for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|\mathrm{C}_{max}\) with job set \(\mathcal{J}_{2,1}\).