## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
One can expect that the inequality \(\sum_{l_{i}\in\mathcal{J}}C_{i}(\pi_{k},p)\leq\sum_{l_{i}\in\mathcal{J}}C_{i}( \pi_{t},p)\) holds for more scenarios \(p\) from the set \(T\) than the opposite inequality \(\sum_{l_{i}\in\mathcal{J}}C_{i}(\pi_{k},p)>\sum_{l_{i}\in\mathcal{J}}C_{i}( \pi_{t},p)\). Next, we show how to construct a permutation \(\pi_{k}\in S\) with the largest value of the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\). The proof of Theorem 4 is based on Procedure 3. **Theorem 5**. : _If the equality \(B_{1}=\mathcal{J}\) holds, then it takes \(O(n)\) time to find the permutation \(\pi_{k}\in S\) and the optimality box \(\mathcal{OB}(\pi_{k},T)\) with the largest length of the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\) among all permutations \(S\)._  
Proof. : Since the equality \(B_{1}=\mathcal{J}\) holds, each permutation \(\pi_{k}\in S\) looks as follows: \(\pi_{k}=(J_{k_{1}},J_{k_{2}},\ldots,J_{k_{n}})\), where \(\{J_{k_{i}},J_{k_{2}},\ldots,J_{k_{n}}\}=B_{1}\). Due to Lemma 2, only job \(J_{k_{1}}\) may have the optimality segment (this segment looks as follows: \([p_{k_{1}}^{L},u_{k_{1}}^{*}]\)) and only job \(J_{n}\) may have the following optimality segment \([l_{k_{n}}^{*},p_{k_{n}}^{L}]\). The length \(u_{k_{1}}^{*}-p_{k_{1}}^{L}\) of the optimality segment \([p_{k_{1}}^{L},u_{k_{1}}^{*}]\) for the job \(J_{k_{1}}\) is determined by the second job \(J_{k_{2}}\) in the permutation \(\pi_{k}\). Similarly, the length \(p_{k_{n}}^{L}-l_{k_{n}}^{*}\) of the optimality segment \([l_{k_{n}}^{*},p_{k_{n}}^{L}]\) for the job \(J_{k_{n}}\) is determined by the second-to-last job \(J_{k_{n-1}}\) in the permutation \(\pi_{k}\). Hence, to find the optimality box \(\mathcal{OB}(\pi_{k},T)\) with the largest value of \(Per\mathcal{OB}(\pi_{k},T)\), it is needed to test only four jobs \(J_{k_{1}}\), \(J_{k_{2}}\), \(J_{k_{n-1}}\) and \(J_{k_{n}}\) from the block \(B_{1}=\mathcal{J}\), which provide the largest relative optimality segments for the jobs \(J_{k_{1}}\) and \(J_{k_{n}}\). To this end, we should choose the job \(J_{k_{i}}\) such that the following equality holds: \(p_{k_{i}}^{L}=\min_{J_{k_{i}}\in B_{1}}\frac{p_{k_{i}}^{L}-p_{k_{n}}^{L}}{p_{k_ {n}}^{L}-p_{k_{n}}^{L}}\). Then, if \(B_{1}\setminus\{J_{k_{i}}\}\
eq\emptyset\), we should choose the job \(J_{k_{n}}\) such that the equality \(p_{k_{n}}^{L}=\max_{J_{k_{i}}\in B_{1}\setminus\{J_{k_{i}}\}}\frac{p_{k_{n}}^{L }-p_{k_{n}}^{L}}{p_{k_{n}}^{L}-p_{k_{n}}^{L}}\) holds. Then, if \(B_{1}\setminus\{J_{k_{i}},J_{k_{n}}\}\
eq\emptyset\), we should choose the job \(J_{k_{i+1}}\) such that the equality \(p_{k_{i+1}}^{L}=\min_{J_{k_{i}}\in B_{1}\setminus\{J_{k_{i}},J_{k_{n}}\}}p_{k_{n}} ^{L}\) holds. Then, if \(B_{1}\setminus\{J_{k_{i}},J_{k_{i+1}},J_{k_{n}}\}\
eq\emptyset\), we should choose the job \(J_{k_{n-1}}\) such that the equality \(p_{k_{n-1}}^{L}=\max_{J_{k_{i}}\in B_{1}\setminus\{J_{k_{i}},J_{k_{i+1}},J_{k_{n} }\}}p_{k_{n}}^{L}\) holds. Thus, to determine the largest value of \(Per\mathcal{OB}(\pi_{k},T)\), one has either to test a single job or to test two jobs or three jobs or to choose and test four jobs from the block \(B_{1}\), where \(|B_{1}|\geq 4\), independently of how large the cardinality \(|B_{1}|\) of the set \(B_{1}\) is. In the worst case, one has to test at most \(4!=24\) permutations of the jobs chosen from the set \(B_{1}\). Due to the direct testing of the chosen jobs, one selects a permutation of \(|B_{1}|\) jobs, which provides the largest length of the relative perimeter \(Per\mathcal{OB}(\pi_{k},T)\) for all \(|B_{1}|!\) permutations \(\pi_{k}\). If \(B_{1}=\mathcal{J}\), the above algorithm (we call it Procedure 3) for finding the permutation \(\pi_{k}\) with the largest value of \(Per\mathcal{OB}(\pi_{k},T)\) takes \(O(n)\) time. Theorem 5 has been proven. **Remark 2**.