# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 5 Properties of the Optimal Pairs of Job Permutations
### Two Illustrative Examples
We see that conditions of Theorem 2 do not hold for the jobs in set \(\mathcal{J}_{1,2}\) since \(J_{1}\in\mathcal{J}_{1,2}^{*}\), \(J_{2}\in\mathcal{J}_{1,2}^{2}\), and \(J_{3}\in\mathcal{J}_{1,2}^{2}\); however the following inequalities hold: \(u_{2,2}>l_{3,2}\) and \(u_{3,2}>l_{2,2}\). \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(J_{i}\) & \(l_{i1}\) & \(u_{i1}\) & \(l_{i2}\) & \(u_{i2}\) \\ \hline \(J_{1}\) & 6 & 7 & 6 & 7 \\ \(J_{2}\) & 8 & 9 & 5 & 6 \\ \(J_{3}\) & 7 & 9 & 5 & 6 \\ \(J_{4}\) & 2 & 3 & - & - \\ \(J_{5}\) & - & - & 16 & 20 \\ \(J_{6}\) & 1 & 3 & 3 & 4 \\ \(J_{7}\) & 1 & 3 & 3 & 4 \\ \(J_{8}\) & 1 & 3 & 3 & 4 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Input data for Example 1. We next construct the binary relation \(A_{\prec}^{1,2}\) over set \(\mathcal{J}_{1,2}\) based on Definition 3 and Theorem 1. Due to checking Inequalities (4) and (5), we conclude that the inequality in Equation (5) holds for the pair of jobs \(J_{1}\) and \(J_{2}\). We obtain the relation \(J_{1}\prec J_{2}\). Analogously, we obtain the relation \(J_{1}\prec J_{3}\). For the pair of jobs \(J_{2}\) and \(J_{3}\), neither Inequality (4) nor Inequality (5) hold. Therefore, the partial strict order \(A_{\prec}^{1,2}\) over set \(\mathcal{J}_{1,2}\) has the following form: \(J_{1}\prec\{J_{2},J_{3}\}\). The job set \(\{J_{2},J_{3}\}\) is a conflict set of these jobs (Definition 6). Let us check whether the sufficient conditions given in Section 5.2 hold. We check the conditions of Theorem 10 for the jobs from set \(\mathcal{J}_{1,2}\). For \(k=1\) and \(r=2\), we obtain the following equalities: \(L_{2}=\sum_{l_{1}\in\mathcal{J}_{2},1\cup\mathcal{J}_{2}}l_{l2}=l_{6,2}+l_{7,2 }+l_{8,2}+l_{5,2}=3+3+3+2=11\). The condition of Theorem 10 does not hold since the following relations hold:  
\[\sum_{i=1}^{k+r}u_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\
ot\leq L_{2}+\sum_{i= 1}^{k}l_{2}=L_{2}+l_{1,2}=11+6=17.\]  
For checking the conditions of Theorem 11, we need to check both permutations of the jobs from set \(\mathcal{J}_{1,2}\), which satisfy the partial strict order \(A_{\prec}^{1,2}\): \(\Pi(\mathcal{G}_{1,2})=\{\pi_{1,2}^{1},\pi_{1,2}^{2}\}\), where \(\pi_{1,2}^{1}=\{J_{1},J_{2},J_{3}\}\) and \(\pi_{1,2}^{2}=\{J_{1},J_{3},J_{2}\}\). We consider permutation \(\pi_{1,2}^{1}\). As in the previous case, \(L_{2}=11\), \(k=1\), \(r=2\), and we must consider two inequalities in the condition in Equaiton (12) with \(s=1\) and \(s=2\). For \(s=1\), we obtain the following:  
\[u_{1+1,1}=u_{2,1}=9\leq L_{2}+\sum_{i=1}^{1+1-1}(l_{l2}-u_{i1})=L_{2}+\sum_{i= 1}^{1}(l_{l2}-u_{i1})=11+(l_{1,2}-u_{1,1})=11+(6-7)=10.\]  
However, for \(s=2\), we obtain  
\[u_{1+2,1}=u_{3,1}=9\
ot\leq L_{2}+\sum_{i=1}^{1+2-1}(l_{l2}-u_{i1})=L_{2}+\sum _{i=1}^{2}(l_{l2}-u_{i1})\]  
\[=11+(l_{1,2}-u_{1,1})+(l_{2,2}-u_{2,1})=11+(6-7)+(5-9)=6.\]  
Thus, the conditions of Theorem 11 do not hold for permutation \(\pi_{1,2}^{1}\). We consider permutation \(\pi_{1,2}^{2}\), where \(J_{k+1}=J_{3}\) and \(J_{k+2}=J_{2}\). Again, we must test the two inequalities in Equation (12), where either \(s=1\) or \(s=2\). For \(s=1\), we obtain  
\[u_{k+1,1}=u_{3,1}=9\leq L_{2}+\sum_{i=1}^{k+1-1}(l_{l2}-u_{i1})=L_{2}+\sum_{i =1}^{1}(l_{l2}-u_{i1})=11+(l_{1,2}-u_{1,1})=11+(6-7)=10.\]  
However, for \(s=2\), we obtain  
\[u_{k+2,1}=u_{2,1}=9\
ot\leq L_{2}+\sum_{i=1}^{k+2-1}(l_{l2}-u_{i1})=L_{2}+\sum _{i=1}^{k+1}(l_{l2}-u_{i1})=11+(l_{1,2}-u_{1,1})+(l_{3,2}-u_{3,1})\]  
\[=11+(6-7)+(5-9)=6.\]  
Thus, the conditions of Theorem 11 do not hold for permutation \(\pi_{1,2}^{2}\). Note that we do not check the conditions of Theorem 12 since the conflict set of jobs \(\{J_{2},J_{3}\}\) is located at the end of the partial strict order \(A_{\prec}^{1,2}\). We conclude that none of the proven sufficient conditions are satisfied for a schedule optimality. Thus, there does not exist a pair of permutations of the jobs in set \(\mathcal{J}=\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{1}\cup \mathcal{J}_{2}\) which is optimal for any scenario \(p\in T\).