# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 7 Computational Experiments  
We describe the conducted computational experiments and discuss the results obtained for randomly generated instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). In the computational experiments, each tested series consisted of 1000 randomly generated instances with the same numbers \(n\in\{10,20,\ldots,100,200,\ldots,1000,2000,\ldots,10.000\}\) of jobs in the set \(\mathcal{J}\) provided that a maximum relative length \(\delta\) of the given segment of the possible durations of the operations \(O_{ij}\) takes the following values: \(\{5\%,10\%,15\%,20\%,30\%,40\%,\) and \(50\%\}\). The lower bounds \(l_{ij}\) and upper bounds \(u_{ij}\) for possible values of the durations \(p_{ij}\) of the operations \(O_{ij}\), \(p_{ij}\in[l_{ij},u_{ij}]\) using the value \(\delta\) have been determined as follows. First, a value of the lower bound \(l_{ij}\) is randomly chosen from the segment \([10,1000]\) using a uniform distribution. Then, the upper bound \(u_{ij}\) is calculated using the following equality:  
\[u_{ij}=l_{ij}\left(1+\frac{\delta}{100}\right) \tag{17}\]  
For example, we assume that \(\delta=5\%\). Then, for the lower bounds \(l_{ij}=50\) and \(l_{ij}=500\), the upper bounds \(u_{ij}=52.5\) and \(u_{ij}=525\) are calculated using Reference (17). If \(\delta=50\%\), then based on the lower bounds \(l_{ij}=50\) and \(l_{ij}=500\) and on Reference (17), we obtain the upper bounds \(u_{ij}=75\) and \(u_{ij}=750\). Thus, rather wide ranges for the tested durations of the jobs \(\mathcal{J}\) were considered. In the experiments, the bounds \(l_{ij}\) and \(u_{ij}\) were decimal fractions with the maximum possible number of digits after the decimal point. For all tested instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\), a strict inequality \(l_{ij}<u_{ij}\) was guarantied for each job \(J_{i}\in\mathcal{J}\) and each machine \(M_{j}\in\mathcal{M}\). We used Algorithms 1 - 4 described in Section 5.4 and Section 6 for solving the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\). These algorithms were coded in C# and tested on a PC with Intel Core i7-7700 (TM) 4 Quad, 3.6 GHz, and 32.00 GB RAM. Since Algorithms 1 - 4 are polynomial in number \(n\) jobs in set \(\mathcal{J}\), the calculations were carried out quickly. In the experiments, we tested 15 classes of randomly generated instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) with different ratios between numbers \(m_{1}\), \(m_{2}\), \(m_{1,2}\), and \(m_{2,1}\) of the jobs in subsets \(\mathcal{J}_{1}\), \(\mathcal{J}_{2}\), \(\mathcal{J}_{1,2}\), and \(\mathcal{J}_{2,1}\) of the set \(\mathcal{J}\). The obtained computational results are presented in Tables A1-A15 for 15 classes of the solved instances. Each tested class of the instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) is characterized by the following ratio of the percentages of the number of jobs in the subsets \(\mathcal{J}_{1}\), \(\mathcal{J}_{2}\), \(\mathcal{J}_{1,2}\), and \(\mathcal{J}_{2,1}\) of the set \(\mathcal{J}\):  
\[\frac{m_{1}}{n}\cdot 100\%:\frac{m_{2}}{n}\cdot 100\%:\frac{m_{1,2}}{n} \cdot 100\%:\frac{m_{2,1}}{n}\cdot 100\% \tag{18}\]  
Tables A1-A9 present the computational results obtained for classes 1-9 of the tested instances characterized by the following ratios (Equation (18)):  
\(25\%:25\%:25\%:25\%\) (Table A1); \(10\%:10\%:40\%:40\%\) (Table A2);  
\(10\%:40\%:10\%:40\%\) (Table A3); \(10\%:30\%:10\%:50\%\) (Table A4);  
\(10\%:20\%:10\%:60\%\) (Table A5); \(10\%:10\%:10\%:70\%\) (Table A6);  
\(5\%:20\%:5\%:70\%\) (Table A7); \(5\%:15\%:5\%:75\%\) (Table A8);  
\(5\%:5\%:5\%:85\%\) (Table A9). Note that all instances from class 1 of the instances with the ratio from Equation (18), \(25\%:25\%:25\%\), were optimally solved by Algorithm 1 - 4 for all values of \(\delta\in\{5\%,10\%,15\%,20\%,30\%,40\%,\) and \(50\%\}\).