# 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
From the first inequality in (7), we obtain the following relations:  
\[\sum_{j_{1}\in\mathcal{J}_{1,2}}p_{i1}\leq\sum_{j_{1}\in\mathcal{J}_{1,2}}u_{ i1}\leq\sum_{j_{1}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}l_{i2}\leq\sum_{j_{1} \in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}p_{i2}=t_{1}.\]  
Therefore, at the time moment \(t_{1}\), machine \(M_{2}\) begins to process jobs from the set \(\mathcal{J}_{1,2}\) without idle times and we obtain the following equality: \(c_{2}(\pi^{\prime\prime})=\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1} \cup\mathcal{J}_{2}}p_{i2}\), where \(I_{2}=0\) and machine \(M_{2}\) has no idle time. We next show that machine \(M_{2}\) is a main machine for the schedule \((\pi^{\prime},\pi^{\prime\prime})\). To this end, we consider the following two possible cases. _(a)_ Let machine \(M_{1}\) have no idle time. By summing Inequalities (7), we obtain the following inequality:  
\[\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{1}}u_{i1} \leq\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{2}} l_{i2}.\]  
Thus, the following relations hold:  
\[c_{1}(\pi^{\prime})=\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}p_{i1}\leq\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1} \cup\mathcal{J}_{1}}u_{i1}\leq\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{ 2,1}\cup\mathcal{J}_{2}}l_{i2}\leq\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J }_{2,1}\cup\mathcal{J}_{2}}p_{i2}=c_{2}(\pi^{\prime\prime}).\]  
Hence, machine \(M_{2}\) is a main machine for the schedule \((\pi^{\prime},\pi^{\prime\prime})\). _(b)_ Let machine \(M_{1}\) have an idle time. 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 this job \(J_{j}\) could be processed on machine \(M_{1}\). Obviously, after the time moment \(\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}\) when machine \(M_{2}\) completes all jobs from set \(\mathcal{J}_{2,1}\), machine \(M_{1}\) can process some jobs from set \(\mathcal{J}_{2,1}\) without an idle time. Therefore, the inequality \(t_{2}+I_{1}\leq\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}\) holds and we obtain the following relations:  
\[c_{1}(\pi^{\prime})\leq t_{2}+I_{1}+\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i1}\leq \sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}+\sum_{j_{1}\in\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}p_{i1}\leq\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}+\sum_{j_{1} \in\mathcal{J}_{2,1}\cup\mathcal{J}_{1}}u_{i1}\]  
\[\leq\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}+\sum_{j_{1}\in\mathcal{J}_{1,2}}l_{i2 }\leq\sum_{j_{1}\in\mathcal{J}_{2,1}}p_{i2}+\sum_{j_{1}\in\mathcal{J}_{1,2}}p_{ i2}\leq\sum_{j_{1}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}\cup\mathcal{J}_{ 1,2}}p_{i2}=c_{2}(\pi^{\prime\prime}).\]  
We conclude that, in case _(b)_, machine \(M_{2}\) is a main machine for the schedule \((\pi^{\prime},\pi^{\prime\prime})\). Thus, if the condition in Inequalities (7) holds, then machine \(M_{2}\) is a main machine for the schedule \((\pi^{\prime},\pi^{\prime\prime})\) and machine \(M_{2}\) has no idle time, i.e., equality \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=c_{2}(\pi^{\prime\prime})\) holds and machine \(M_{2}\) is completely filled in the segment \([0,c_{2}(\pi^{\prime\prime})]\) with processing jobs from the set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{2}\). Thus, the pair of permutations \((\pi^{\prime},\pi^{\prime\prime})\) is optimal for scenario \(p\in T\). Since scenario \(p\) was chosen arbitrarily in the set \(T\), we conclude that the pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) 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 set \(\mathcal{J}=\mathcal{J}_{1}\cup\mathcal{J}_{2}\cup\mathcal{J}_{1,2}\cup \mathcal{J}_{2,1}\)of the given jobs.