# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 4 A Literature Review and Closed Results
### Closed Results
The partition \(\mathcal{J}=\mathcal{J}^{0}\cup\mathcal{J}^{1}\cup\mathcal{J}^{2}\cup \mathcal{J}^{*}\) of the set \(\mathcal{J}=\mathcal{J}_{1,2}\) is considered, where  
\(\mathcal{J}^{0}=\{l_{i}\in\mathcal{J}\ :\ u_{i1}\leq l_{l2},u_{2}\leq l_{l1}\}\),  
\(\mathcal{J}^{1}=\{l_{i}\in\mathcal{J}\ :\ u_{i1}\leq l_{l2},u_{2}>l_{1}\}=\{l_{i} \in\mathcal{J}\setminus\mathcal{J}^{0}\ :\ u_{i1}\leq l_{l2}\}\),  
\(\mathcal{J}^{2}=\{l_{i}\in\mathcal{J}\ :\ u_{i1}>l_{l2},u_{2}\leq l_{l1}\}=\{l_{i} \in\mathcal{J}\setminus\mathcal{J}^{0}\ :\ u_{i2}\leq l_{i1}\}\),  
\(\mathcal{J}^{*}=\{l_{i}\in\mathcal{J}\ :\ u_{i1}>l_{l2},u_{i2}>l_{11}\}\). For each job \(J_{k}\in\mathcal{J}^{0}\), inequalities \(u_{k1}\leq l_{k2}\) and \(u_{k2}\leq l_{k1}\) imply inequalities \(l_{k1}=u_{k1}=l_{k2}=u_{k2}\). Since both segments of the possible durations of the job \(J_{k}\) on machines \(M_{1}\) and \(M_{2}\) become a point, the durations \(p_{k1}\) and \(p_{k2}\) are fixed and equal for both machines \(M_{1}\) and \(M_{2}\): \(p_{k1}=p_{k2}=:p_{k}\). In Reference [41], Theorems 2 and 3 have been proven. **Theorem 2**. : _There exists a single-element \(J\)-solution \(S(T)\subset S\), \(|S(T)|=1\), for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) if and only if_  
_(a) for any pair of jobs \(J_{i}\) and \(J_{j}\) from the set \(\mathcal{J}^{1}\) (from the set \(\mathcal{J}^{2}\), respectively), either \(u_{i1}\leq l_{j1}\) or \(u_{j1}\leq l_{i1}\) (either \(u_{i2}\leq l_{j2}\) or \(u_{j2}\leq l_{l2}\)),_  
_(b) \(|\mathcal{J}^{*}|\leq 1\); for job \(l_{i^{*}}\in\mathcal{J}^{*}\), the inequalities \(l_{i^{*}1}\geq\max\{u_{i1}\ :J_{i}\in\mathcal{J}^{1}\}\), \(l_{i^{*}2}\geq\max\{u_{j2}\ :J_{j}\in\mathcal{J}^{2}\}\) hold; and \(\max\{l_{i^{*}1},\ l_{i^{*}2}\}\geq p_{k}\) for each job \(J_{k}\in\mathcal{J}^{0}\)._Theorem 2 characterizes the simplest case of the problem \(F2||_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) when one permutation \(\pi_{k}\) of the jobs \(\mathcal{J}=\mathcal{J}_{1,2}\) dominates all other job permutations. The hardest case of this problem is characterized by the following theorem. Theorem 3: _If \(\max\{l_{ik}\::\:J_{i}\in\mathcal{J},M_{k}\in\mathcal{M}\}<\min\{u_{ik}\::\:J_ {i}\in\mathcal{J},M_{k}\in\mathcal{M}\}\), then \(S(T)=S\)._  
The \(J\)-solution \(S(T)\) may be represented in a compact form using the dominance digraph which may be constructed in \(O(n^{2})\) time. Let \(\mathcal{J}\times\mathcal{J}\) denote the Cartesian product of two sets \(\mathcal{J}\). One can construct the following binary relation \(\mathcal{A}_{\preceq}\subseteq\mathcal{J}\times\mathcal{J}\) over set \(\mathcal{J}=\mathcal{J}_{1,2}\). Definition 2: For the two jobs \(J_{v}\in\mathcal{J}\) and \(J_{w}\in\mathcal{J}\), the inclusion \((J_{v},J_{w})\in\mathcal{A}_{\preceq}\) holds if and only if there exists a \(J\)-solution \(S(T)\) for the problem \(F2|l_{ij}\leq p_{ij}\leq u_{ij}|C_{max}\) such that job \(J_{v}\in\mathcal{J}\) is located before job \(J_{w}\in\mathcal{J}\), \(v\
eq w\), in all permutations \(\pi_{k}\), where \((\pi_{k},\pi_{k})\in S(T)\). The binary relation \((J_{v},J_{w})\in\mathcal{A}_{\preceq}\) is represented as follows: \(J_{v}\preceq J_{w}\). Due to Theorem 1, if for the jobs \(J_{v}\in\mathcal{J}\) and \(J_{w}\in\mathcal{J}\) the relation \(J_{v}\preceq J_{w}\), \(v\
eq w\), holds, then for the jobs \(J_{v}\) and \(J_{w}\), at least one of conditions in Inequalities (4) and (5) holds. To construct the binary relation \(\mathcal{A}_{\preceq}\) of the jobs on the set \(\mathcal{J}\), it is sufficient to check Inequalities (4) and (5) for each pair of jobs \(J_{v}\) and \(J_{w}\). The binary relation \(\mathcal{A}_{\preceq}\) determines the digraph \((\mathcal{J},\mathcal{A}_{\preceq})\) with vertex set \(\mathcal{J}\) and arc set \(\mathcal{A}_{\preceq}\). It takes \(O(n^{2})\) time to construct the digraph \((\mathcal{J},\mathcal{A}_{\preceq})\). In the general case, the binary relation \(\mathcal{A}_{\preceq}\) may be not transitive.