# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## Appendix A Proofs of the Statements  
### Proof of Lemma 2  
We choose an arbitrary vector \(p\) in the set \(T\), \(p\in T\), and show that set \(<S^{\prime}_{1,2},S_{2,1}>\) contains at least one optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\). Let \((\pi^{*},\pi^{**})=((\pi^{*}_{1,2},\pi_{1},\pi^{*}_{2,1}),(\pi^{*}_{2,1},\pi_{2 },\pi^{*}_{1,2}))\) be a [PERSON]'s pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\), i.e., \(C_{max}(\pi^{*},\pi^{**})=C_{max}\). Without loss of generality, one can assume that jobs in both permutations \(\pi_{1}\) and \(\pi_{2}\) are ordered in increasing order of their indexes. It is clear that \(\pi^{*}_{2,1}\in S_{2,1}\). If inclusion \(\pi^{*}_{1,2}\in S^{\prime}_{1,2}\) holds as well, then \((\pi^{*},\pi^{**})\in<\)\(S^{\prime}_{1,2},S_{2,1}>\) and set \(<S^{\prime}_{1,2},S_{2,1}>\) contains an optimal pair of job permutations for the problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\in T\). We now assume that \(\pi^{*}_{1,2}\
ot\in S^{\prime}_{1,2}\). The set \(S^{\prime}_{1,2}\) contains at least one optimal permutation for the problem \(F2|p_{1,2}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and scenario \(p_{1,2}\) (the components of vector \(p_{1,2}\) are equal to the corresponding components of vector \(p\)). We denote this permutation as \(\pi^{\prime}_{1,2}\). Remember that permutation \(\pi^{\prime}_{1,2}\) may be not a [PERSON]'s permutation for the problem \(F2|p_{1,2}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and scenario \(p_{1,2}\). We consider a pair of job permutations \((\pi^{\prime},\pi^{**})=((\pi^{\prime}_{1,2},\pi_{1},\pi^{*}_{2,1}),\)\((\pi^{*}_{2,1},\pi_{2},\pi^{\prime}_{1,2}))\in<\)\(S^{\prime}_{1,2},S_{2,1}>\) and show that equality \(C_{max}(\pi^{\prime},\pi^{**})=C_{max}\) holds. We consider the following two possible cases. _(j) \(C_{max}(\pi^{\prime},\pi^{**})=c_{1}(\pi^{\prime})\)._  
If equality \(c_{1}(\pi^{\prime})=\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}p_{i1}\) holds, then \(c_{1}(\pi^{\prime})\leq c_{1}(\pi^{*})\). We now assume that inequality \(c_{1}(\pi^{\prime})>\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}p_{i1}\) holds. Then, machine \(M_{1}\) has an idle time. As it is mentioned in the proof of Theorem 7, an idle time for machine \(M_{1}\) is only possible if some job \(J_{j}\) from the 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}\). Thus, 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}\) (the components of vector \(p_{2,1}\) are equal to the corresponding components of vector \(p\)). As jobs from the set \(\mathcal{J}_{2,1}\) are processed as in the permutation \(\pi^{*}_{2,1}\), which is a Johnson's permutation, the value of \(c_{1}(\pi^{\prime})\) cannot be reduced and so \(c_{1}(\pi^{\prime})\leq c_{1}(\pi^{*})\). We obtain the following relations: \(C_{max}(\pi^{\prime},\pi^{**})=c_{1}(\pi^{\prime})\leq c_{1}(\pi^{*})\leq\max \{c_{1}(\pi^{*}),c_{2}(\pi^{**})\}=C_{max}(\pi^{*},\pi^{**})=C_{max}\). Thus, equality \(C_{max}(\pi^{\prime},\pi^{**})=C_{max}\) holds. _(jj) \(C_{max}(\pi^{\prime},\pi^{**})=c_{2}(\pi^{**})\)._  
Similarly to case _(j)_, we obtain the following equality:  
\[c_{2}(\pi^{**})=\max\{\sum_{j_{1}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup \mathcal{J}_{2}}p_{i2},C_{max}(\pi^{\prime}_{1,2})\},\]where \(C_{max}(\pi^{\prime}_{1,2})\) is the makespan for the problem \(F2|p_{1,2}|C_{max}\) with job set \(\mathcal{J}_{1,2}\) and vector \(p_{1,2}\) of the job durations (it is assumed that \(\pi^{\prime}_{1,2}\) is an optimal permutation for this problem). Thus, the value of \(c_{2}(\pi^{**})\) cannot be reduced and equality \(C_{max}(\pi^{\prime},\pi^{**})=C_{max}\) holds.