## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
In each instance from classes 2, 3, 5, 6 and 7, for generating the factual processing times for the jobs \(\mathcal{J}\), the numbers of the distribution law were randomly chosen from the set \(\{1,2,3\}\), and they are indicated in column 4 in Table 3. In the instances of class 7, the cores of the blocks were determined in order to generate different numbers of non-fixed jobs in different instances. The numbers of non-fixed jobs were randomly chosen from the set \(\{2,3,\ldots,8\}\). Numbers \(n\) of the jobs are presented in column 1. In Table 3, column 2 represents the number \(|B|\) of blocks in the solved instance and column 3 the number of non-fixed jobs. The distribution laws used for determining the factual job processing times are indicated in column 4 in \[u_{k_{i}}^{*}-l_{k_{i}}^{*}=p_{k_{i}}^{U}-p_{k_{i}}^{L}. \tag{3}\]0 Each solved series contained 10 instances with the same combination of \(n\) and the other parameters. The obtained smallest, average and largest values of \(\Delta\), \(\Delta_{mid-p}\), \(\frac{\Delta_{mid-p}}{\Delta}\) and \(\frac{\Delta_{max}}{\Delta}\) for each series of the tested instances are presented in columns 5, 6, 8 and 9 in Table 3 at the end of series. Column 7 presents the average relative perimeter of the optimality box \(\mathcal{OB}(\pi_{k},T)\) for the permutation \(\pi_{k}\) with the minimal value of \(F(\pi_{k},T)\). Column 10 presents the average CPU-time of Algorithm 3 for the solved instances in seconds. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \(n\) & \(\delta\) **(\%)** & \(\Delta\) **(\%)** & \(\Delta_{mid-p}\) **(\%)** & \(Per\mathcal{OB}(\pi_{k},T)\)** & \(\Delta_{mid-p}/\Delta\) & \(\Delta_{max}/\Delta\) & **CPU-Time (s)** \\ \hline
**1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline
100 & 1 & 0.08715 & 0.197231 & 1.6 & 2.263114 & 1.27022 & 0.046798 \\
100 & 5 & 0.305088 & 0.317777 & 1.856768 & 1.041589 & 1.014261 & 0.031587 \\
100 & 10 & 0.498286 & 0.500731 & 1.916064 & 1.001077 & 1.000278 & 0.033953 \\
500 & 1 & 0.095548 & 0.208343 & 1.6 & 2.18052 & 1.0385 & 0.218393 \\
500 & 5 & 0.273933 & 0.319028 & 1.909091 & 1.164623 & 1.017235 & 0.2146 \\
500 & 10 & 0.469146 & 0.486097 & 1.948988 & 1.036133 & 1.006977 & 0.206222 \\
1000 & 1 & 0.093147 & 0.21632 & 1.666667 & 2.322344 & 1.090832 & 0.542316 \\
1000 & 5 & 0.264971 & 0.315261 & 1.909091 & 1.189795 & 1.030789 & 0.542938 \\
1000 & 10 & 0.472471 & 0.494142 & 1.952143 & 1.045866 & 1.000832 & 0.544089 \\
5000 & 1 & 0.095824 & 0.217874 & 1.666667 & 2.273683 & 1.006018 & 7.162931 \\
5000 & 5 & 0.264395 & 0.319645 & 1.909091 & 1.208965 & 1.002336 & 7.132647 \\
5000 & 10 & 0.451069 & 0.481421 & 1.952381 & 1.06729 & 1.00641 & 7.137556 \\
10,000 & 1 & 0.095715 & 0.217456 & 1.666667 & 2.271905 & 1.003433 & 25.52557 \\
10,000 & 5 & 0.26198 & 0.316855 & 1.909091 & 1.209463 & 1.003251 & 25.5448 \\
10,000 & 10 & 0.454655 & 0.486105 & 1.952381 & 1.069175 & 1.003809 & 25.50313 \\ \hline
**Minimum** & 0.08715 & 0.197231 & 1.6 & 1.001077 & 1.000278 & 0.031587 \\
**Average** & 0.278892 & 0.339619 & 1.827673 & 1.489703 & 1.033012 & 6.692502 \\
**Maximum** & 0.498286 & 0.500731 & 1.952381 & 2.322344 & 1,27022 & 25.5448 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Computational results for randomly generated instances with a single block (class 1).