# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 5 Properties of the Optimal Pairs of Job Permutations  
We consider the uncertain job-shop problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) and prove sufficient conditions for determining a small dominant set of schedules for this problem. In what follows, we use Definition 4 of the dominant set \(DS(T)\subseteq S\) along with Definition 1 of the \(J\)-solution \(S(T)\subseteq S\).  
**Definition 4**.: _A set of the pairs of job permutations \(DS(T)\subseteq S\) is called a dominant set (of schedules) for the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) if, for each scenario \(p\in T\), the set \(DS(T)\) contains at least one optimal pair of job permutations for the individual deterministic problem \(J2|p,n_{i}\leq 2|C_{max}\) with scenario \(p\)._  
Every \(J\)-solution (Definition 1) is a dominant set for the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). Before processing jobs of the set \(\mathcal{J}\) (before the realization of a schedule \(s\in S\)), a scheduler does not know exact values of the job durations. Nevertheless, it is needed to choose a pair of permutationsof the jobs \(\mathcal{J}\), i.e., it is needed to determine orders of jobs for processing them on machine \(M_{1}\) and machine \(M_{2}\). When all jobs will be processed on machines \(\mathcal{M}\) (a schedule will be realized) and the job durations will take on exact values \(p_{ij}^{*}\), \(l_{ij}\leq p_{ij}^{*}\leq u_{ij}\), and so a factual scenario \(p^{*}\in T\) will be determined. A schedule \(s\) chosen for the realization should be optimal for the obtained factual scenario \(p^{*}\). In the stability approach, one can use two phases of scheduling for solving an uncertain scheduling problem: the off-line phase and the on-line phase. The off-line phase of scheduling is finished before starting the realization of a schedule. At this phase, a scheduler knows only given segments of the job durations and the aim is to find a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) which is optimal for the most scenarios \(p\in T\). After constructing a small dominant set of schedules \(DS(T)\), a scheduler can choose a pair of job permutations in the set \(DS(T)\), which dominates the most pairs of job permutations \((\pi^{\prime},\pi^{\prime\prime})\in S\) for the given scenarios \(T\). Note that making a decision at the off-line phase may be time-consuming since the realization of a schedule is not started.  
The on-line phase of scheduling can begin once the earliest job in the schedule \((\pi^{\prime},\pi^{\prime\prime})\) starts. At this phase, a scheduler can use additional on-line information on the job duration since, for each operation \(O_{ij}\), the exact value \(p_{ij}^{*}\) becomes known at the time of the completion of this operation. At the on-line phase, the selection of a next job for processing should be quick.  
In Section 5.1, we investigate sufficient conditions for a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\) such that equality \(DS(T)=\{(\pi^{\prime},\pi^{\prime\prime})\}\) holds. In Section 5.2, the sufficient conditions allowing to construct a single optimal schedule dominating all other schedules in the set \(S\) are proven. If a single-element dominant set \(DS(T)\) does not exist, then one should construct two partial strict orders \(A_{<}^{12}\) and \(A_{<}^{2.1}\) on the set \(\mathcal{J}_{1,2}\) and on the set \(\mathcal{J}_{2,1}\) of jobs as it is described in Section 4.2. These orders may be constructed in the form of the two precedence digraphs allowing a scheduler to reduce a size of the dominant set \(DS(T)\). Section 5.4 presents Algorithm 1 for constructing a semi-active schedule, which is optimal for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) for all possible scenarios \(T\) provided that such a schedule exists. Otherwise, Algorithm 1 constructs the precedence digraphs determining a minimal dominant set of schedules for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\).