# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 3 Problem Settings and Notations
Therefore, we next assume that duration \(p_{ij}\) of each operation \(O_{ij}\) is unknown before scheduling; namely, in the realization of a schedule, a value of \(p_{ij}\) may be equal to any real number no less than the given lower bound \(l_{ij}\) and no greater than the given upper bound \(u_{ij}\). Furthermore, it is assumed that probability distributions of random durations of the jobs are unknown before scheduling. Such a job-shop scheduling problem is denoted as \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). The problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) is called an uncertain scheduling problem in contrast to the deterministic scheduling problem \(J2|n_{i}\leq 2|C_{max}\). Let a set of all possible vectors \(p=(p_{1,1},p_{1,2},\ldots,p_{n1},p_{n2})\) of the job durations be determined as follows: \(T=\{p\ :\ \ l_{ij}\leq p_{ij}\leq u_{ij},\ J_{i}\in\mathcal{J},\ M_{j}\in \mathcal{M}\}\). Such a vector \(p=(p_{1,1},p_{1,2},\ldots,p_{n1},p_{n2})\in T\) of the possible durations of the jobs is called a scenario. It should be noted that the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) is mathematically incorrect. Indeed, in most cases, a single pair of job permutations which is optimal for all possible scenarios\(p\in T\) for the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) does not exist. Therefore, in the general case, one cannot find an optimal solution for this uncertain scheduling problem. For a fixed scenario \(p\in T\), the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) turns into the deterministic problem \(J2|n_{i}\leq 2|C_{max}\) associated with scenario \(p\). The latter deterministic problem is an individual one and we denote it as \(J2|p,n_{i}\leq 2|C_{max}\). For any fixed scenario \(p\in T\), there exists a Jackson's pair of the job permutations that is optimal for the individual deterministic problem \(J2|p,n_{i}\leq 2|C_{max}\) associated with scenario \(p\). Let \(S_{1,2}\) denote a set of all permutations of \(m_{1,2}\) jobs from the set \(\mathcal{J}_{1,2}\), where \(|S_{1,2}|=m_{1,2}!\). Let \(S_{2,1}\) denote a set of all permutations of \(m_{2,1}\) jobs from the set \(\mathcal{J}_{2,1}\), where \(|S_{2,1}|=m_{2,1}!\). Let \(S=<S_{1,2}\), \(S_{2,1}>\) be a subset of the Cartesian product \((S_{1,2},\pi_{1},S_{2,1})\times(S_{2,1},\pi_{2},S_{1,2})\) such that each element of the set \(S\) is a pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\in S\), where \(\pi^{\prime}=(\pi_{1,2}^{i},\pi_{1},\pi_{2,1}^{j})\) and \(\pi^{\prime\prime}=(\pi_{2,1}^{j},\pi_{2},\pi_{1,2}^{i})\), \(1\leq i\leq m_{1,2}!\), \(1\leq j\leq m_{2,1}!\). The set \(S\) determines all semi-active schedules and vice versa. **Remark 1**. : _As an order for processing jobs from set \(\mathcal{J}_{1}\) (from set \(\mathcal{J}_{2}\)) may be arbitrary in the [PERSON]'s pair of job permutations \((\pi^{\prime},\pi^{\prime\prime})\), in what follows, we fix both permutations \(\pi_{1}\) and \(\pi_{2}\) in the increasing order of the indexes of their jobs. Thus, both permutations \(\pi_{1}\) and \(\pi_{2}\) are now fixed, and so their upper indexes are omitted in each permutation from the pair \((\pi^{\prime},\pi^{\prime\prime})=((\pi_{1,2}^{i},\pi_{1},\pi_{2,1}^{j}),(\pi_ {2,1}^{j},\pi_{2,2},\pi_{1,2}^{i}))\)._  
Due to Remark 1, the equality \(|S|=m_{1,2}!\cdot m_{2,1}!\) holds. The following definition is used for a \(J\)-solution for the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). **Definition 1**.