# Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
## 7 Computational Experiments
We also tested classes 10-15 of the hard instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) characterized by the following ratios (Equation (18)):  
\(3\%:2\%:5\%:90\%\) (Table A10); \(2\%:3\%:5\%:90\%\) (Table A11);  
\(2\%:2\%:1\%:95\%\) (Table A12); \(1\%:2\%:2\%:95\%\) (Table A13);  
\(1\%:1\%:3\%:95\%\) (Table A14); \(1\%:1\%:97\%\) (Table A15). All Tables A1-A15 are organized as follows. Number \(n\) of given jobs \(\mathcal{J}\) in the instances of the problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) are presented in column 1. The values of \(\delta\) (a maximum relative length of the given segment of the job durations) in percentages are presented in the firstline of each table. For the fixed value of \(\delta\), the obtained computational results are presented in four columns called \(Opt\), \(NC\), \(SC\), and \(t\). The column \(Opt\) determines the percentage of instances from the series of 1000 randomly generated instances which were optimally solved using Algorithms 1 - 4. For each such instance, an optimal pair \((\pi^{\prime},\pi^{\prime\prime})\) of the job permutations was constructed in spite of the uncertain durations of the given jobs \(\mathcal{J}\). In other words, the equality \(\mathcal{C}_{max}(\pi^{\prime},\pi^{\prime\prime})=C_{max}(\pi^{*},\pi^{**})\) holds, where \((\pi^{*},\pi^{**})\in S\) is a pair of job permutations which is optimal for the deterministic problem \(J2|p^{*},n_{i}\leq 2|C_{max}\) associated with the factual scenario \(p^{*}\in T\). The factual scenario \(p^{*}\in T\) for the instance of the uncertain problem \(J2|l_{ij}\leq p_{ij}\leq u_{ij},n_{i}\leq 2|C_{max}\) is assumed to be unknown until completing the jobs \(\mathcal{J}\). Column \(NC\) presents total number of conflict sets of the jobs in the partial strict orders \(A_{\prec}^{1.2}\) on the job sets \(\mathcal{J}_{1,2}\) and partial strict orders \(A_{\prec}^{2,1}\) on the job sets \(\mathcal{J}_{2,1}\) constructed by Algorithm 2. The value of \(NC\) is equal to the total number of decision points, where Algorithm 2 has to select an order for processing jobs from the corresponding conflict set. To make a _correct decision_ for such an order means to construct a permutation of all jobs from the conflict set, which is optimal for the factual scenario (which is unknown before scheduling). In particular, if all conflict sets have received correct decisions in Algorithm 2, then the constructed pair of job permutations will be optimal for the problem \(J2|p^{*},n_{i}\leq 2|C_{max}\), where \(p^{*}\in T\) is the factual scenario. Column \(SC\) presents a percentage of the correct decisions made for determining optimal orders of the conflict jobs by Algorithm 2 with Algorithms 3 and 4. Column \(t\) presents a total CPU time (in seconds) for solving all 1000 instances of the corresponding series. Average percentages of the instances which were optimally solved (\(Opt\)) are presented in Figure 1 for classes 1-9 of the tested instances and in Figure 2 for classes 10-15 of the hard-tested instances. Percentages of the average values of the correct decisions (\(SC\)) made for determining optimal orders of the conflict jobs for classes 1-9 are presented in Figure 3. Most instances from these nine classes were optimally solved (Table 2). If the values of \(\delta\) were no greater than 20%, i.e., \(\delta\in\{5\%,10\%,15\%,20\%\}\), then more than 80% of the tested instances were optimally solved in spite of the data uncertainty. If the value \(\delta\) is increased, the percentage of the optimally solved instances decreased. If the value \(\delta\) was equal to 50%, then 45% of the tested instances was optimally solved. For all series of the hard instances presented in Tables A10-A15 (see the third line in Table 2), only a few instances were optimally solved. If \(\delta=5\%\), then 70% of the tested instances was optimally solved. If value \(\delta\) belongs to the set \(\{20\%,30\%,40\%,50\%\}\), then only 1% of the tested instances was optimally solved.