# 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  
In the proofs of several claims, we use a notion of the main machine, which is introduced within the proof of the following theorem. **Theorem 7**: _Consider the following conditions in Inequalities (7) or (8):_  
\[\sum_{I_{i}\in\mathcal{J}_{1,2}}u_{11} \leq\sum_{I_{1}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}l_{22}\text { and }\sum_{I_{1}\in\mathcal{J}_{1,2}}l_{22}\geq\sum_{I_{1}\in\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}u_{11} \tag{7}\] \[\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}\]  
_If one of the above conditions holds, then 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 the problem \(\mathcal{J}2|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. : Let the condition in Inequalities (7) hold. Then, we consider an arbitrary pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\in S\) with any fixed scenario \(p\in T\) and show that this pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) is optimal for the individual deterministic problem \(\mathcal{J}2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\), i.e., \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=C_{max}\). Let \(c_{1}(\pi^{\prime})\) (\(c_{2}(\pi^{\prime\prime})\)) denote a completion time of all jobs \(\mathcal{J}_{1}\cup\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\) (jobs \(\mathcal{J}_{2}\cup\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\)) on machine \(M_{1}\) (machine \(M_{2}\)) in the schedule \((\pi^{\prime},\pi^{\prime\prime})\), where \(\pi^{\prime}=(\pi_{1,2},\pi_{1},\pi_{2,1})\) and \(\pi^{\prime\prime}=(\pi_{2,1},\pi_{2},\pi_{1,2})\). For the problem \(\mathcal{J}2|p,n_{i}\leq 2|C_{max}\), the maximal completion time of the jobs in schedule \((\pi^{\prime},\pi^{\prime\prime})\) may be calculated as follows: \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=\max\{c_{1}(\pi^{\prime}),c_{2}(\pi^{ \prime\prime})\}\). Machine \(M_{1}\) (machine \(M_{2}\)) is called a _main machine_ for the schedule \((\pi^{\prime},\pi^{\prime\prime})\) if equality \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=c_{1}(\pi^{\prime})\) holds (equality \(C_{max}(\pi^{\prime},\pi^{\prime\prime})=c_{2}(\pi^{\prime\prime})\) holds, respectively). For schedule \((\pi^{\prime},\pi^{\prime\prime})\in S\), the following equality holds:  
\[c_{1}(\pi^{\prime})=\sum_{j_{i}\in\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup \mathcal{J}_{1}}p_{i1}+I_{1};\quad c_{2}(\pi^{\prime\prime})=\sum_{j_{1}\in \mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}p_{i2}+I_{2},\]  
where \(I_{1}\) and \(I_{2}\) denote total idle times of machine \(M_{1}\) and machine \(M_{2}\) in the schedule \((\pi^{\prime},\pi^{\prime\prime})\), respectively. We next show that, if the condition in Inequalities (7) holds, then machine \(M_{2}\) is a main machine for schedule \((\pi^{\prime},\pi^{\prime\prime})\) and machine \(M_{2}\) has no idle time, i.e., machine \(M_{2}\) is completely filled in the segment \([0,c_{2}(\pi^{\prime\prime})]\) for processing jobs from the set \(\mathcal{J}_{1,2}\cup\mathcal{J}_{2,1}\cup\mathcal{J}_{2}\). At the initial time \(t=0\), machine \(M_{2}\) begins to process jobs from the set \(\mathcal{J}_{2,1}\cup\mathcal{J}_{2}\) without idle times until the time moment \(t_{1}=\sum_{j_{1}\in\mathcal{J}_{2,1}\cup\mathcal{J}_{2}}p_{i2}\).