# 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  
**Example 1**. : _We consider the uncertain job-shop scheduling problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) with lower and upper bounds of the job durations given in Table 1._These bounds determine the set \(T\) of possible scenarios. In Example 1, jobs \(J_{1}\), \(J_{2}\), and \(J_{3}\) have the machine route \((M_{1},M_{2})\); jobs \(J_{6}\), \(J_{7}\), and \(J_{8}\) have the machine route \((M_{2},M_{1})\); and job \(J_{4}\) (job \(J_{5}\), respectively) has to be processed only on machine \(M_{1}\) (on machine \(M_{2}\), respectively). Thus, \(\mathcal{J}_{1,2}=\{J_{1},J_{2},J_{3}\}\), \(\mathcal{J}_{2,1}=\{J_{6},J_{7},J_{8}\}\), \(\mathcal{J}_{1}=\{J_{4}\}\), \(\mathcal{J}_{2}=\{J_{5}\}\). We check the conditions of Theorem 7 for a single pair of job permutations, which is optimal for all scenarios \(T\). For the given jobs, the condition in Inequalities (7) of Theorem 7 holds due to the following relations:  
\[\sum_{l_{i}\in\mathcal{J}_{1,2}}u_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\leq \sum_{l_{i}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}l_{2}=l_{6,2}+l_{7,2}+l_{8,2 }+l_{5,2}=3+3+3+16=25;\]  
\[\sum_{l_{i}\in\mathcal{J}_{1,2}}l_{2}=l_{1,2}+l_{2,2}+l_{3,2}=6+5+5=16\geq\sum_ {l_{i}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{1}}u_{i1}=u_{6,1}+u_{7,1}+u_{8,1}+u_ {4,1}=3+3+3+3=12.\]  
Due to Theorem 7, the order of jobs from the set \(\mathcal{J}_{1,2}=\{J_{1},J_{2},J_{3}\}\) and the order of jobs from the set \(\mathcal{J}_{2,1}=\{J_{6},J_{7},J_{8}\}\) may be arbitrary in the optimal pair of job permutations for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) under consideration. Thus, any pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\in S\) is a single-element dominant set \(DS(T)=\{(\pi^{\prime},\pi^{\prime\prime})\}\) for Example 1. **Example 2**. : _Let us now consider the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) with numerical input data given in Table 1 with the following two exceptions: \(l_{5,2}=2\) and \(u_{5,2}=3\)._  
We check the condition in Inequalities (7) of Theorem 7 and obtain  
\[\sum_{l_{i}\in\mathcal{J}_{1,2}}u_{i1}=u_{1,1}+u_{2,1}+u_{3,1}=7+9+9=25\
ot \leq\sum_{l_{i}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}l_{2}=l_{6,2}+l_{7,2}+ l_{8,2}+l_{5,2}=3+3+3+2=11. \tag{14}\]  
Thus, the condition of Inequalities (7) does not hold for Example 2. We check the condition of Inequalities (8) of Theorem 7 and obtain  
\[\sum_{l_{i}\in\mathcal{J}_{2,1}}u_{i2}=u_{6,2}+u_{7,2}+u_{8,2}=4+4+4=12\leq \sum_{l_{i}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{1}}l_{1}=l_{1,1}+l_{2,1}+l_{3,1}+l_{4,1}=6+8+7+2=23. \tag{15}\]  
However, we see that the condition of Equation (8) does not hold:  
\[\sum_{l_{i}\in\mathcal{J}_{2,1}}l_{1}=l_{6,1}+l_{7,1}+l_{8,1}=1+1+1=3\
ot \geq\sum_{l_{i}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2}}u_{2}=u_{1,2}+u_{2,2}+ u_{3,2}+u_{5,2}=7+6+6+3=22.\]  
From Equation (14), it follows that the condition of Inequalities (9) of Corollary 3 does not hold. On the other hand, due to Equation (15), conditions of Corollary 4 hold. Thus, the order for processing jobs from set \(\mathcal{J}_{2,1}\subseteq\mathcal{J}\) in the optimal schedule \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}),(\pi_{2,1}, \pi_{2},\pi_{1,2}))\) for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) may be arbitrary. One can fix permutation \(\pi_{2,1}\) with the increasing order of the indexes of their jobs: \(\pi_{2,1}=(J_{6},J_{7},J_{8})\). Since the orders of jobs from the sets \(\mathcal{J}_{1}\) and \(\mathcal{J}_{2}\) are fixed in the optimal schedule (Remark 1), i.e., \(\pi_{1}=(J_{4})\) and \(\pi_{2}=(J_{5})\), we need to determine the order for processing jobs in set \(\mathcal{J}_{1,2}\). To this end, we consider the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\).