# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 5 Properties of the Optimal Pairs of Job Permutations
### Sufficient Conditions for an Optimal Pair of Job Permutations
As the permutation \(\pi_{2,1}^{*}\) is a Johnson's permutation, the value of \(C_{max}(\pi_{2,1}^{*})\) cannot be reduced and we obtain the following equalities:  
\[\sum_{I_{1}\in\mathcal{J}_{2,1}}u_{22} \leq\sum_{I_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{1}}l_{11}\text { and }\sum_{I_{1}\in\mathcal{J}_{2,1}}l_{11}\geq\sum_{I_{1}\in\mathcal{J}_{2,1}\cup \mathcal{J}_{2}}u_{I2} \tag{8}\]0  
Thus, the pair of job permutation \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}^{*}),(\pi_{2,1 }^{*},\pi_{2,1}^{*},\pi_{2,1}))\in<\{\pi_{1,2}\},S_{2,1}>\subseteq S\) is optimal for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\). The optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\) belongs to the set \(<\{\pi_{1,2}\},S_{2,1}>\). As vector \(p\) is an arbitrary vector in the set \(T\), the set \(<\{\pi_{1,2}\},S_{2,1}>\) contains an optimal pair of job permutations for all scenarios from set \(T\). Due to Definition 4, the set \(<\{\pi_{1,2}\},S_{2,1}>\subseteq S\) 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}\). Corollary 4: _Consider the following inequality:_  
\[\sum_{I_{1}\in\mathcal{J}_{2,1}}u_{22} \leq\sum_{I_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{1}}l_{11}\text { and }\sum_{I_{1}\in\mathcal{J}_{2,1}}l_{11}\geq\sum_{I_{1}\in\mathcal{J}_{2,1}\cup \mathcal{J}_{2}}u_{I2} \tag{8}\]1_If the above inequality holds, then set \(<S_{1,2}\), \(\{\pi_{2,1}\}>\), where \(\pi_{2,1}\) is an arbitrary permutation in set \(S_{2,1}\), 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 set \(\mathcal{J}=\mathcal{J}_{1}\cup\mathcal{J}_{2}\cup\mathcal{J}_{1,2}\cup \mathcal{J}_{2,1}\) of the given jobs._  
This claim may be proven similar to Corollary 3. If the conditions of Corollary 3 (Corollary 4) hold, then the order for processing jobs from set \(\mathcal{J}_{1,2}\subseteq\mathcal{J}\) (set \(\mathcal{J}_{2,1}\subseteq\mathcal{J}\), respectively) in the optimal schedule \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}),(\pi_{2,1}, \pi_{2,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. Since the orders of jobs from the sets \(\mathcal{J}_{1}\) and \(\mathcal{J}_{2}\) are fixed in the optimal schedule (Remark 1), we need to determine only orders for processing jobs from set \(\mathcal{J}_{2,1}\) (set \(\mathcal{J}_{1,2}\), respectively). To do this, we will consider two uncertain problems \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\subseteq\mathcal{J}\) and with the machine route \((M_{1},M_{2})\) and that with job set \(\mathcal{J}_{2,1}\subseteq\mathcal{J}\) and with the opposite machine route \((M_{2},M_{1})\). **Lemma 2**. : _If \(S^{\prime}_{1,2}\subseteq S_{1,2}\) is a set of permutations from the dominant set for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{1,2}\), then \(<S^{\prime}_{1,2},S_{2,1}>\subseteq S\) 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}=\mathcal{J}_{1}\cup\mathcal{J}_{2}\cup\mathcal{J}_{1,2}\cup \mathcal{J}_{2,1}\)._  
The proof of Lemma 2 and those for other statements in this section are given in Appendix A. **Lemma 3**. : _Let \(S^{\prime}_{2,1}\subseteq S_{2,1}\) be a set of permutations from the dominant set for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) with job set \(\mathcal{J}_{2,1}\), \(S^{\prime}_{2,1}\subseteq S_{2,1}\). Then, \(<S_{1,2}\), \(S^{\prime}_{2,1}>\) 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}\)._  
The proof of this claim is similar to that for Lemma 2 (see Appendix A). **Theorem 8**.