# 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 a pair of permutations \((\pi^{\prime},\pi^{\prime\prime})\) is an arbitrary pair of job permutations in the set \(S\), any pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\in S\) is a singleton \(DS(T)=\{(\pi^{\prime},\pi^{\prime\prime})\}\) 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 case when the condition in Inequalities (8) holds may be analyzed similarly via replacing machine \(M_{1}\) by machine \(M_{2}\) and vice versa. If conditions of Theorem 7 hold, then in the optimal pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) existing for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\), the orders of jobs from sets \(\mathcal{J}_{1,2}\subseteq\mathcal{J}\) and \(\mathcal{J}_{2,1}\subseteq\mathcal{J}\) may be chosen arbitrarily. Theorem 7 implies the following two corollaries. Corollary 3: _If the following inequality holds:_  
\[\sum_{j_{i}\in\mathcal{J}_{1,2}}u_{i1}\leq\sum_{J_{j}\in\mathcal{J}_{2,1}\cup \mathcal{J}_{2}}l_{i2}, \tag{9}\]  
_then set \(<\{\pi_{1,2}\},S_{2,1}>\subseteq S\), where \(\pi_{1,2}\) is an arbitrary permutation in set \(S_{1,2}\), 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._  
Proof: We consider an arbitrary vector \(p\in T\) of the job durations and an arbitrary permutation \(\pi_{1,2}\) in the set \(S_{1,2}\). The set \(S_{2,1}\) contains at least one [PERSON]'s permutation \(\pi_{2,1}^{*}\) for the deterministic problem \(F2|p_{2,1}|C_{max}\) with job set \(\mathcal{J}_{2,1}\) and scenario \(p_{2,1}\) (the components of vector \(p_{2,1}\) are equal to the corresponding components of vector \(p\)). We consider a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2},\pi_{1},\pi_{2,1}^{*}),(\pi_{2,1 }^{*},\pi_{2,2},\pi_{1,2}))\in<\{\pi_{1,2}\},S_{2,1}>\subseteq S\) and show that it is an optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with job set \(\mathcal{J}\) and scenario \(p\). Without loss of generality, both permutations \(\pi_{1}\) and \(\pi_{2}\) are ordered in increasing order of the indexes of their jobs. Similar to the proof of Theorem 7, one can show that, if the condition in Inequalities (9) holds, then machine \(M_{2}\) processes jobs without idle times and equality \(c_{2}(\pi^{\prime\prime})=\sum_{l_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1 }\cup\mathcal{J}_{2}}p_{i2}\) holds, where the value of \(c_{2}(\pi^{\prime\prime})\) cannot be reduced. If machine \(M_{1}\) has no idle time, we obtain equalities  
\[C_{max}(\pi^{\prime},\pi^{\prime\prime})=\max\{c_{1}(\pi^{\prime}),c_{2}(\pi^{ \prime\prime})\}=\max\{\sum_{l_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1} \cup\mathcal{J}_{1}}p_{i1},\sum_{l_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1 }\cup\mathcal{J}_{2}}p_{i2}\}=C_{max}.\]  
On the other hand, an idle time of machine \(M_{1}\) is only possible if some job \(J_{j}\) from set \(\mathcal{J}_{2,1}\) is processed on machine \(M_{2}\) at the time moment \(t_{2}\) when job \(J_{j}\) could be processed on machine \(M_{1}\). In such a case, the value of \(c_{1}(\pi^{\prime})\) is equal to the makespan \(C_{max}(\pi_{2,1}^{*})\) for the problem \(F2|p_{2,1}|C_{max}\) with job set \(\mathcal{J}_{2,1}\) and scenario \(p_{2,1}\).