# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 3 Problem Settings and Notations  
Using the notation \(\alpha|\beta|\gamma\)[24], the two-machine job-shop scheduling problem with minimizing the makespan is denoted as \(J2|n_{i}\leq 2|C_{max}\), where \(\alpha=J2\) denotes a job-shop system with two available machines, \(n_{i}\) is the number of stages for processing a job, and \(\gamma=C_{max}\) denotes the criterion of minimizing the makespan. In the problem \(J2|n_{i}\leq 2|C_{max}\), the set \(\mathcal{J}=\{I_{1},J_{2},...,J_{n}\}\) of the given jobs have to be processed on machines from the set \(\mathcal{M}=\{M_{1},M_{2}\}\). All jobs are available for processing from the initial time \(t=0\). Let \(O_{ij}\) denote an operation of the job \(J_{i}\in\mathcal{J}\) processed on machine \(M_{j}\in\mathcal{M}\). Each machine can process a job \(J_{i}\in\mathcal{J}\) no more than once provided that preemption of each operation \(O_{ij}\) is not allowed. Each job \(J_{i}\in\mathcal{J}\) has its own processing order (machine route) on the machines in \(\mathcal{M}\). Let \(\mathcal{J}_{1,2}\) denote a subset of the set \(\mathcal{J}\) of the jobs with the same machine route \((M_{1},M_{2})\), i.e., each job \(J_{i}\in\mathcal{J}_{1,2}\) has to be processed first on machine \(M_{1}\) and then on machine \(M_{2}\). Let \(\mathcal{J}_{2,1}\subseteq\mathcal{J}\) denote a subset of the jobs with the opposite machine route \((M_{2},M_{1})\). Let \(\mathcal{J}_{k}\subseteq\mathcal{J}\) denote a set of the jobs, which has to be processed only on machine \(M_{k}\in\mathcal{M}\). The partition \(\mathcal{J}=\mathcal{J}_{1}\bigcup\mathcal{J}_{2}\bigcup\mathcal{J}_{1,2} \bigcup\mathcal{J}_{2,1}\) holds. We denote \(m_{h}=|\mathcal{J}_{h}|\), where \(h\in\{1;2;1,2;2,1\}\). We first assume that the duration \(p_{ij}\) of each operation \(O_{ij}\) is fixed before scheduling. The considered criterion \(C_{max}\) is the minimization of the makespan (schedule length) as follows:  
\[C_{max}:=\min_{s\in S}C_{max}(s)=\min_{s\in S}\{\max\{C_{i}(s):J_{i}\in \mathcal{J}\}\},\]  
where \(C_{i}(s)\) denotes a completion time of the job \(J_{i}\in\mathcal{J}\) in the schedule \(s\) and \(S\) denotes a set of semi-active schedules existing for the problem \(J2|n_{i}\leq 2|C_{max}\). A schedule is called semi-active if no job (operation) can be processed earlier without changing the processing order or violating some given constraints [1; 25; 26]. [PERSON] [27] proved that the problem \(J2|n_{i}\leq 2|C_{max}\) is polynomially solvable and that the optimal schedule for this problem may be determined as a pair \((\pi^{\prime},\pi^{\prime\prime})\) of the job permutations (calling it a _[PERSON]'s pair of permutations_) such that \(\pi^{\prime}=(\pi_{1,2},\pi_{1},\pi_{2,1})\) is a sequence of all jobs from the set \(\mathcal{J}_{1}\bigcup\mathcal{J}_{1,2}\bigcup\mathcal{J}_{2,1}\) processed on machine \(M_{1}\) and \(\pi^{\prime\prime}=(\pi_{2,1},\pi_{2},\pi_{1,2})\) is a sequence of all jobs from the set \(\mathcal{J}_{2}\bigcup\mathcal{J}_{1,2}\bigcup\mathcal{\tilde{J}}_{2,1}\) processed on machine \(M_{2}\). Job \(J_{j}\) belongs to the permutation \(\pi_{h}\) if \(J_{j}\in\mathcal{J}_{h}\). In a Jackson's pair \((\pi^{\prime},\pi^{\prime\prime})\) of the job permutations, the order for processing jobs from set \(\mathcal{J}_{1}\) (from set \(\mathcal{J}_{2}\), respectively) may be arbitrary, while for the permutation \(\pi_{1,2}\), the following inequality holds for all indexes \(k\) and \(m\), \(1\leq k<m\leq m_{1,2}\):  
\[\min\{p_{i_{k}1},p_{i_{m}2}\}\leq\min\{p_{i_{m}1},p_{i_{k}2}\} \tag{1}\]  
(for the permutation \(\pi_{2,1}\), the following inequality holds for all indexes \(k\) and \(m\), \(1\leq k<m\leq m_{2,1}\)) [28]:  
\[\min\{p_{j_{k}2},p_{j_{m}1}\}\leq\min\{p_{j_{m}2}p_{j_{k}1}\} \tag{2}\]  
The aim of this paper is to investigate the uncertain two-machine job-shop scheduling problem.