## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
In our computational experiments, we tested seven classes of harder problems, where the job permutation \(\pi_{k}\in S\) constructed by Algorithm 3 outperforms the mid-point permutation \(\pi_{mid-p}\) and the permutation \(\pi_{max}\) constructed by Algorithm MAX-OPTBOX derived in [15]. Algorithm MAX-OPTBOX and Algorithm 3 were coded in C# and tested on a PC with Intel Core (TM) 2 Quad, 2.5 GHz, 4.00 GB RAM. For all tested instances, inequalities \(p_{i}^{L}<p_{i}^{U}\) hold for all jobs \(J_{i}\in\mathcal{J}\). Table 2 presents computational results for randomly generated instances of the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) with \(n\in\{100,500,1000,5000,10,000\}\). The segments of the possible processing times have been randomly generated similar to that in [15]. An integer center \(C\) of the segment \([p_{i}^{L},p_{i}^{U}]\) was generated using a uniform distribution in the range \([1,100]\). The lower bound \(p_{i}^{L}\) of the possible processing time \(p_{i}\) was determined using the equality \(p_{i}^{L}=C\cdot(1-\frac{\delta}{100})\). Hereafter, \(\delta\) denotes the maximal relative error of the processing times \(p_{i}\) due to the given segments \([p_{i}^{L},p_{i}^{U}]\). The upper bound \(p_{i}^{U}\) was determined using the equality \(p_{i}^{U}=C\cdot(1+\frac{\delta}{100})\). Then, for each job \(J_{i}\in\mathcal{J}\), the point \(\underline{p}_{i}\) was generated using a uniform distribution in the range \([p_{i}^{L},p_{i}^{U}]\). In order to generate instances, where all jobs \(\mathcal{J}\) belong to a single block, the segments \([p_{i}^{L},p_{i}^{U}]\) of the possible processing times were modified as follows: \([\widetilde{p}_{i}^{L},\widetilde{p}_{i}^{U}]=[p_{i}^{L}+\underline{p}- \underline{p}_{i},\ \ p_{i}^{U}+\underline{p}-\underline{p}_{i}]\), where \(\underline{p}=\max_{i=1}^{n}\underline{p}_{i}\). Since the inclusion \(\underline{p}\in[\widetilde{p}_{i}^{L},\widetilde{p}_{i}^{U}]\) holds, each constructed instance contains a single block, \(|B|=1\). The maximum absolute error of the uncertain processing times \(p_{i}\), \(J_{i}\in\mathcal{J}\), is equal to \(\max_{i=1}^{n}(p_{i}^{U}-p_{i}^{L})\), and the maximum relative error of the uncertain processing times \(p_{i}\), \(J_{i}\in\mathcal{J}\), is not greater than \(2\delta\%\). We say that these instances belong to class 1. Similarly as in [15], three distribution laws were used in our experiments to determine the factual processing times of the jobs. (We remind that if inequality \(p_{i}^{L}<p_{i}^{U}\) holds, then the factual processing time of the job \(J_{i}\) becomes known after completing the job \(J_{i}\)) We call the uniform distribution as the distribution law with number 1, the gamma distribution with the parameters \(\alpha=9\) and \(\beta=2\) as the distribution law with number 2 and the gamma distribution with the parameters \(\alpha=4\) and \(\beta=2\) as the distribution law with number 3. In each instance of class 1, for generating the factual processing times for different jobs of the set \(\mathcal{J}\), the number of the distribution law was randomly chosen from the set \(\{1,2,3\}\). We solved 15 series of the randomly generated instances from class 1. Each series contains 10 instances with the same combination of \(n\) and \(\delta\). In the conducted experiments, we answered the question of how large the obtained relative error \(\Delta=\frac{\gamma_{p^{*}}^{k}-\gamma_{p^{*}}^{k}}{\gamma_{p^{*}}^{k}}\cdot 1 00\%\) of the value \(\gamma_{p^{*}}^{k}\) of the objective function \(\gamma=\sum_{i=1}^{n}C_{i}\) was for the permutation \(\pi_{k}\) with the minimal value of \(F(\pi_{k},T)\) with respect to the actually optimal objective function value \(\gamma_{p^{*}}^{t}\) calculated for the factual processing times \(p^{*}=(p_{1}^{*},p_{2}^{*},\ldots,p_{n}^{*})\in T\).