## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
The factual processing time \(p_{i}^{*}\) becomes known after completing the job \(J_{i}\in\mathcal{J}\). If the permutation \(\pi_{k}=(\pi_{k_{1}},\pi_{k_{2}},\ldots,\pi_{k_{n}})\in S\) has the non-empty optimality box \(\mathcal{OB}(\pi_{k},T)\
eq\emptyset\), then one can calculate the following error function:

\[F(\pi_{k},T)=\sum_{i=1}^{n}\left(1-\frac{u_{k_{i}}^{*}-l_{k_{i}}^{*}}{p_{k_{i}} ^{U}-p_{k_{i}}^{L}}\right)(n-i+1)\,. \tag{7}\]

A value of the error function \(F(\pi_{k},T)\) characterizes how the objective function value of \(\sum_{i=1}^{n}C_{i}(\pi_{k},p^{*})\) for the permutation \(\pi_{k}\) may be close to the objective function value of \(\sum_{i=1}^{n}C_{i}(\pi_{t},p^{*})\) for the permutation \(\pi_{t}\in S\), which is optimal for the factual scenario \(p^{*}\in T\) of the job processing times. The function \(F(\pi_{k},T)\) characterizes the following difference

\[\sum_{i=1}^{n}C_{i}(\pi_{k},p^{*})-\sum_{i=1}^{n}C_{i}(\pi_{t},p^{*}), \tag{8}\]

which has to be minimized for a good approximate solution \(\pi_{k}\) to the uncertain problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\). The better approximate solution \(\pi_{k}\) to the uncertain problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{U}|\sum C_{i}\) will have a smaller value of the error function \(F(\pi_{k},T)\). The formula (7) is based on the cumulative property of the objective function \(\sum_{i=1}^{n}C_{i}(\pi_{k},T)\), namely, each relative error \(\left(1-\frac{u_{k_{i}}^{*}-l_{k_{i}}^{*}}{p_{k_{i}}^{U}-p_{k_{i}}^{L}}\right)>0\) obtained due to the wrong position of the job \(J_{k_{i}}\) in the permutation \(\pi_{k}\) is repeated \((n-i)\) times for all jobs, which succeed the job \(J_{k_{i}}\) in the permutation \(\pi_{k}\). Therefore, a value of the error function \(F(\pi_{k},T)\) must be minimized for a good approximation of the value of \(\sum_{i=1}^{n}C_{i}(\pi_{t},T)\) for the permutation \(\pi_{k}\). If the equality \(\mathit{Per\mathcal{OB}}(\pi_{k},T)=0\) holds, the error function \(F(\pi_{k},T)\) has the maximal possible value determined as follows: \(F(\pi_{k},T)=\sum_{i=1}^{n}\left(1-\frac{u_{k_{i}}^{*}-l_{k_{i}}^{*}}{p_{k_{i }}^{U}-p_{k_{i}}^{L}}\right)(n-i+1)=\sum_{i=1}^{n}\left(n-i+1\right)=\frac{n( n+1)}{2}\). The necessary and sufficient condition for the largest value of \(F(\pi_{k},T)=\frac{n(n+1)}{2}\) is given in Theorem 3. If the equality \(\mathit{Per\mathcal{OB}}(\pi_{k},T)=n\) holds, the error function \(F(\pi_{k},T)\) has the smallest value equal to 0: \(F(\pi_{k},T)=\sum_{i=1}^{n}\left(1-\frac{u_{k_{i}}^{*}-l_{k_{i}}^{*}}{p_{k_{i }}^{U}-p_{k_{i}}^{L}}\right)(n-i+1)=\sum_{i=1}^{n}\left(1-1\right)(n-i+1)=0\). The necessary and sufficient condition for the smallest value of \(F(\pi_{k},T)=0\) is given in Theorem 4, where the permutation \(\pi_{k}\in S\) is optimal for any factual scenario \(p^{*}\in T\) of the job processing times. Due to evident modifications of the proofs given in Section 3.3, it is easy to prove that Theorems 5 and 6 remain correct in the following forms. **Theorem 7**. : _If the equality \(B_{1}=\mathcal{J}\) holds, then it takes \(O(n)\) time to find the permutation \(\pi_{k}\in S\) and optimality box \(\mathcal{OB}(\pi_{k},T)\) with the smallest value of the error function \(F(\pi_{k},T)\) among all permutations \(S\)._

**Theorem 8**. : _Let each block \(B_{r}\in B\) contain at most one non-fixed job. The permutation \(\pi_{k}\in S\) with the smallest value of the error function \(F(\pi_{k},T)\) among all permutations \(S\) is constructed in \(O(n\log n)\) time._

Using Theorems 7 and 8, we developed the modifications of Procedures 3 and 4 for the minimization of the values of \(F(\pi_{k},T)\) instead of the maximization of the values of \(\mathit{Per\mathcal{OB}}(\pi_{k},T)\). The derived modifications of Procedures 3 and 4 are called Procedures 3\(+F(\pi_{k},T)\) and 4\(+F(\pi_{k},T)\), respectively. We modify also Procedures 2 and 5 for minimization of the values of \(F(\pi_{k},T)\) instead of the maximization of the values of \(\mathit{Per\mathcal{OB}}(\pi_{k},T)\).