## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
We also answered the question of how small the obtained relative error \(\Delta\) of the value \(\gamma_{p^{*}}^{k}\) of the objective function \(\sum C_{i}\) was for the permutation \(\pi_{k}\) with the minimal value of \(F(\pi_{k},T)\). We compared the relative error \(\Delta\) with the relative error \(\Delta_{mid-p}\) of the value \(\gamma_{p^{*}}^{m}\) of the objective function \(\sum C_{i}\) for the permutation \(\pi_{mid-p}\) obtained for determining the job processing times using the mid-points of the given segments. We compared the relative error \(\Delta\) with the relative error \(\Delta_{max}\) of the value of the objective function \(\sum C_{i}\) for the permutation \(\pi_{max}\) constructed by Algorithm MAX-OPTBOX derived in [15]. The number \(n\) of jobs in the instance is given in column 1 in Table 2. The half of the maximum possible errors \(\delta\) of the random processing times (in percentage) is given in column 2. Column 3 gives the average error \(\Delta\) for the permutation \(\pi_{k}\) with the minimal value of \(F(\pi_{k},T)\). Column 4 presents the average error \(\Delta_{mid-p}\) obtained for the mid-point permutations \(\pi_{mid-p}\), where all jobs are ordered according to increasing mid-points of their segments. Column 5 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 6 presents the relation \(\Delta_{mid-p}/\Delta\). Column 7 presents the relation \(\Delta_{max}/\Delta\). Column 8 presents the average CPU-time of Algorithm 3 for the solved instances in seconds. The computational experiments showed that for all solved examples of class 1, the permutations \(\pi_{k}\) with the minimal values of \(F(\pi_{k},T)\) for their optimality boxes generated good objective function values \(\gamma_{p^{*}}^{k}\), which are smaller than those obtained for the permutations \(\pi_{mid-p}\) and for the permutations\(\pi_{max}\). The smallest errors, average errors, largest errors for the tested series of the instances are presented in the last rows of Table 2.

In the second part of our experiments, Algorithm 3 was applied to the randomly generated instances from other hard classes 2-7 of the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). We randomly generated non-fixed jobs \(J_{1},J_{2},\ldots,J_{s}\), which belong to all blocks \(B_{1}\), \(B_{2}\), \(\ldots\), \(B_{m}\) of the randomly generated \(n-s\) fixed jobs. The lower bound \(p_{i}^{L}\) and the upper bound \(p_{i}^{U}\) on the feasible values of \(p_{i}\in R_{+}^{1}\) of the processing times of the fixed jobs, \(p_{i}\in[p_{i}^{L},p_{i}^{U}]\), were generated as follows. We determined a bound of blocks \([\widetilde{p}_{i}^{L},\widetilde{p}_{i}^{U}]\) for generating the cores of the blocks \([b_{i}^{L},b_{i}^{U}]\subseteq[\widetilde{b}_{i}^{L},\widetilde{b}_{i}^{U}]\) and for generating the segments \([p_{i}^{L},p_{i}^{U}]\) for the processing times of \(|B_{i}|\) jobs from all blocks \(B_{i}\), \(i\in\{1,2,3\}\), \([b_{i}^{L},b_{i}^{U}]\subseteq[p_{i}^{L},p_{i}^{U}]\subseteq[\widetilde{b}_{ i}^{L},\widetilde{b}_{i}^{U}]\). Each instance in class 2 has fixed jobs \(J_{i}\in\mathcal{J}\) with rather closed centers \((p_{i}^{L}+p_{i}^{U})/2\) and large difference between segment lengths \(p_{i}^{U}-p_{i}^{L}\). Each instance in class 3 or in class 4 has a single non-fixed job \(J_{v}\), whose bounds are determined as follows: \(p_{j_{v}}^{L}\leq\widetilde{b}_{1}^{L}\leq\widetilde{b}_{1}^{U}<\widetilde{b}_ {2}^{L}\leq\widetilde{b}_{2}^{U}<\widetilde{b}_{3}^{L}\leq\widetilde{b}_{3}^{ U}\leq p_{J_{v}}^{U}\). Classes 3 and 4 of the solved instances differ one from another by the numbers of non-fixed jobs and the distribution laws used for choosing the factual processing times of the jobs \(\mathcal{J}\). Each instance from classes 5 and 6 has two non-fixed jobs.